深圳幻海软件技术有限公司 欢迎您！
更多

Java基础汇总（十六）——LinkedHashMap

2023-04-21

方法 key 顺序
一、LinkedHashMap1.定义：        LinkedHashMap是HashMap和双向链表的合二为一，即一个将所有Entry节点链入一个双向链表的HashMap（LinkedHashMap=HashMa

一、LinkedHashMap

1.定义：

        LinkedHashMap是HashMap和双向链表的合二为一，即一个将所有Entry节点链入一个双向链表的HashMap（LinkedHashMap = HashMap + 双向链表）

  • LinkedHashMap和HashMap是Java Collection Framework 的重要成员，也是Map族(如下图所示)
  • LinkedHashMap是HashMap的子类（拥有HashMap的所有特性）
  • LinkedHashMap和HashMap最多只允许一条Entry的键为Null(多条会覆盖)，但允许多条Entry的值为Null
  • LinkedHashMap 也是 Map 的一个非同步的实现
  • LinkedHashMap很好的支持LRU算法
  • HashMap是无序的，LinkedHashMap通过维护一个额外的双向链表保证了迭代顺序
  • 迭代顺序可以是插入顺序，也可以是访问顺序（即根据链表中元素的顺序可以将LinkedHashMap分为：保持插入顺序的LinkedHashMap和保持访问顺序的LinkedHashMap，其中LinkedHashMap的默认实现是按插入顺序排序的）

 LinkedHashMap的原理图：

 LinkedHashMap和HashMap的Entry结构图：

2.LinkedHashMap在JDK中的定义

LinkedHashMap继承关系：

  1. public class LinkedHashMap<K,V>
  2. extends HashMap<K,V>
  3. implements Map<K,V>

LinkedHashMap成员变量：

  • 相比于Hashmap，LinkedHashMap新增 双向链表头结点header和标志位accessOrder 
  • accessOrder：
    • 默认为false（即默认按照插入顺序迭代）
    • 为true时（按照访问顺序迭代，支持实现LRU算法时）
  1. private static final long serialVersionUID = 3801124242820219131L;
  2. private transient Entry<K,V> header;//双向链表头节点，也即哨兵节点，里面不存储任何信息
  3. private final boolean accessOrder;//有序性标识

LinkedHashMap构造方法（5种）：

  • 相比于Hashmap，LinkedHashMap并没有增加构造方法
  1. //传入的参数为初始容量，加载因子，调用了父类的构造方法，按照插入顺序
  2. public LinkedHashMap(int initialCapacity, float loadFactor) {
  3.         super(initialCapacity, loadFactor);
  4.         accessOrder = false;
  5.     }
  6.  
  7. //传入的参数的初始容量，调用父类的构造方法，取得键值对的顺序是插入顺序
  8. public LinkedHashMap(int initialCapacity) {
  9.         super(initialCapacity);
  10.         accessOrder = false;
  11.     }
  12.  
  13. //无参构造，调用父类的构造方法，取得键值对的顺序是插入顺序
  14. public LinkedHashMap() {
  15.         super();
  16.         accessOrder = false;
  17.     }
  18.  
  19. //传入的参数是一个Map的集合，调用父类的构造方法，取得键值对的顺序是插入顺序
  20. public LinkedHashMap(Map<? extends K, ? extends V> m) {
  21.         super(m);
  22.         accessOrder = false;
  23.     }
  24.  
  25. //传入的参数为初始容量，加载因子，有序性标识（键值对保持顺序），调用了父类的构造方法
  26. public LinkedHashMap(int initialCapacity,
  27.                          float loadFactor,
  28.                          boolean accessOrder) {
  29.         super(initialCapacity, loadFactor);
  30.         this.accessOrder = accessOrder;
  31.     }

 LinkedHashMap的init()方法：

由 LinkedHashMap的五种构造方法可知：

  • 无论采用何种方式创建LinkedHashMap，其都会调用HashMap相应的构造函数
  • 不管调用HashMap的哪个构造函数，HashMap的构造函数都会在最后调用一个init()方法进行初始化
  • init()方法在HashMap中是一个空实现，而在LinkedHashMap中重写了它，用于初始化它所维护的双向链表
  1. //Hashmap
  2. /**
  3.  * Constructs an empty <tt>HashMap</tt> with the default initial capacity
  4.  * (16) and the default load factor (0.75).
  5.  */
  6. public HashMap() {
  7.     this.loadFactor = DEFAULT_LOAD_FACTOR;
  8.     threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
  9.     table = new Entry[DEFAULT_INITIAL_CAPACITY];
  10.     init();
  11. }
  12.  
  13.  
  14. //LinkedHashmap
  15. @Override
  16.     void init() {
  17.         //header初始化
  18.         //hash为-1，其他的参数均为null
  19.         //也就是说这个header不在数组中
  20.         //只是用来标志开始元素和标志结束元素的
  21.         header = new Entry<>(-1, null, null, null);
  22.         header.before = header.after = header;
  23.     }

