【搞定Java集合框架】第7篇：深入理解 LinkedHashMap 和 LRU 缓存

小鱼儿 2022-03-26 07:46 209阅读 0赞

本文内容大部分来自于：[https://blog.csdn.net/a724888/article/details/80290276][https_blog.csdn.net_a724888_article_details_80290276]

## **本文目录：** ##

**1、LinkedHashMap 概述 **

**2、LinkedHashMap 在 JDK 中的定义**

2.1  类结构定义

2.2  成员变量定义

2.3  成员方法定义

2.4  基本元素 Entry

2.5  LinkedHashMap 的构造函数

2.6  LinkedHashMap 的数据结构

2.7  LinkedHashMap 的快速存取

**3、LinkedHashMap 与 LRU**

3.1  put 操作与标志位 accessOrder

3.2  get 操作与标志位 accessOrder

3.3  LinkedListMap 与 LRU 小结

**4、使用 LinkedHashMap 实现 LRU 算法**

**5、LinkedHashMap 有序性原来分析**

**6、LinkedHashMap 【JDK1.8】**

**7、总结**

--------------------

*  ### 摘要 ###

> **HashMap 和双向链表合二为一即是 LinkedHashMap**。所谓LinkedHashMap，其落脚点在 HashMap，因此更准确地说，它是一个将所有 Entry 节点链入一个双向链表的 HashMap。
> 
> 由于 LinkedHashMap 是 HashMap 的子类，所以 LinkedHashMa p自然会拥有 HashMap 的所有特性。比如：LinkedHashMap 的元素存取过程基本与 HashMap 基本类似，只是在细节实现上稍有不同。当然，这是由 LinkedHashMap 本身的特性所决定的，因为它**额外维护了一个双向链表用于保持迭代顺序**。
> 
> 此外，LinkedHashMap 可以很好的支持 LRU 算法，笔者在第七节便在 LinkedHashMap 的基础上实现了一个能够很好支持 LRU 的结构。

*  ### 友情提示 ###

> 本文所有关于 LinkedHashMap 的源码都是基于 JDK 1.6 的，不同 JDK 版本之间也许会有些许差异，但不影响我们对 LinkedHashMap 的数据结构、原理等整体的把握和了解。后面会讲解 JDK1.8 对于 LinkedHashMap 的改动。
> 
> 　　由于 LinkedHashMap 是 HashMap 的子类，所以其具有 HashMap 的所有特性，这一点在源码共用上体现的尤为突出。因此，读者在阅读本文之前，最好对 HashMap 有一个较为深入的了解和回顾，否则很可能会导致事倍功半。可以参考我之前关于 [HashMap][] 的文章。

--------------------

# 1、LinkedHashMap 概述  #

HashMap 是 Java Collection Framework 的重要成员，也是 Map 族（如下图所示）中我们最为常用的一种。不过遗憾的是，**HashMap是无序的**，也就是说，迭代 HashMap 所得到的元素顺序并不是它们最初放置到 HashMap 的顺序。

HashMap的这一缺点往往会造成诸多不便，因为在有些场景中，我们确需要用到一个可以保持插入顺序的Map。庆幸的是，JDK为我们解决了这个问题，它为 HashMap 提供了一个子类 —— LinkedHashMap。**虽然 LinkedHashMap 增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序。 **

特别地，**该迭代顺序可以是插入顺序，也可以是访问顺序**。因此，根据链表中元素的顺序可以将 LinkedHashMap 分为：**保持插入顺序的 LinkedHashMap 和保持访问顺序的 LinkedHashMap**，其中 LinkedHashMap 的默认实现是按插入顺序排序的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

本质上，HashMap 和双向链表合二为一即是 LinkedHashMap。所谓 LinkedHashMap，其落脚点在 HashMap，因此更准确地说，它是一个将所有 Entry 节点链入一个双向链表的 HashMap。

在 LinkedHashMapMap 中，所有 put 进来的 Entry 都保存在如下面第 1 个图所示的哈希表中，但由于它又额外定义了一个以 head 为头结点的双向链表(如下面第 2 个图所示)。因此对于每次 put 进来 Entry，除了将其保存到哈希表中对应的位置上之外，还会将其插入到双向链表的尾部。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

更直观地，下图很好地还原了 LinkedHashMap 的原貌：HashMap 和双向链表的密切配合和分工合作造就了LinkedHashMap。特别需要注意的是，next 用于维护 HashMap 各个桶中的 Entry 链，before、after 用于维护LinkedHashMap 的双向链表，虽然它们的作用对象都是Entry，但是各自分离，是两码事儿。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2][]

