JDK源码分析（6）之 LinkedHashMap 相关

LinkedHashMap实质是HashMap+LinkedList，提供了顺序访问的功能；所以在看这篇博客之前最好先看一下我之前的两篇博客，HashMap 相关 和 LinkedList 相关；

一、整体结构 1. 定义 public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {}

从上述定义中也能看到LinkedHashMap其实就是继承了HashMap，并加了双向链表记录顺序，代码和结构本身不难，但是其中结构的组织，代码复用这些地方十分值得我们学习；具体结构如图所示：

2. 构造函数和成员变量 public LinkedHashMap(int initialCapacity, float loadFactor) {} public LinkedHashMap(int initialCapacity) {} public LinkedHashMap() {} public LinkedHashMap(Map<? extends K, ? extends V> m) {} public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {} /** * The iteration ordering method for this linked hash map: <tt>true</tt> * for access-order, <tt>false</tt> for insertion-order. * @serial */ final boolean accessOrder;

可以看到LinkedHashMap的5个构造函数和HashMap的作用基本是一样的，都是初始化initialCapacity和loadFactor，但是多了一个accessOrder，这也是LinkedHashMap最重要的一个成员变量了；

当accessOrder为true的时候，表示LinkedHashMap中记录的是访问顺序，也是就没放get一个元素的时候，这个元素就会被移到链表的尾部；

当accessOrder为false的时候，表示LinkedHashMap中记录的是插入顺序；

3. Entry关系

扎眼一看可能会觉得HashMap体系的节点继承关系比较混乱；一所以这样设计因为

LinkedHashMap继承至HashMap，其中的节点同样有普通节点和树节点两种；并且树节点很少使用；

现在的设计中，树节点是可以完全复用的，但是HashMap的树节点，会浪费双向链表的能力；

如果不这样设计，则至少需要两条继承关系，并且需要抽出双向链表的能力，整个继承体系以及方法的复用会变得非常复杂，不利于扩展；

二、重要方法

上面我们已经讲了LinkedHashMap就是HashMap+链表，所以我们只需要在结构有可能改变的地方加上链表的修改就可以了，结构可能改变的地方只要有put/get/replace，这里需要注意扩容的时候虽然结构改变了，但是节点的顺序仍然保持不变，所以扩容可以完全复用；

1. put 方法

未找到key时，直接在最后添加一个节点

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); linkNodeLast(p); return p; } TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next); linkNodeLast(p); return p; } private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { LinkedHashMap.Entry<K,V> last = tail; tail = p; if (last == null) head = p; else { p.before = last; last.after = p; } }

上面代码很简单，但是很清晰的将添加节点到最后的逻辑抽离的出来；

找到key，则替换value，这部分需要联系 HashMap 相关 中的put方法部分；

// HashMap.putVal ... // 如果找到key if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } // 如果没有找到key ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; ...

在之前的HashMap源码分析当中可以看到有几个空的方法

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

这三个就是用来调整链表位置的事件方法，可以看到HashMap.putVal中就使用了两个，

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