LinkedHashMap

该集合通过维护一个双向链表来提供可预测的迭代顺序的Hash表结构.
在某些情况下,能有固定的迭代顺序,但是可以避免TreeMap的排序开销.
特性:

• Hash表的优点
• 可预测的迭代顺序
• 迭代时间与元素个数正比,而不是容量(HashMap迭代时间与容量正比)
• 非线程安全

有序性的实现方式

HashMap提供了三个方法,分别用于节点操作时的后处理,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缓存实现

LRU(Least Recently Used): 按最近最少访问的策略淘汰数据;
采用访问顺序构造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;
     }
 };

 //插入数据
 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

构造函数之保证访问顺序

 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);
         });

访问顺序:
945
181
473
586
854
------
Insert:854,Access:945
Insert:586,Access:181
Insert:473,Access:473
Insert:181,Access:586
Insert: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:320
Insert:817,Key:817
Insert:639,Key:639
Insert:311,Key:311
Insert:253,Key:253

引用

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