LinkedHashMap基本数据结构（Entry：具体结构图在定义中）：

  • LinkedHashMap中的Entry增加了两个指针 before 和 after，用于维护双向链接列表
    • before、after用于维护Entry插入的先后顺序
    • next用于维护HashMap各个桶中Entry的连接顺序
  1. private static class Entry<K,V> extends HashMap.Entry<K,V> {
  2.         // These fields comprise the doubly linked list used for iteration.
  3.         Entry<K,V> before, after;
  4.  
  5.         Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
  6.             super(hash, key, value, next);
  7.         }

 LinkedHashMap(Map<? extends K, ? extends V> m)：

  • 构造一个与指定Map具有相同映射的 LinkedHashMap，其初始容量不小于16 (具体依赖于指定Map的大小)，负载因子是 0.75，是 Java Collection Framework 规范推荐提供的，源码如下：
  1. /**
  2.  * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with
  3.  * the same mappings as the specified map.  The <tt>LinkedHashMap</tt>
  4.  * instance is created with a default load factor (0.75) and an initial
  5.  * capacity sufficient to hold the mappings in the specified map.
  6.  *
  7.  * @param  m the map whose mappings are to be placed in this map
  8.  * @throws NullPointerException if the specified map is null
  9.  */
  10. public LinkedHashMap(Map<? extends K, ? extends V> m) {
  11.     super(m);       // 调用HashMap对应的构造函数
  12.     accessOrder = false;    // 迭代顺序的默认值
  13. }

3.LinkedHashMap的快速存取