其中，HashMap 与 LinkedHashMap 的 Entry 结构示意图如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 3][]

特别地，由于 LinkedHashMap 是 HashMap 的子类，所以 LinkedHashMap 自然会拥有 HashMap 的所有特性。比如：LinkedHashMap 也最多只允许一条 Entr y的键为Null（多条会覆盖），但允许多条Entry的值为Null。  
　　   
　　此外，LinkedHashMap 也是 Map 的一个非同步的实现。此外，LinkedHashMap 还可以用来实现 LRU (Least recently used，最近最少使用)算法，这个问题会在下文的特别谈到。

--------------------

# 2、LinkedHashMap 在 JDK 中的定义 #

## 2.1  类结构定义 ##

LinkedHashMap 继承于 HashMap，其在 JDK 中的定义为：

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
    
        ...
    }

## 2.2  成员变量定义 ##

与 HashMap 相比，LinkedHashMap 增加了两个属性用于保证迭代顺序，分别是双向链表头结点 header 和 标志位accessOrder (值为 true 时，表示按照访问顺序迭代；值为false时，表示按照插入顺序迭代)。

// 双向链表的表头元素
    private transient Entry<K,V> header;
    
    // true表示按照访问顺序迭代，fasle表示按照插入顺序迭代
    private final boolean accessOrder;

## 2.3  成员方法定义 ##

从下图我们可以看出，LinkedHashMap 中并增加没有额外方法。也就是说，LinkedHashMap 与 HashMap 在操作上大致相同，只是在实现细节上略有不同罢了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 4][]

## 2.4  基本元素 Entry ##

LinkedHashMap 采用的 hash 算法和 HashMap 相同，但是它重新定义了 Entry。LinkedHashMap 中的 Entry 增加了两个指针 before 和 after，它们分别用于维护双向链表。特别需要注意的是，next 用于维护 HashMap 各个桶中 Entry 的连接顺序，before、after 用于维护 Entry 插入的先后顺序的，源代码如下：

private static class Entry<K,V> extends HashMap.Entry<K,V> {
    
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;
    
        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }
        ...
    }

形象地，HashMap 与 LinkedHashMap 的 Entry 结构示意图如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 5][]

## 2.5  LinkedHashMap 的构造函数 ##

LinkedHashMap 一共提供了五个构造函数，它们都是在HashMap的构造函数的基础上实现的，除了默认空参数构造方法，下面这个构造函数包含了大部分其他构造方法使用的参数，就不一 一列举了。

*  **LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)**

该构造函数意在构造一个指定初始容量和指定负载因子的具有指定迭代顺序的 LinkedHashMap，其源码如下：

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { 
    	
    	super(initialCapacity, loadFactor); // 调用HashMap对应的构造函数 
    	this.accessOrder = accessOrder;     // 迭代顺序的默认值 
    }

初始容量和负载因子是影响 HashMap 性能的两个重要参数。同样地，它们也是影响 LinkedHashMap 性能的两个重要参数。此外，LinkedHashMap 增加了双向链表头结点 header 和标志位 accessOrder 两个属性用于保证迭代顺序。

*  **init() 方法**

从上面的五种构造函数我们可以看出，无论采用何种方式创建 LinkedHashMap，其都会调用 HashMap 相应的构造函数。事实上，不管调用 HashMap 的哪个构造函数，HashMap 的构造函数都会在最后调用一个 init() 方法进行初始化，只不过这个方法在 HashMap 中是一个空实现，而在 LinkedHashMap 中重写了它用于初始化它所维护的双向链表。例如，HashMap的参数为空的构造函数以及 init() 方法的源码如下：

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
    }
    
    void init() { 
    }

在 LinkedHashMap 中，它重写了 init() 方法以便初始化双向列表，源码如下：

@Override
    void init() {
    	header = new Entry<>(-1, null, null, null);
    	header.before = header.after = header;
    }

## 2.6  LinkedHashMap 的数据结构 ##

**本质上，LinkedHashMap = HashMap + 双向链表，也就是说，HashMap 和双向链表合二为一即是 LinkedHashMap。**

也可以这样理解，LinkedHashMap 在不对 HashMap 做任何改变的基础上，给 HashMap 的任意两个节点间加了两条连线 (before 指针和 after 指针)，使这些节点形成一个双向链表。

