LinkedHashMap

該集合通過維護一個雙向鏈表來提供可預測的迭代順序的Hash表結構.
在某些情況下,能有固定的迭代順序,但是可以避免TreeMap的排序開銷.
特性:

• Hash表的優(yōu)點
• 可預測的迭代順序
• 迭代時間與元素個數(shù)正比,而不是容量(HashMap迭代時間與容量正比)
• 非線程安全

有序性的實現(xiàn)方式

HashMap提供了三個方法,分別用于節(jié)點操作時的后處理,LinkedHashMap通過這三個方法來維護雙向鏈表.

    // Callbacks to allow LinkedHashMap post-actions    void afterNodeAccess(Node<K,V> p) { }    void afterNodeInsertion(boolean evict) { }    void afterNodeRemoval(Node<K,V> p) { }

典型的應用場景

按原始Map集合的順序來復制集合

例如按顧客購買順序來退貨.

void foo(Map m) {    Map copy = new LinkedHashMap(m);    ...}

LRU緩存實現(xiàn)

LRU(Least Recently Used): 按最近最少訪問的策略淘汰數(shù)據(jù);
采用訪問順序構造LinkedHashMap,覆蓋方法

protected boolean removeEldestEntry(Map.Entry<K,V> eldest){}

示例見下文:Lru緩存示例

API Example

Lru緩存示例

 int cacheSize = 4; float loadFactor = 0.75f; int capacity = (int) Math.ceil(cacheSize / loadFactor); LinkedHashMap<Integer, Object> linkedHashMap = new LinkedHashMap<Integer, Object>(capacity, loadFactor, true) {     @Override     protected boolean removeEldestEntry(Map.Entry<Integer, Object> eldest) {         boolean yes = size() > cacheSize;         if (yes) {             println("淘汰:"   eldest.getKey());         }         return yes;     } }; //插入數(shù)據(jù) Random random = new Random(); List<Integer> randomData = Stream.generate(() -> random.nextInt(1000))         .limit(cacheSize)         .map(v -> {             linkedHashMap.put(v, v);             return v;         })         .collect(Collectors.toList()); System.out.println("Map Size:"   linkedHashMap.size()); //正序訪問 IntStream.range(0, randomData.size())         .map(index ->                 randomData.get(index))         .forEach(key ->                 println("訪問:"   linkedHashMap.get(key))); Stream.generate(() -> random.nextInt(1000))         .limit(cacheSize * 2)         .forEach(v -> {             println("新增:"   v);             linkedHashMap.put(v, v);         });

Map Size:4訪問:399訪問:514訪問:277訪問:917新增:746淘汰:399新增:213淘汰:514新增:616淘汰:277新增:718淘汰:917新增:634淘汰:746新增:442淘汰:213新增:985淘汰:616新增:113淘汰:718

構造函數(shù)之保證訪問順序

 LinkedHashMap<Integer, Object> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true); Random random = new Random(); List<Integer> randomData = Stream.generate(() -> random.nextInt(1000))         .limit(5)         .collect(Collectors.toList()); //正序插入 randomData.forEach(v -> linkedHashMap.put(v, v)); //倒序訪問 println("訪問順序:"); IntStream.range(0, randomData.size())         .map(i ->                 randomData.size() - 1 - i)         .map(index ->                 randomData.get(index))         .forEach(key ->                 println(linkedHashMap.get(key))); List<Integer> keySet = new ArrayList<>(linkedHashMap.keySet()); println("------"); //比較插入順序和訪問順序 IntStream.range(0, linkedHashMap.size())         .forEach(i -> {             Integer insertKey = randomData.get(i);             Integer key = keySet.get(i);             System.out.printf("Insert:%d,Access:%d\n", insertKey, key);         });

訪問順序:945181473586854------Insert:854,Access:945Insert:586,Access:181Insert:473,Access:473Insert:181,Access:586Insert:945,Access:854

默認保證插入順序

 LinkedHashMap<Integer, Object> linkedHashMap = new LinkedHashMap<>(); Random random = new Random(); List<Integer> randomData = Stream.generate(() -> random.nextInt(1000))         .limit(5)         .collect(Collectors.toList()); //正序插入 randomData.forEach(v -> linkedHashMap.put(v, v)); List<Integer> keySet = new ArrayList<>(linkedHashMap.keySet()); long diffOrderCount = IntStream.range(0, linkedHashMap.size())         .map(i -> {             Integer insertKey = randomData.get(i);             Integer key = keySet.get(i);             System.out.printf("Insert:%d,Key:%d\n", insertKey, key);             return insertKey - key;         })         .filter(v -> v != 0).count(); assertEquals(diffOrderCount, 0L);

Insert:320,Key:320Insert:817,Key:817Insert:639,Key:639Insert:311,Key:311Insert:253,Key:253

引用

• 源碼
• JDK8 java.util.TreeSet Source Code