LinkedHashMap 的存储实现 : put(key, vlaue)

  • LinkedHashMap完全继承了HashMap的 put(Key,Value) 方法
  1. public V put(K key, V value) {
  2.         if (table == EMPTY_TABLE) {      //数组为null时
  3.             inflateTable(threshold);     //给数组根据阈值分配内容空间
  4.         }
  5.         if (key == null)      //key为null时
  6.             return putForNullKey(value);
  7.         int hash = hash(key);  //通过key计算hash
  8.         int i = indexFor(hash, table.length);  //计算在数组中的索引位置
  9.         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  10.             Object k;
  11.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  12.                 V oldValue = e.value;
  13.                 e.value = value;
  14.                //使用的是LinkedHashMap重写的方法
  15.                          1 
  16.                 e.recordAccess(this);         
  17.                 return oldValue;
  18.             }
  19.         }
  20.  
  21.         modCount++;
  22.        //addEntry调用的是LinkedHashMap重写了的方法
  23.                  2 
  24.         addEntry(hash, key, value, i);     
  25.         return null;
  26.     }
  • 只是对put(Key,Value)方法所调用的recordAccess方法和addEntry方法进行了重写
  • addEntry方法中还调用了removeEldestEntry方法，该方法是用来被重写的，一般如果用LinkedHashmap实现LRU算法，就要重写该方法
  • 比如可以将该方法覆写为如果设定的内存已满，则返回true，这样当再次向LinkedHashMap中putEntry时，在调用的addEntry方法中便会将近期最少使用的节点删除掉（header后的那个节点）
  1. void recordAccess(HashMap<K,V> m) {      1
  2.             //将传入的HashMap类型的m强制转换成LinkedHashMap类型的    
  3.             LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;  
  4.             //accessOrder默认的是false，当accessOrder为true时进入
  5.             if (lm.accessOrder) { 
  6.                 lm.modCount++;
  7.                 //移除当前节点 
  8.                 remove(); 
  9.                 3      
  10.                 addBefore(lm.header);           
  11.             }
  12.         }  
  13.  
  14.  
  15. void addEntry(int hash, K key, V value, int bucketIndex) {           2
  16.         // 重写了HashMap中的createEntry方法
  17.         createEntry(hash, key, value, bucketIndex);  
  18.  
  19.         // Remove eldest entry if instructed
  20.         Entry<K,V> eldest = header.after;   //还是header自身
  21.         if (removeEldestEntry(eldest)) {            4
  22.             removeEntryForKey(eldest.key);
  23.         } else {  
  24.         //扩容到原来的2倍  
  25.         if (size >= threshold)             5
  26.             resize(2 * table.length);  
  27.     }  
  28. }
  29.  
  30.  
  31.  
  32.  
  33. protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {    4
  34.     return false;
  35. }
  • 在LinkedHashMap的addEntry方法中，它重写了HashMap中的createEntry方法
  1.  
  2. void createEntry(int hash, K key, V value, int bucketIndex) { 
  3.     // 向哈希表中插入Entry，这点与HashMap中相同 
  4.     //创建新的Entry并将其链入到数组对应桶的链表的头结点处， 
  5.     HashMap.Entry<K,V> old = table[bucketIndex];  
  6.     Entry<K,V> e = new Entry<K,V>(hash, key, value, old);  
  7.     table[bucketIndex] = e;     
  8.  
  9.     //在每次向哈希表插入Entry的同时，都会将其插入到双向链表的尾部，  
  10.     //这样就按照Entry插入LinkedHashMap的先后顺序来迭代元素
  11.     //(LinkedHashMap根据双向链表重写了迭代器)
  12.     //同时，新put进来的Entry是最近访问的Entry，把其放在链表末尾 ，也符合LRU算法的实现  
  13.     e.addBefore(header);  
  14.     size++;  
  15. }
  • 在LinkedHashMap中向哈希表中插入新Entry的同时，还会通过Entry的addBefore方法将其链入到双向链表中
  • addBefore方法本质上是一个双向链表的插入操作
  1. //插入有序不做处理，在访问有序做相应处理：addBefore（将当前节点插到header的前面）
  2. private void addBefore(Entry<K,V> existingEntry) {             3
  3.             after  = existingEntry;     //existingEntry即为header
  4.             before = existingEntry.before;
  5.             before.after = this;     //this即为要插入的节点
  6.             after.before = this;
  7. }
  8.
  • LinkedHashMap完全继承了HashMap的resize()方法，只是对它所调用的transfer方法进行了重写
  • Map扩容操作的核心在于重哈希
  • 重哈希是指重新计算原HashMap中的元素在新table数组中的位置并进行复制处理的过程，鉴于性能和LinkedHashMap自身特点的考量，LinkedHashMap对重哈希过程(transfer方法)进行了重写
  1. void resize(int newCapacity) {       5
  2.     Entry[] oldTable = table;
  3.     int oldCapacity = oldTable.length;
  4.  
  5.     // 若 oldCapacity 已达到最大值，直接将 threshold 设为 Integer.MAX_VALUE
  6.     if (oldCapacity == MAXIMUM_CAPACITY) {  
  7.         threshold = Integer.MAX_VALUE;
  8.         return;             // 直接返回
  9.     }
  10.  
  11.     // 否则，创建一个更大的数组
  12.     Entry[] newTable = new Entry[newCapacity];
  13.  
  14.     //将每条Entry重新哈希到新的数组中
  15.             6
  16.     transfer(newTable);  //LinkedHashMap对它所调用的transfer方法进行了重写
  17.  
  18.     table = newTable;
  19.     threshold = (int)(newCapacity * loadFactor);  // 重新设定 threshold
  20. }
  21.  
  22.  
  23.  
  24.  
  25. void transfer(HashMap.Entry[] newTable) {     6
  26.     int newCapacity = newTable.length;
  27.     // 与HashMap相比，借助于双向链表的特点进行重哈希使得代码更加简洁
  28.     for (Entry<K,V> e = header.after; e != header; e = e.after) {
  29.         int index = indexFor(e.hash, newCapacity);   // 计算每个Entry所在的桶
  30.         // 将其链入桶中的链表
  31.         e.next = newTable[index];
  32.         newTable[index] = e;   
  33.     }
  34. }