**在 LinkedHashMapMap 中，所有 put 进来的 Entry 都保存在 HashMap 中，但由于它又额外定义了一个以 head 为头结点的空的双向链表，因此对于每次 put 进来 Entry 还会将其插入到双向链表的尾部。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 6][]

## 2.7  LinkedHashMap 的快速存取 ##

我们知道，在 HashMap 中最常用的两个操作就是：put(Key, Value) 和 get(Key)。同样地，在 LinkedHashMap 中最常用的也是这两个操作。

对于 put(Key,Value) 方法而言，LinkedHashMap 完全继承了 HashMap 的 put(Key,Value) 方法，只是对 put(Key,Value)方法所调用的 recordAccess 方法和 addEntry 方法进行了重写；对于 get(Key) 方法而言，LinkedHashMap 则直接对它进行了重写。

下面我们结合 JDK 源码看 LinkedHashMap 的存取实现。

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

上面谈到，LinkedHashMap 没有对 put(key,vlaue) 方法进行任何直接的修改，完全继承了 HashMap 的 put(Key,Value) 方法，其源码如下：

public V put(K key, V value) {
    
    	// 当key为null时，调用putForNullKey方法，并将该键值对保存到table的第一个位置 
    	if (key == null)
    		return putForNullKey(value); 
    
    	// 根据key的hashCode计算hash值
    	int hash = hash(key.hashCode());           
    
    	// 计算该键值对在数组中的存储位置（哪个桶）
    	int i = indexFor(hash, table.length);              
    
    	// 在table的第i个桶上进行迭代，寻找 key 保存的位置
    	for (Entry<K,V> e = table[i]; e != null; e = e.next) {      
    		Object k;
    		// 判断该条链上是否存在hash值相同且key值相等的映射，若存在，则直接覆盖 value，并返回旧value
    		if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    			V oldValue = e.value;
    			e.value = value;
    			e.recordAccess(this); // LinkedHashMap重写了Entry中的recordAccess方法--- (1)    
    			return oldValue;      // 返回旧值
    		}
    	}
    
    	modCount++;  // 修改次数增加1，快速失败机制
    
    	// 原Map中无该映射，将该添加至该链的链头
    	addEntry(hash, key, value, i);  // LinkedHashMap重写了HashMap中的createEntry方法 ---- (2)    
    	return null;
    }

上述源码反映了 LinkedHashMap 与 HashMap 保存数据的过程。特别地，在 LinkedHashMap 中，它对 addEntry 方法和 Entry 的 recordAccess 方法进行了重写。下面我们对比地看一下 LinkedHashMap 和 HashMap 的 addEntry 方法的具体实现：

// LinkedHashMap中的addEntry方法
    void addEntry(int hash, K key, V value, int bucketIndex) {   
    
    	// 创建新的Entry，并插入到LinkedHashMap中  
    	createEntry(hash, key, value, bucketIndex);  // 重写了HashMap中的createEntry方法
    
    	// 双向链表的第一个有效节点（header后的那个节点）为最近最少使用的节点，这是用来支持LRU算法的
    	Entry<K,V> eldest = header.after;  
    	// 如果有必要，则删除掉该近期最少使用的节点，  
    	// 这要看对removeEldestEntry的覆写,由于默认为false，因此默认是不做任何处理的。  
    	if (removeEldestEntry(eldest)) {  
    		removeEntryForKey(eldest.key);  
    	} else {  
    		// 扩容到原来的2倍  
    		if (size >= threshold)  
    			resize(2 * table.length);  
    	}  
    } 
    
    -------------------------------我是分割线------------------------------------
    
    // HashMap中的addEntry方法
    void addEntry(int hash, K key, V value, int bucketIndex) {
    	// 获取bucketIndex处的Entry
    	Entry<K,V> e = table[bucketIndex];
    
    	// 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry 
    	table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    
    	// 若HashMap中元素的个数超过极限了，则容量扩大两倍
    	if (size++ >= threshold)
    		resize(2 * table.length);
    }

由于 LinkedHashMap 本身维护了插入的先后顺序，因此其可以用来做缓存，中间有几步的操作就是用来支持LRU算法的，这里暂时不用去关心它。此外，在 LinkedHashMap 的 addEntry 方法中，它重写了 HashMap 中的 createEntry 方法，我们接着看一下 createEntry 方法：

