前言

LinkedHashMap继承于HshMap，维护了一条双向链表，解决了遍历顺序和插入顺序问题。

原理

LinkedHashMap继承于HashMap，所以底层还是数组+链表）+红黑树结构。每次的数据插入操作，都会附带上前后指针，形成一条有序链路。

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

LinkedHashMap

相比较于HashMap对应的多了以下参数。

  1. /**
  2.  * The head (eldest) of the doubly linked list. 头结点
  3.  */
  4. transient LinkedHashMap.Entry<K,V> head;
  6. /**
  7.  * The tail (youngest) of the doubly linked list. 尾结点
  8.  */
  9. transient LinkedHashMap.Entry<K,V> tail;
  11. /**
  12.  * The iteration ordering method for this linked hash map: <tt>true</tt>
  13.  * for access-order, <tt>false</tt> for insertion-order.
  14.  * true：访问顺序；false：插入顺序
  15.  */
  16. final boolean accessOrder;

Entry

带有前后节点

  1. static class Entry<K,V> extends HashMap.Node<K,V> {
  2.     Entry<K,V> before, after;
  3.     Entry(int hash, K key, V value, Node<K,V> next) {
  4.         super(hash, key, value, next);
  5.     }
  6. }

Put

put还是复用的HashMap方法，但是重写了newNode方法。每次插入的新节点，都带有before和after的前后引用。

  1. //HashMap
  2. public V put(K key, V value) {
  3.     return putVal(hash(key), key, value, false, true);
  4. }
  5. //HashMap
  6. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  7.                boolean evict) {
  8.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  9.     if ((tab = table) == null || (n = tab.length) == 0)
  10.         n = (tab = resize()).length;
  11.     if ((p = tab[i = (n - 1) & hash]) == null)
  12.         //override
  13.         tab[i] = newNode(hash, key, value, null);
  14.     else {
  15.        ...
  16. }
  17. //LinkedHashMap
  18. Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
  19.     LinkedHashMap.Entry<K,V> p =
  20.         new LinkedHashMap.Entry<K,V>(hash, key, value, e);
  21.     linkNodeLast(p);
  22.     return p;
  23. }
  25. // link at the end of list
  26. private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
  27.     LinkedHashMap.Entry<K,V> last = tail;
  28.     //设置tail节点是新元素
  29.     tail = p;
  30.     if (last == null)
  31.         //tail节点为空时，头结点也为空，设置下head节点
  32.         head = p;
  33.     else {
  34.         //存在尾结点时，进行设置前后节点
  35.         p.before = last;
  36.         last.after = p;
  37.     }
  38. }

Remove

删除方法也是复用的HashMap的，数据的删除都是和HashMap一样的，最后删除完了后，修改下节点的引用关系。

  1. //HashMap
  2. public V remove(Object key) {
  3.     Node<K,V> e;
  4.     return (e = removeNode(hash(key), key, null, false, true)) == null ?
  5.         null : e.value;
  6. }
  7. final Node<K,V> removeNode(int hash, Object key, Object value,
  8.                            boolean matchValue, boolean movable) {
  9.         ...    
  10.         if (node != null && (!matchValue || (v = node.value) == value ||
  11.                              (value != null && value.equals(v)))) {
  12.             if (node instanceof TreeNode)
  13.                 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
  14.             else if (node == p)
  15.                 tab[index] = node.next;
  16.             else
  17.                 p.next = node.next;
  18.             ++modCount;
  19.             --size;
  20.             //override
  21.             afterNodeRemoval(node);
  22.             return node;
  23.         }
  24. }
  25. //LinkedHashMap
  26. void afterNodeRemoval(Node<K,V> e) { // unlink
  27.     LinkedHashMap.Entry<K,V> p =
  28.         (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  29.     //删除节点before，after置为空
  30.     p.before = p.after = null;
  31.     //头结点处理
  32.     if (b == null)
  33.         head = a;
  34.     else
  35.         b.after = a;
  36.     //尾结点处理
  37.     if (a == null)
  38.         tail = b;
  39.     else
  40.         a.before = b;
  41. }

Get

LinkedHashMap默认是按照插入顺序排序的，指定accessOrder=true，就按照访问顺序。方法还是复用的HashMap方法，调用get/getOrDefault/replace时，将节点移动到链表尾部。

  1. //LinedHashMap
  2. public V get(Object key) {
  3.     Node<K,V> e;
  4.     if ((e = getNode(hash(key), key)) == null)
  5.         return null;
  6.     if (accessOrder)
  7.         //访问顺序排序
  8.         afterNodeAccess(e);
  9.     return e.value;
  10. }
  12. void afterNodeAccess(Node<K,V> e) { // move node to last
  13.     LinkedHashMap.Entry<K,V> last;
  14.     if (accessOrder && (last = tail) != e) {
  15.         LinkedHashMap.Entry<K,V> p =
  16.             (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  17.         //前节点置空
  18.         p.after = null;
  19.         if (b == null)
  20.             head = a;
  21.         else
  22.             //after节点修改下一指向
  23.             b.after = a;
  24.         if (a != null)
  25.             //before节点修改前一指向
  26.             a.before = b;
  27.         else
  28.             last = b;
  29.         if (last == null)
  30.             head = p;
  31.         else {
  32.             p.before = last;
  33.             last.after = p;
  34.         }
  35.         //设置为尾部节点
  36.         tail = p;
  37.         ++modCount;
  38.     }
  39. }

缓存

当LinkedHashMap操作任何put方法后，都会触发一个字方法回调，这里可以做额外的处理。

  1. void afterNodeInsertion(boolean evict) { // possibly remove eldest
  2.     LinkedHashMap.Entry<K,V> first;
  3.     //evict 是否删除；
  4.     if (evict && (first = head) != null && removeEldestEntry(first)) {
  5.         K key = first.key;
  6.         //移除节点
  7.         removeNode(hash(key), key, null, false, true);
  8.     }
  9. }
  10. //是否移除最早的节点
  11. protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
  12.     return false;
  13. }

有了这个，可以实现removeEldestEntry 方法，当put元素时，会根据覆盖的方法来控制长度。

参考