LinkedHashMap 的读取实现 ：get(Object key)

  1. public V get(Object key) {
  2. //调用父类HashMap的getEntry()方法，取得要查找的元素
  3.         Entry<K,V> e = (Entry<K,V>)getEntry(key);
  4.         if (e == null)
  5.             return null;
  6. // 记录访问顺序
  7.         e.recordAccess(this);
  8.         return e.value;
  9.     }
  10.  
  11.  
  12. private static class Entry<K,V> extends HashMap.Entry<K,V> {
  13.         // These fields comprise the doubly linked list used for iteration.
  14.         Entry<K,V> before, after;
  15.  
  16.         Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
  17.             super(hash, key, value, next);
  18.         }
  19.  
  20. //在HashMap的put和get方法中，会调用该方法，在HashMap中该方法为空；
  21. //在LinkedHashMap中，
  22. //当按访问顺序排序时，该方法会将当前节点插入到链表尾部(头结点的前一个节点)，
  23. //否则不做任何事
  24. void recordAccess(HashMap<K,V> m) {
  25.             LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
  26.             if (lm.accessOrder) {
  27.                 lm.modCount++;
  28. //移除当前节点
  29.                 remove();
  30. //将当前节点插入到头结点前面
  31.                 addBefore(lm.header);
  32.             }
  33.         }
  34.         private void addBefore(Entry<K,V> existingEntry) {
  35.             after  = existingEntry;
  36.             before = existingEntry.before;
  37.             before.after = this;
  38.             after.before = this;
  39.         }
  • recordAccess方法：
    • 如果链表中元素的排序规则是按照插入的先后顺序排序的话（accessOrder=false），该方法什么也不做
    • 如果链表中元素的排序规则是按照访问的先后顺序排序的话（accessOrder=true），则将e移到链表的末尾处
  • 调用LinkedHashMap的get(Object key)方法，返回值是 NULL，有如下两种可能：
    • 该 key 对应的值就是 null
    • HashMap 中不存在该 key

二、LinkeList与LRU(Least recently used，最近最少使用)算法

        当accessOrder标志位为true时，表示双向链表中的元素按照访问的先后顺序排列，可以看到，虽然Entry插入链表的顺序依然是按照其put到LinkedHashMap中的顺序，但put和get方法均有调用recordAccess方法（put方法在key相同时会调用）

        recordAccess方法判断accessOrder是否为true，如果是，则将当前访问的Entry（put进来的Entry或get出来的Entry）移到双向链表的尾部（key不相同时，put新Entry时，会调用addEntry，它会调用createEntry，该方法同样将新插入的元素放入到双向链表的尾部，既符合插入的先后顺序，又符合访问的先后顺序，因为这时该Entry也被访问了）

        当标志位accessOrder的值为false时，表示双向链表中的元素按照Entry插入LinkedHashMap到中的先后顺序排序，即每次put到LinkedHashMap中的Entry都放在双向链表的尾部，这样遍历双向链表时，Entry的输出顺序便和插入的顺序一致，这也是默认的双向链表的存储顺序

        当标志位accessOrder的值为false时，虽然也会调用recordAccess方法，但不做任何操作

具体分析代码见内容一、LinkedList

1.使用LinkedList实现LRU算法

  1. public class LRU<K,V> extends LinkedHashMap<K, V> implements Map<K, V>{
  2.  
  3.     private static final long serialVersionUID = 1L;
  4.  
  5.     public LRU(int initialCapacity,
  6.              float loadFactor,
  7.                         boolean accessOrder) {
  8.         super(initialCapacity, loadFactor, accessOrder);
  9.     }
  10.  
  11.     /** 
  12.      * @description 重写LinkedHashMap中的removeEldestEntry方法，当LRU中元素多余6个时，
  13.      *              删除最不经常使用的元素
  14.      * @author rico       
  15.      * @created 2017年5月12日 上午11:32:51      
  16.      * @param eldest
  17.      * @return     
  18.      * @see java.util.LinkedHashMap#removeEldestEntry(java.util.Map.Entry)     
  19.      */  
  20.     @Override
  21.     protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
  22.         // TODO Auto-generated method stub
  23.         if(size() > 6){
  24.             return true;
  25.         }
  26.         return false;
  27.     }
  28.  
  29.     public static void main(String[] args) {
  30.  
  31.         LRU<Character, Integer> lru = new LRU<Character, Integer>(
  32.                 16, 0.75f, true);
  33.  
  34.         String s = "abcdefghijkl";
  35.         for (int i = 0; i < s.length(); i++) {
  36.             lru.put(s.charAt(i), i);
  37.         }
  38.         System.out.println("LRU中key为h的Entry的值为： " + lru.get('h'));
  39.         System.out.println("LRU的大小 ：" + lru.size());
  40.         System.out.println("LRU ：" + lru);
  41.     }
  42. }

代码运行结果图

https://camo.githubusercontent.com/d6bb9433960255bc9266852d29706dc3c97a3945dc7908882c07bcf79ae297c8/687474703a2f2f7374617469632e7a7962756c756f2e636f6d2f5269636f3132332f676a7a386d6a76686b6b68776a6c7a72356f3862323779762f4c52552e706e67