void createEntry(int hash, K key, V value, int bucketIndex) { 
    	// 向哈希表中插入Entry，这点与HashMap中相同 
    	// 创建新的Entry并将其链入到数组对应桶的链表的头结点处， 
    	HashMap.Entry<K,V> old = table[bucketIndex];  
    	Entry<K,V> e = new Entry<K,V>(hash, key, value, old);  
    	table[bucketIndex] = e;     
    
    	// 在每次向哈希表插入Entry的同时，都会将其插入到双向链表的尾部，  
    	// 这样就按照Entry插入LinkedHashMap的先后顺序来迭代元素(LinkedHashMap根据双向链表重写了迭代器)
    	// 同时，新put进来的Entry是最近访问的Entry，把其放在链表末尾 ，也符合LRU算法的实现  
    	e.addBefore(header);  
    	size++;  
    }

由以上源码我们可以知道，在 LinkedHashMap 中向哈希表中插入新 Entry 的同时，还会通过 Entry 的 addBefore 方法将其链入到双向链表中。其中，addBefore 方法本质上是一个双向链表的插入操作，其源码如下：

// 在双向链表中，将当前的Entry插入到existingEntry(header)的前面  
    private void addBefore(Entry<K,V> existingEntry) {  
        after  = existingEntry;  
        before = existingEntry.before;  
        before.after = this;  
        after.before = this;  
    }

到此为止，我们分析了在 LinkedHashMap 中 put 一条键值对的完整过程。总的来说，相比 HashMap 而言，LinkedHashMap 在向哈希表添加一个键值对的同时，也会将其链入到它所维护的双向链表中，以便设定迭代顺序。

*  ### LinkedHashMap 的扩容操作 : resize() ###

在 HashMap 中，我们知道随着 HashMap 中元素的数量越来越多，发生碰撞的概率将越来越大，所产生的子链长度就会越来越长，这样势必会影响 HashMap 的存取速度。

为了保证 HashMap 的效率，系统必须要在某个临界点进行扩容处理，该临界点就是 HashMap 中元素的数量在数值上等于 threshold（table数组长度 \* 加载因子）。

但是，不得不说，扩容是一个非常耗时的过程，因为它需要重新计算这些元素在新 table 数组中的位置并进行复制处理。所以，如果我们能够提前预知 HashMap 中元素的个数，那么在构造 HashMap 时预设元素的个数能够有效的提高HashMap 的性能。

同样的问题也存在于 LinkedHashMap 中，因为 LinkedHashMap 本来就是一个 HashMap，只是它还将所有 Entry 节点链入到了一个双向链表中。LinkedHashMap 完全继承了 HashMap 的 resize() 方法，只是对它所调用的 transfer 方法进行了重写。我们先看 resize() 方法源码：

void resize(int newCapacity) {
    	Entry[] oldTable = table;
    	int oldCapacity = oldTable.length;
    
    	// 若 oldCapacity 已达到最大值，直接将 threshold 设为 Integer.MAX_VALUE
    	if (oldCapacity == MAXIMUM_CAPACITY) {  
    		threshold = Integer.MAX_VALUE;
    		return;             // 直接返回
    	}
    
    	// 否则，创建一个更大的数组
    	Entry[] newTable = new Entry[newCapacity];
    
    	// 将每条Entry重新哈希到新的数组中
    	transfer(newTable);   // LinkedHashMap对它所调用的transfer方法进行了重写
    
    	table = newTable;
    	threshold = (int)(newCapacity * loadFactor);  // 重新设定 threshold
    }

从上面代码中我们可以看出，Map 扩容操作的核心在于重哈希。所谓重哈希是指重新计算原 HashMap 中的元素在新table 数组中的位置并进行复制处理的过程。鉴于性能和 LinkedHashMap 自身特点的考量，LinkedHashMap 对重哈希过程（transfer方法）进行了重写，源码如下：

void transfer(HashMap.Entry[] newTable) {
    	int newCapacity = newTable.length;
    	// 与HashMap相比，借助于双向链表的特点进行重哈希使得代码更加简洁
    	for (Entry<K,V> e = header.after; e != header; e = e.after) {
    		int index = indexFor(e.hash, newCapacity);   // 计算每个Entry所在的桶
    		// 将其链入桶中的链表
    		e.next = newTable[index];
    		newTable[index] = e;   
    	}
    }

如上述源码所示，LinkedHashMap 借助于自身维护的双向链表轻松地实现了重哈希操作。

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

相对于 LinkedHashMap 的存储而言，读取就显得比较简单了。LinkedHashMap 中重写了 HashMap 中的 get 方法，源码如下：

