Java容器（五）：LinkedHashMap实现原理

我会带着你远行 2022-05-16 03:28 103阅读 0赞

从之前的LinkedList源码分析来看，带有Linked的，其实就是和双链表相关，毫无疑问，LinkedHashMap就是HashMap再多加一个双向链表，其内部的**存储规则**和HashMap是一样的，但是在迭代中，**HashMap是无序的，LinkedHashMap是有序的**   
　　LinkedHashMap维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）。

# **一、LinkedHashMap的数据结构** #

<code>public class LinkedHashMap<K,V>
 extends HashMap<K,V>
 implements Map<K,V></code>

LinkedHashMap继承自HashMap，因此继承了HashMap的成员变量等

<code>//header是双链表的头结点
 private transient Entry<K,V> header; 
 //accessOrder为true时，按访问顺序排序，false时，按插入顺序排序
 private final boolean accessOrder; </code>

LinkedHashMap中有两个特有的成员变量 — header和accessOrder，接下来会讲到

<code>public LinkedHashMap(int initialCapacity, float loadFactor) {
 super(initialCapacity, loadFactor);
 accessOrder = false;
 }</code>

LinkedHashMap共有五个构造方法，每一个方法都是调用父类HashMap的构造方法，并且accessOrder都为false，也就是默认按插入顺序排序

### **LinkedHashMap的数据结构** ###

![这里写图片描述][SouthEast]

图中，有两个比较特殊的变量，after和before，他们是Entry引用，before指向当前节点的前一个节点，after指向当前节点的后一个节点（注意绿线）   
　　LinkedHashMap中，覆盖了Entry内部类，在原来的Entry的实现上，增加了before和after，这就是双联链表的前引用和后引用，并增加了addBefore和remove等重要方法

<code> 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);
 }
 
 /**
 * Removes this entry from the linked list.
 */
 private void remove() {
 before.after = after;
 after.before = before;
 }
 
 /**
 * Inserts this entry before the specified existing entry in the list.
 */
 private void addBefore(Entry<K,V> existingEntry) {
 after = existingEntry;
 before = existingEntry.before;
 before.after = this;
 after.before = this;
 }</code>

# **二、LinkedHashMap的存储实现** #

在HashMap中，存储实现的流程是这样的：   
　　put() -> addEntry() -> createEntry()   
　　put()中计算当前key的hash值所在的哈希表的索引位置，并在createEntry()中完成key-value节点在该索引位置的插入

而在LinkedHashMap中，**覆盖了addEntry() 和 createEntry()方法的实现，而没有覆盖put方法**，因此这就证明了LinkedHashMap的存储规则是和HashMap一样的   
　　我们来看看addEntry() 和 createEntry()方法

<code> void addEntry(int hash, K key, V value, int bucketIndex) {
 //调用HashMap的addEntry()
 super.addEntry(hash, key, value, bucketIndex);
 
 // Remove eldest entry if instructed
 Entry<K,V> eldest = header.after;
 if (removeEldestEntry(eldest)) {
 removeEntryForKey(eldest.key);
 }
 }
 
 
 void createEntry(int hash, K key, V value, int bucketIndex) {
 HashMap.Entry<K,V> old = table[bucketIndex];
 Entry<K,V> e = new Entry<>(hash, key, value, old);
 table[bucketIndex] = e;
 //addBefore，其他都和HashMap的createEntry相关
 e.addBefore(header);
 size++;
 }</code>

从上面的代码看，LinkedHashMap和HashMap中，addEntry() 和 createEntry()的实现差不多，而LinkedHashMap多调用了一个新增的addBefore方法，这是LinkedHashMap存储排序最关键的地方

<code> /**
 * 将当前节点插入到existingEntry的前面
 */
 private void addBefore(Entry<K,V> existingEntry) {
 after = existingEntry;
 before = existingEntry.before;
 before.after = this;
 after.before = this;
 }</code>

通过addBefore，这样便形成了一个双线链表   
　　![这里写图片描述][SouthEast 1]

# **三、HashMap和LinkedHashMap遍历** #

首先来看HashMap的遍历，HashMap的核心代码如下：

<code> private abstract class HashIterator<E> implements Iterator<E> {
 Entry<K,V> next; // next entry to return
 int expectedModCount; // For fast-fail
 int index; // current slot
 Entry<K,V> current; // current entry
 
 //当调用keySet().iterator()时，调用此代码
 HashIterator() {
 expectedModCount = modCount;
 if (size > 0) { // advance to first entry
 Entry[] t = table;
 //从哈希表数组从上到下，查找第一个不为null的节点，并把next引用指向该节点
 while (index < t.length && (next = t[index++]) == null)
 ;
 }
 }
 
 public final boolean hasNext() {
 return next != null;
 }
 
 //当调用next时，会调用此代码
 final Entry<K,V> nextEntry() {
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 Entry<K,V> e = next;
 if (e == null)
 throw new NoSuchElementException();
 
 //如果当前节点的下一个节点为null，从节点处罚往下查找哈希表，找到第一个不为null的节点
 if ((next = e.next) == null) {
 Entry[] t = table;
 while (index < t.length && (next = t[index++]) == null)
 ;
 }
 current = e;
 return e;
 }
 
 public void remove() {
 if (current == null)
 throw new IllegalStateException();
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 Object k = current.key;
 current = null;
 HashMap.this.removeEntryForKey(k);
 expectedModCount = modCount;
 }
 }</code>

从这里可以看出，HashMap遍历时，按哈希表的每一个索引的链表从上往下遍历，由于HashMap的存储规则，最晚添加的节点都有可能在第一个索引的链表中，这就造成了HashMap的遍历时无序的。

然后来看LinkedHashMap的遍历：

# **四、总结** #

可见LinkedHashMap的实现原理还是比较简单的，而且LinkedHashSet的内部完全就是通过LinkedHashMap来实现的

[SouthEast]: /images/20220516/7cb4e9e367cf414b9b4fbd6e5c55c4cc.png
[SouthEast 1]: /images/20220516/500698c5bea646f9abbaa9f03fa9a1ac.png