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

访问顺序: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

来源：https://www.icode9.com/content-4-690351.html

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。