// LinkedHashMap 中的方法
    public V get(Object key) {
    	// 根据key获取对应的Entry，若没有这样的Entry，则返回null
    	Entry<K,V> e = (Entry<K,V>)getEntry(key); 
    	if (e == null)      // 若不存在这样的Entry，直接返回
    		return null;
    	e.recordAccess(this);
    	return e.value;
    }
    
    // hashMap 中的方法
    final Entry<K,V> getEntry(Object key) {
    	if (size == 0) {
    		return null;
    	}
    
    	int hash = (key == null) ? 0 : hash(key);
    	for (Entry<K,V> e = table[indexFor(hash, table.length)];
    		 e != null;
    		 e = e.next) {
    		Object k;
    		if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
    			return e;
    	}
    	return null;
    }

在 LinkedHashMap 的 get 方法中，通过调用 HashMap 中的 getEntry 方法获取 Entry 对象。注意这里的 recordAccess方法，如果链表中元素的排序规则是按照插入的先后顺序排序的话，该方法什么也不做；如果链表中元素的排序规则是按照访问的先后顺序排序的话，则将 e 移到链表的末尾处，笔者会在后文专门阐述这个问题。

另外，同样地，调用 LinkedHashMap 的 get(Object key) 方法后，若返回值是 NULL，则也存在如下两种可能：

该 key 对应的值就是 null 或者 HashMap 中不存在该 key。

*  ### LinkedHashMap 存取小结 ###

> 1、LinkedHashMap 的存取过程基本与 HashMap 类似，只是在细节实现上稍有不同，这是由 LinkedHashMap 本身的特性所决定的，因为它要额外维护一个双向链表用于保持迭代顺序。
> 
> 2、在 put 操作上，虽然 LinkedHashMap 完全继承了 HashMap 的 put 操作，但是在细节上还是做了一定的调整，比如，在LinkedHashMap 中向哈希表中插入新 Entry 的同时，还会通过 Entry 的 addBefore 方法将其链入到双向链表中。
> 
> 3、在扩容操作上，虽然 LinkedHashMap 完全继承了 HashMap 的 resize 操作，但是鉴于性能和 LinkedHashMap 自身特点的考量，LinkedHashMap 对其中的重哈希过程（transfer方法）进行了重写。在读取操作上，LinkedHashMap 中重写了HashMap 中的 get 方法，通过 HashMap 中的 getEntry 方法获取 Entry 对象，在此基础上，进一步获取指定键对应的值。

--------------------

# 3、LinkedHashMap 与 LRU #

LRU：Least Recently Used，最近最少使用算法。

到此为止，我们已经分析完了 LinkedHashMap 的存取实现，这与 HashMap 大体相同。LinkedHashMap 区别于HashMap 最大的一个不同点是，前者是有序的，而后者是无序的。为此，LinkedHashMap 增加了两个属性用于保证顺序，分别是双向链表头结点 header 和标志位 accessOrder。

我们知道，header 是 LinkedHashMap 所维护的双向链表的头结点，而 accessOrder 用于决定具体的迭代顺序。实际上，accessOrder 标志位的作用可不像我们描述的这样简单，我们接下来仔细分析一波~

我们知道，当 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 方法，但不做任何操作。

## 3.1  put 操作与标志位 accessOrder ##

// 将key/value添加到LinkedHashMap中      
    public V put(K key, V value) {      
    	// 若key为null，则将该键值对添加到table[0]中。      
    	if (key == null)      
    		return putForNullKey(value);      
    	// 若key不为null，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。      
    	int hash = hash(key.hashCode());      
    	int i = indexFor(hash, table.length);      
    	for (Entry<K,V> e = table[i]; e != null; e = e.next) {      
    		Object k;      
    		// 若key对已经存在，则用新的value取代旧的value     
    		if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {      
    			V oldValue = e.value;      
    			e.value = value;      
    			e.recordAccess(this);      
    			return oldValue;      
    		}      
    	}      
    
    	// 若key不存在，则将key/value键值对添加到table中      
    	modCount++;    
    	// 将key/value键值对添加到table[i]处    
    	addEntry(hash, key, value, i);      
    	return null;      
    }

从上述源码我们可以看到，当要 put 进来的 Entry 的 key 在哈希表中已经在存在时，会调用 Entry 的 recordAccess 方法；当该 key 不存在时，则会调用 addEntry 方法将新的 Entry 插入到对应桶的单链表的头部。我们先来看 recordAccess 方法：

