Map 类型的集合类是通过 put(K,V) 方法插入键值对,LinkedHashMap 本身并没有覆写父类的 put 方法,而是直接使用了父类的实现。但在 HashMap 中,put 方法插入的是 HashMap 内部类 Node 类型的节点,该类型的节点并不具备与 LinkedHashMap 内部类 Entry 及其子类型节点组成链表的能力。那么,LinkedHashMap 是怎样建立链表的呢?在展开说明之前,我们先看一下 LinkedHashMap 插入操作相关的代码:
// HashMap 中实现 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } // HashMap 中实现 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) {...} // 通过节点 hash 定位节点所在的桶位置,并检测桶中是否包含节点引用 if ((p = tab[i = (n - 1) & hash]) == null) {...} else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) {...} else { // 遍历链表,并统计链表长度 for (int binCount = 0; ; ++binCount) { // 未在单链表中找到要插入的节点,将新节点接在单链表的后面 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) {...} break; } // 插入的节点已经存在于单链表中 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) {...} afterNodeAccess(e); // 回调方法,后续说明 return oldValue; } } ++modCount; if (++size > threshold) {...} afterNodeInsertion(evict); // 回调方法,后续说明 return null; } // HashMap 中实现 Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next); } // LinkedHashMap 中覆写 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); // 将 Entry 接在双向链表的尾部 linkNodeLast(p); return p; } // LinkedHashMap 中实现 private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { LinkedHashMap.Entry<K,V> last = tail; tail = p; // last 为 null,表明链表还未建立 if (last == null) head = p; else { // 将新节点 p 接在链表尾部 p.before = last; last.after = p; } }