2.LinkedList有序性原理分析

        LinkedHashMap 增加了双向链表头结点header 和 标志位accessOrder两个属性用于保证迭代顺序。但是要想真正实现其有序性，还差临门一脚，那就是重写HashMap 的迭代器，其源码实现如下：

  1. private abstract class LinkedHashIterator<T> implements Iterator<T> {
  2.     Entry<K,V> nextEntry    = header.after;
  3.     Entry<K,V> lastReturned = null;
  4.  
  5.     /**
  6.      * The modCount value that the iterator believes that the backing
  7.      * List should have.  If this expectation is violated, the iterator
  8.      * has detected concurrent modification.
  9.      */
  10.     int expectedModCount = modCount;
  11.  
  12.     public boolean hasNext() {         // 根据双向列表判断 
  13.             return nextEntry != header;
  14.     }
  15.  
  16.     public void remove() {
  17.         if (lastReturned == null)
  18.         throw new IllegalStateException();
  19.         if (modCount != expectedModCount)
  20.         throw new ConcurrentModificationException();
  21.  
  22.             LinkedHashMap.this.remove(lastReturned.key);
  23.             lastReturned = null;
  24.             expectedModCount = modCount;
  25.     }
  26.  
  27.     Entry<K,V> nextEntry() {        // 迭代输出双向链表各节点
  28.         if (modCount != expectedModCount)
  29.         throw new ConcurrentModificationException();
  30.             if (nextEntry == header)
  31.                 throw new NoSuchElementException();
  32.  
  33.             Entry<K,V> e = lastReturned = nextEntry;
  34.             nextEntry = e.after;
  35.             return e;
  36.     }
  37. }
  38.  
  39. // Key 迭代器，KeySet
  40. private class KeyIterator extends LinkedHashIterator<K> {   
  41.     public K next() { return nextEntry().getKey(); }
  42. }
  43.  
  44.    // Value 迭代器，Values(Collection)
  45. private class ValueIterator extends LinkedHashIterator<V> {
  46.     public V next() { return nextEntry().value; }
  47. }
  48.  
  49. // Entry 迭代器，EntrySet
  50. private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
  51.     public Map.Entry<K,V> next() { return nextEntry(); }
  52. }

三、总结

  • 上文是基于JDK1.6的实现，实际上JDK1.8对其进行了改动
  • linkedhashmap在hashmap的数组加链表结构的基础上，将所有节点连成了一个双向链表
  • 当主动传入的accessOrder参数为false时, 使用put方法时，新加入元素不仅加入哈希桶中，还被加入双向链表末尾，get方法使用时不会把元素放到双向链表尾部
  • 当主动传入的accessOrder参数为true时，使用put方法新加入的元素，如果遇到了哈希冲突，并且对key值相同的元素进行了替换，就会被放在双向链表的尾部，当元素超过上限且removeEldestEntry方法返回true时，直接删除最早元素以便新元素插入。如果没有冲突直接放入，同样加入到链表尾部。使用get方法时会把get到的元素放入双向链表尾部
  • inkedhashmap的扩容比hashmap来的方便，因为hashmap需要将原来的每个链表的元素分别在新数组进行反向插入链化，而linkedhashmap的元素都连在一个链表上，可以直接迭代然后插入
  • linkedhashmap的removeEldestEntry方法默认返回false，要实现LRU很重要的一点就是集合满时要将最久未访问的元素删除，在linkedhashmap中这个元素就是头指针指向的元素。实现LRU可以直接实现继承linkedhashmap并重写removeEldestEntry方法来设置缓存大小。jdk中实现了LRUCache也可以直接使用
  • 在put操作上，虽然LinkedHashMap完全继承了HashMap的put操作，但是在细节上还是做了一定的调整，比如，在LinkedHashMap中向哈希表中插入新Entry的同时，还会通过Entry的addBefore方法将其链入到双向链表中
  • 在扩容操作上，虽然LinkedHashMap完全继承了HashMap的resize操作，但是鉴于性能和LinkedHashMap自身特点的考量，LinkedHashMap对其中的重哈希过程(transfer方法)进行了重写
  • 在读取操作上，LinkedHashMap中重写了HashMap中的get方法（加入recordAccess方法，重写transfer方法），通过HashMap中的getEntry方法获取Entry对象

参考文章：

（LRU与linkedlist建议看Github）Java-Tutorial/Java集合详解5：深入理解LinkedHashMap和LRU缓存.md at master · h2pl/Java-Tutorial · GitHub

LinkedHashMap源码解读_ZQ_313的博客-CSDN博客 

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览44658 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