void recordAccess(HashMap<K,V> m) {  
    	LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;  
    	// 如果链表中元素按照访问顺序排序，则将当前访问的Entry移到双向循环链表的尾部，  
    	// 如果是按照插入的先后顺序排序，则不做任何事情。  
    	if (lm.accessOrder) {  
    		lm.modCount++;  
    		// 移除当前访问的Entry  
    		remove();  
    		// 将当前访问的Entry插入到链表的尾部  
    		addBefore(lm.header);  
    	}  
    }

LinkedHashMap 重写了 HashMap 中的 recordAccess 方法（HashMap中该方法为空），当调用父类的 put 方法时，在发现 key 已经存在时，会调用该方法；当调用自己的 get 方法时，也会调用到该方法。

**该方法提供了 LRU 算法的实现，它将最近使用的 Entry 放到双向循环链表的尾部**。也就是说，**当 accessOrder 为 true 时，get 方法和 put 方法都会调用 recordAccess 方法使得最近使用的Entry移到双向链表的末尾**；当 accessOrder 为默认值false 时，从源码中可以看出 recordAccess 方法什么也不会做。我们反过头来，再看一下 addEntry 方法：

// LinkedHashMap中的addEntry方法  
    void addEntry(int hash, K key, V value, int bucketIndex) {
    	// 创建新的Entry，并插入到LinkedHashMap中  
    	createEntry(hash, key, value, bucketIndex);  // 重写了HashMap中的createEntry方法
    
    	// 双向链表的第一个有效节点（header后的那个节点）为最近最少使用的节点，这是用来支持LRU算法的
    	Entry<K,V> eldest = header.after;  
    	// 如果有必要，则删除掉该近期最少使用的节点，  
    	// 这要看对removeEldestEntry的覆写,由于默认为false，因此默认是不做任何处理的。  
    	if (removeEldestEntry(eldest)) {  
    		removeEntryForKey(eldest.key);  
    	} else {  
    		// 扩容到原来的2倍  
    		if (size >= threshold)  
    			resize(2 * table.length);  
    	}  
    }
    
    // LinkedHashMap中的createEntry方法
    void createEntry(int hash, K key, V value, int bucketIndex) { 
    	// 向哈希表中插入Entry，这点与HashMap中相同 
    	// 创建新的Entry并将其链入到数组对应桶的链表的头结点处， 
    	HashMap.Entry<K,V> old = table[bucketIndex];  
    	Entry<K,V> e = new Entry<K,V>(hash, key, value, old);  
    	table[bucketIndex] = e;     
    
    	// 在每次向哈希表插入Entry的同时，都会将其插入到双向链表的尾部，  
    	// 这样就按照Entry插入LinkedHashMap的先后顺序来迭代元素(LinkedHashMap根据双向链表重写了迭代器)
    	// 同时，新put进来的Entry是最近访问的Entry，把其放在链表末尾 ，也符合LRU算法的实现  
    	e.addBefore(header);  
    	size++;  
    }

同样是将新的 Entry 链入到 table 中对应桶中的单链表中，但可以在 createEntry 方法中看出，同时也会把新 put 进来的 Entry 插入到了双向链表的尾部。

从插入顺序的层面来说，新的 Entry 插入到双向链表的尾部可以实现按照插入的先后顺序来迭代 Entry，而从访问顺序的层面来说，新 put 进来的 Entry 又是最近访问的 Entry，也应该将其放在双向链表的尾部。在上面的 addEntry 方法中还调用了 removeEldestEntry 方法，该方法源码如下：

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

该方法是用来被重写的，一般地，如果用 LinkedHashMap 实现 LRU 算法，就要重写该方法。比如可以将该方法覆写为如果设定的内存已满，则返回 true，这样当再次向 LinkedHashMap 中 putEntry 时，在调用的 addEntry 方法中便会将近期最少使用的节点删除掉（header后的那个节点）。在第七节，笔者便重写了该方法并实现了一个名副其实的 LRU 结构。

## 3.2  get 操作与标志位 accessOrder ##

public V get(Object key) {
    	// 根据key获取对应的Entry，若没有这样的Entry，则返回null
    	Entry<K,V> e = (Entry<K,V>)getEntry(key); 
    	if (e == null)      // 若不存在这样的Entry，直接返回
    		return null;
    	e.recordAccess(this);
    	return e.value;
    }

在 LinkedHashMap 中进行读取操作时，一样也会调用 recordAccess 方法。上面笔者已经表述的很清楚了，此不赘述。

## 3.3  LinkedListMap 与 LRU 小结 ##

使用 LinkedHashMap 实现 LRU 的必要前提是将 accessOrder 标志位设为 true 以便开启按访问顺序排序的模式。我们可以看到，无论是 put 方法还是 get 方法，都会导致目标 Entry 成为最近访问的 Entry，因此就把该 Entry 加入到了双向链表的末尾：get 方法通过调用 recordAccess 方法来实现。

put 方法在覆盖已有 key 的情况下，也是通过调用 recordAccess 方法来实现，在插入新的 Entry 时，则是通过createEntry 中的 addBefore 方法来实现。这样，我们便把最近使用的 Entry 放入到了双向链表的后面。多次操作后，双向链表前面的 Entry 便是最近没有使用的，这样当节点个数满的时候，删除最前面的 Entry（head后面的那个Entry）即可，因为它就是最近最少使用的 Entry。

--------------------

# 4、使用 LinkedHashMap 实现 LRU 算法 #

如下所示，笔者使用 LinkedHashMap 实现一个符合 LRU 算法的数据结构，该结构最多可以缓存 6 个元素，但元素多于 6 个时，会自动删除最近最久没有被使用的元素，如下所示：

package com.zju.lru;
    
    import java.util.LinkedHashMap;
    import java.util.Map;
    
    /**
     * 模拟LRU算法
     */
    public class LRU<K,V> extends LinkedHashMap<K, V> implements Map<K,V> {
    
    	private static final long serialVersionUID = 1L;
    	
    	public LRU(int initialCapacity, float loadFactor, boolean accessOrder){
    		super(initialCapacity, loadFactor, accessOrder);
    	}
    	
    	// 重写LinkdHashMap中的removeEldestEntry方法，当LRU中元素多于6个时，删除最不经常使用的元素
    	@Override
    	public boolean removeEldestEntry(Map.Entry<K, V> eldest){
    		if(size() > 6){
    			return true;
    		}
    		return false;
    	}
    	
    	// 测试
    	public static void main(String[] args) {
    		LRU<Character, Integer> lru = new LRU<Character, Integer>(16, 0.75f, true);
    		
    		String str = "abcdefghijkl";
    		
    		for (int i = 0; i < str.length(); i++) {
    			lru.put(str.charAt(i), i);    //key:str.charAt(i)  value:i
    		}
    
    		System.out.println("LRU中key为h的Entry的值为：" + lru.get('h'));
    		System.out.println("LRU的大小：" + lru.size());
    		System.out.println("LRU：" + lru);
    	}
    }

*  运行结果

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 7][]

--------------------

# 5、LinkedHashMap 有序性原来分析 #

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

private abstract class LinkedHashIterator<T> implements Iterator<T> {
    	Entry<K,V> nextEntry = header.after;
    	Entry<K,V> lastReturned = null;
    
    	int expectedModCount = modCount;
    	
    	// 根据双向列表判断
    	public boolean hasNext() {          
    			return nextEntry != header;
    	}
    
    	public void remove() {
    		if (lastReturned == null)
    		throw new IllegalStateException();
    		if (modCount != expectedModCount)
    		throw new ConcurrentModificationException();
    
    			LinkedHashMap.this.remove(lastReturned.key);
    			lastReturned = null;
    			expectedModCount = modCount;
    	}
    
    	// 迭代输出双向链表各节点
    	Entry<K,V> nextEntry() {        
    		if (modCount != expectedModCount)
    		throw new ConcurrentModificationException();
    			if (nextEntry == header)
    				throw new NoSuchElementException();
    
    			Entry<K,V> e = lastReturned = nextEntry;
    			nextEntry = e.after;
    			return e;
    	}
    }
    
    // Key 迭代器，KeySet
    private class KeyIterator extends LinkedHashIterator<K> {   
    	public K next() { return nextEntry().getKey(); }
    }
    
    // Value 迭代器，Values(Collection)
    private class ValueIterator extends LinkedHashIterator<V> {
    	public V next() { return nextEntry().value; }
    }
    
    // Entry 迭代器，EntrySet
    private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
    	public Map.Entry<K,V> next() { return nextEntry(); }
    }

从上述代码中我们可以知道，LinkedHashMap 重写了 HashMap 的迭代器，它使用其维护的双向链表进行迭代输出。

--------------------

# 6、LinkedHashMap 【JDK1.8】 #

原文是基于 JDK1.6 的实现，实际上 JDK1.8 对其进行了改动。 首先它删除了addEntry，createEnrty等方法（事实上是hashMap 的改动影响了它而已）。

LinkedHashMap 同样使用了大部分 HashMap 的增删改查方法。 新版本 LinkedHashMap 主要是通过对 HashMap 内置几个方法重写来实现 LRU 的。

**HashMap 不提供实现：**

void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }

**LinkedHashMap 的实现：**

*  处理元素被访问后的情况：

void afterNodeAccess(Node<K,V> e) { // move node to last
    	LinkedHashMap.Entry<K,V> last;
    	if (accessOrder && (last = tail) != e) {
    		LinkedHashMap.Entry<K,V> p =
    			(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    		p.after = null;
    		if (b == null)
    			head = a;
    		else
    			b.after = a;
    		if (a != null)
    			a.before = b;
    		else
    			last = b;
    		if (last == null)
    			head = p;
    		else {
    			p.before = last;
    			last.after = p;
    		}
    		tail = p;
    		++modCount;
    	}
    }

*  处理元素插入后的情况：

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    	LinkedHashMap.Entry<K,V> first;
    	if (evict && (first = head) != null && removeEldestEntry(first)) {
    		K key = first.key;
    		removeNode(hash(key), key, null, false, true);
    }

*  处理元素被删除后的情况：

void afterNodeRemoval(Node<K,V> e) { // unlink
    	LinkedHashMap.Entry<K,V> p =
    		(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    	p.before = p.after = null;
    	if (b == null)
    		head = a;
    	else
    		b.after = a;
    	if (a == null)
    		tail = b;
    	else
    		a.before = b;
    }

另外 JDK1.8 的 HashMap 在链表长度超过 8 时自动转为红黑树，会按顺序插入链表中的元素，可以自定义比较器来定义节点的插入顺序。

JDK1.8 的 LinkedHashMap 同样会使用这一特性，当变为红黑树以后，节点的先后顺序同样是插入红黑树的顺序，其双向链表的性质没有改变，只是原来 HashMap 的链表变成了红黑树而已，在此不要混淆。

--------------------

# 7、总结 #

本文从 LinkedHashMap 的数据结构，以及源码分析，到最后的 LRU 缓存实现，比较深入地剖析了 LinkedHashMap 的底层原理。

总结以下几点：

1、LinkedHashMap 在 HashMap 的数组加链表结构的基础上，将所有节点连成了一个双向链表。

2、当主动传入的 accessOrder 参数为 false 时, 使用 put 方法时，新加入元素不会被加入双向链表，get 方法使用时也不会把元素放到双向链表尾部。

3、当主动传入的 accessOrder 参数为 true 时，使用 put 方法新加入的元素，如果遇到了哈希冲突，并且对 key 值相同的元素进行了替换，就会被放在双向链表的尾部，当元素超过上限且 removeEldestEntry 方法返回 true 时，直接删除最早元素以便新元素插入。如果没有冲突直接放入，同样加入到链表尾部。使用 get 方法时会把 get 到的元素放入双向链表尾部。

4、LinkedHashMap 的扩容比 HashMap 来的方便，因为 HashMap 需要将原来的每个链表的元素分别在新数组进行反向插入链化，而 LinkedHashMap 的元素都连在一个链表上，可以直接迭代然后插入。

5 LinkedHashMap 的 removeEldestEntry 方法默认返回 false，要实现 LRU 很重要的一点就是集合满时要将最久未访问的元素删除，在 LinkedHashMap 中这个元素就是头指针指向的元素。实现 LRU 可以直接实现继承 LinkedHashMap 并重写removeEldestEntry 方法来设置缓存大小。JDK 中实现了 LRUCache 也可以直接使用。

--------------------

## 全文完！ ##

[https_blog.csdn.net_a724888_article_details_80290276]: https://blog.csdn.net/a724888/article/details/80290276
[HashMap]: https://blog.csdn.net/pcwl1206/article/details/86497373
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220326/c3db09470edc432b91b836ea77b38b46.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20220326/e1f2d0c6cdbe43f5b095004462652d0d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2]: /images/20220326/ae00466d7d884213b496b5ff620cbcda.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 3]: /images/20220326/f3b56a09d80643cc9dccce6d3e3514dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 4]: /images/20220326/1dbcb3b46aa447f3acd5f5e759d2d00a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 5]: /images/20220326/f4a0a4b62f814328ba7413f45e8d9e46.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 6]: /images/20220326/2fe1113831814eeba13a440526c17bd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 7]: /images/20220326/c0d55e412f57455885b0689b617228fd.png