Map之LinkedHashMap源码实现

约定不等于承诺〃 2022-05-03 23:50 313阅读 0赞

一、引言

1.回顾

1.1 HashMap的是怎么保证添加的元素的索引的（也就是说哈希桶是如何分布的）？

首先通过hash()方法:实现高位和低位进行充分位运算；然后通过 “table的长度” & “hash值”，计算得出其bucket值。

1.2 HashMap的扩容的流程是怎么样的？

把resize()的各种情况梳理一遍。值得注意的是：HashMap的的初始化操作也移到了resize方法中了。

1.3 1.8比1.7版本在HashMap的那些方面做了改动和优化？

最主要的是引入了红黑树对长链表进行了优化。其他的包括但不限于初始化的时机、扩容机制的微调等等。

2.要点


























要点 说明
是否可以为空 key和value都可以为空，但是key只能一个为空，value则不限
是否有序 有序。在继承HashMap的基础上，通过一个链表来维持顺序
是否可以重复 key重复会覆盖，value则可以重复
是否线程安全 非线程安全

二、分析

1.继承关系结构图

在这里插入图片描述
说明：LinkedHashMap是HashMap的子类。只是重写了其中维持顺序的列表的相关的操作。如下图所示：
在这里插入图片描述

LinkedHashMap:
在这里插入图片描述

2.原理

2.1 图示

HashMap的存储方式：
在这里插入图片描述
有顺序的HashMap的存储方式（即LinkedHashMap）:多了一个双向列表来维护顺序
在这里插入图片描述

2.2 说明

LinkedHashMap的Entry结构：

  1. /**
  2.      * HashMap.Node subclass for normal LinkedHashMap entries.
  3.      * LinkedHashMap的entry在hashmap的基础上多了before和after两个地址，依次来维护顺序。这点和LinkedList一致.
  4.      */
  5.     static class Entry<K,V> extends HashMap.Node<K,V> {
  6.         Entry<K,V> before, after;
  7.         Entry(int hash, K key, V value, Node<K,V> next) {
  8.             super(hash, key, value, next);
  9.         }
  10.     }

3.字段

  1. /**
  2.      * The head (eldest) of the doubly linked list.
  3.      * 链表的头结点
  4.      */
  5.     transient LinkedHashMap.Entry<K,V> head;
  7.     /**
  8.      * The tail (youngest) of the doubly linked list.
  9.      * 链表的尾结点
  10.      */
  11.     transient LinkedHashMap.Entry<K,V> tail;
  13.     /**
  14.      * The iteration ordering method for this linked hash map: <tt>true</tt>
  15.      * for access-order, <tt>false</tt> for insertion-order.
  16.      * LRU算法相关
  17.      * @serial
  18.      */
  19.     final boolean accessOrder;

4.方法

4.1构造方法

  1. public LinkedHashMap() {
  2.         super();
  3.         accessOrder = false; // 是否开启LRU缓冲
  4.     }
  6.     public LinkedHashMap(int initialCapacity) {
  7.         super(initialCapacity);
  8.         accessOrder = false; // 是否开启LRU缓冲
  9.     }
  11.     public LinkedHashMap(int initialCapacity, float loadFactor) {
  12.         super(initialCapacity, loadFactor);
  13.         accessOrder = false; // 是否开启LRU缓冲
  14.     }
  16.     public LinkedHashMap(Map<? extends K, ? extends V> m) {
  17.         super();
  18.         accessOrder = false; // 是否开启LRU缓冲
  19.         putMapEntries(m, false);
  20.     }

4.2 方法

4.2.1 存储：put方法
  1. public V put(K key, V value) {
  2.         return putVal(hash(key), key, value, false, true);
  3.     }
  5. // 说明：在这里再次强调一遍：evict参数用于LinkedHashMap中的尾部操作，这里没有实际意义。
  6. // onlyIfAbsent参数用于是否覆盖相同key下的value值
  7. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  8.                    boolean evict) {
  9.         Node<K,V>[] tab; Node<K,V> p; int n, i;
  10.         if ((tab = table) == null || (n = tab.length) == 0)
  11.             n = (tab = resize()).length;
  12.         if ((p = tab[i = (n - 1) & hash]) == null)
  13.             // 这里调用的是LinkedHashMap的newNode()方法。
  14.             // 如果理解多态的：这点应该很容易理解
  15.             tab[i] = newNode(hash, key, value, null);
  16.         else {
  17.             Node<K,V> e; K k;
  18.             if (p.hash == hash &&
  19.                 ((k = p.key) == key || (key != null && key.equals(k))))
  20.                 e = p;
  21.             else if (p instanceof TreeNode)
  22.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  23.             else {
  24.                 for (int binCount = 0; ; ++binCount) {
  25.                     if ((e = p.next) == null) {
  26.                         // 同上
  27.                         p.next = newNode(hash, key, value, null);
  28.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  29.                             treeifyBin(tab, hash);
  30.                         break;
  31.                     }
  32.                     if (e.hash == hash &&
  33.                         ((k = e.key) == key || (key != null && key.equals(k))))
  34.                         break;
  35.                     p = e;
  36.                 }
  37.             }
  38.             if (e != null) { // existing mapping for key
  39.                 V oldValue = e.value;
  40.                 if (!onlyIfAbsent || oldValue == null)
  41.                     e.value = value;
  42.                // 由LinkedHashMap的实现，并调用
  43.                // 作用：
  44.                 afterNodeAccess(e);
  45.                 return oldValue;
  46.             }
  47.         }
  48.         ++modCount;
  49.         if (++size > threshold)
  50.             resize();
  51.         // 由LinkedHashMap的实现，并调用
  52.         // 作用：在执行一次插入操作都会执行的操作
  53.         // 主要就是对LRU算法的支持。
  54.         // 是否移动最早的元素。但是LinkedHashMap中总是返回false.所以在这里没什么用。
  55.         afterNodeInsertion(evict);
  56.         return null;
  57.     }
  59.     Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
  60.         LinkedHashMap.Entry<K,V> p =
  61.             new LinkedHashMap.Entry<K,V>(hash, key, value, e);
  62.         // 作用：将新建的节点添加到维护的双向链表上去
  63.         // 方式：往链表的尾部进行添加
  64.         linkNodeLast(p);
  65.         return p;
  66.     }
  68.     // link at the end of list
  69.     private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
  70.         LinkedHashMap.Entry<K,V> last = tail;
  71.        // p为新的需要追加的结点
  72.         tail = p;
  73.         // 如果last为null.则表示现在链表为空。新new出来的p元素就是链表的头结点
  74.         if (last == null)
  75.             head = p;
  76.         else {
  77.         // 否则就是链表中已存在结点的情况：往尾部添加即可
  78.             // 把新追加p的结点的前驱结点设置之前的尾部结点
  79.             // 把之前的尾部结点的后驱结点设为新追加的p结点
  80.             p.before = last;
  81.             last.after = p;
  82.         }
  83.     }

由此可见：LinkedHashMap的在新建一个结点的时候，做了两件事：1.新建结点，并放入到对应的hash桶位置。2.将新建的结点追加到双向链表的尾部。

  1. void afterNodeInsertion(boolean evict) { // possibly remove eldest
  2.         LinkedHashMap.Entry<K,V> first;
  3.         // 此方法在LinkedHashMap中总是执行不到。原因见下面。
  4.         if (evict && (first = head) != null && removeEldestEntry(first)) {
  5.             K key = first.key;
  6.             removeNode(hash(key), key, null, false, true);
  7.         }
  8.     }
  10.     // 总是返回false,所有上面的方法总是执行不到
  11.     protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
  12.         return false;
  13.     }

下面我们我们看一下添加时候的另外一种情况：既不是新建结点、也不是放入到hash桶的位置。而是放到链表或红黑树的情况：

  1. // 作用：将结点元素移到链表的最后位置
  2.     void afterNodeAccess(Node<K,V> e) { // move node to last
  3.         LinkedHashMap.Entry<K,V> last;
  4.         // 根据LRU原则，只有当元素不在尾部的时候，才需要进行以为操作
  5.         // 需要move的e结点有以下几种情况：
  6.         // ①e结点没有前驱结点，有后驱结点情况下：将头结点设为e的后驱结点，然后把e的后驱结点的前驱结点“连接”到e的前驱结点的前驱结点上（这时候为null）。最后把p设为tail结点，置于尾部。
  7.         // ②e结点没有后驱结点，有前驱结点情况下：将e结点的前驱结点和后驱结点（null）直接相连；并把last结点设为e的前驱结点。最后将p(即e)结点设为tail结点，置于尾部。
  8.         // ③链表为空情况下：直接将当前结点p，置为链表的head结点。
  9.         // ④e结点既有前驱结点，也有后驱结点情况下：将p结点的前驱结点和后驱结点直接相连。然后把p结点方法最后一个结点。同时将tail结点赋值为p.
  10.         if (accessOrder && (last = tail) != e) {
  11.             LinkedHashMap.Entry<K,V> p =
  12.                 (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  13.             p.after = null;
  14.             if (b == null)
  15.                 head = a;
  16.             else
  17.                 b.after = a;
  18.             if (a != null)
  19.                 a.before = b;
  20.             else
  21.                 last = b;
  22.             if (last == null)
  23.                 head = p;
  24.             else {
  25.                 p.before = last;
  26.                 last.after = p;
  27.             }
  28.             tail = p;
  29.             ++modCount;
  30.         }
  31.     }
4.2.2 获取：get方法
  1. // 说明：调用HashMap的get逻辑；如果获取值为null，则直接返回null。否则判断是否开启了LRU,如果开启的话，就把最近访问的元素放到链表的尾部。最后返回需要获取元素的值。
  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.             afterNodeAccess(e);
  8.         return e.value;
  9.     }
4.2.3 获取：删除方法
  1. // 这里是：HashMap的删除方法
  2.     final Node<K,V> removeNode(int hash, Object key, Object value,
  3.                                boolean matchValue, boolean movable) {
  4.         Node<K,V>[] tab; Node<K,V> p; int n, index;
  5.         if ((tab = table) != null && (n = tab.length) > 0 &&
  6.             (p = tab[index = (n - 1) & hash]) != null) {
  7.             Node<K,V> node = null, e; K k; V v;
  8.             if (p.hash == hash &&
  9.                 ((k = p.key) == key || (key != null && key.equals(k))))
  10.                 node = p;
  11.             else if ((e = p.next) != null) {
  12.                 if (p instanceof TreeNode)
  13.                     node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
  14.                 else {
  15.                     do {
  16.                         if (e.hash == hash &&
  17.                             ((k = e.key) == key ||
  18.                              (key != null && key.equals(k)))) {
  19.                             node = e;
  20.                             break;
  21.                         }
  22.                         p = e;
  23.                     } while ((e = e.next) != null);
  24.                 }
  25.             }
  26.             if (node != null && (!matchValue || (v = node.value) == value ||
  27.                                  (value != null && value.equals(v)))) {
  28.                 if (node instanceof TreeNode)
  29.                     ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
  30.                 else if (node == p)
  31.                     tab[index] = node.next;
  32.                 else
  33.                     p.next = node.next;
  34.                 ++modCount;
  35.                 --size;
  36.                 // 在删除元素之后，回调钩子方法，进行相关的钩子操作：
  37.                 // 在这里就是：删除节点，删除其关联的维护顺序的双向列表的操作
  38.                 afterNodeRemoval(node);
  39.                 return node;
  40.             }
  41.         }
  42.         return null;
  43.     }
  46.     void afterNodeRemoval(Node<K,V> e) { // unlink
  47.         LinkedHashMap.Entry<K,V> p =
  48.             (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  49.         // 此时p节点已删除，将p的前驱和后驱结点均置为null
  50.         p.before = p.after = null;
  51.         // 目的：将a,b结点进行相连操作
  52.         if (b == null)
  53.             head = a;
  54.         else
  55.             b.after = a;
  56.         if (a == null)
  57.             tail = b;
  58.         else
  59.             a.before = b;
  60.     }
4.2.4 迭代器
  1. // 首先LinkedHashMap重写了entry的方法
  2.     // 返回LinkedEntrySet的一个内部类类型
  3.     public Set<Map.Entry<K,V>> entrySet() {
  4.         Set<Map.Entry<K,V>> es;
  5.         return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
  6.     }
  8.     // 下面是：LinkedEntrySet类的全部代码。在这里我们主要看iterator()方法。其他的方法或代码感兴趣的可以研究，并不难。
  9.     final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
  10.         public final int size()                 { return size; }
  11.         public final void clear()               { LinkedHashMap.this.clear(); }
  12.         public final Iterator<Map.Entry<K,V>> iterator() {
  13.             // 这里返回了LinedEntryIterator对象。下面我们来看看这个对象是什么
  14.             return new LinkedEntryIterator();
  15.         }
  16.         public final boolean contains(Object o) {
  17.             if (!(o instanceof Map.Entry))
  18.                 return false;
  19.             Map.Entry<?,?> e = (Map.Entry<?,?>) o;
  20.             Object key = e.getKey();
  21.             Node<K,V> candidate = getNode(hash(key), key);
  22.             return candidate != null && candidate.equals(e);
  23.         }
  24.         public final boolean remove(Object o) {
  25.             if (o instanceof Map.Entry) {
  26.                 Map.Entry<?,?> e = (Map.Entry<?,?>) o;
  27.                 Object key = e.getKey();
  28.                 Object value = e.getValue();
  29.                 return removeNode(hash(key), key, value, true, true) != null;
  30.             }
  31.             return false;
  32.         }
  33.         public final Spliterator<Map.Entry<K,V>> spliterator() {
  34.             return Spliterators.spliterator(this, Spliterator.SIZED |
  35.                                             Spliterator.ORDERED |
  36.                                             Spliterator.DISTINCT);
  37.         }
  38.         public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
  39.             if (action == null)
  40.                 throw new NullPointerException();
  41.             int mc = modCount;
  42.             for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
  43.                 action.accept(e);
  44.             if (modCount != mc)
  45.                 throw new ConcurrentModificationException();
  46.         }
  47.     }
  48.     // 类LinkedEntryIterator的构成：
  49.     final class LinkedEntryIterator extends LinkedHashIterator
  50.         implements Iterator<Map.Entry<K,V>> {
  51.         //在这里调用了nextNode()方法。下面让我们来看看nextNode是个 什么方法。
  52.         public final Map.Entry<K,V> next() { return nextNode(); }
  53.     }
  55.     // nextNode()方法是LinkedHashIterator中的一个方法。
  56.     // 下面让我们来研究下这个类的大概结构：
  57.     abstract class LinkedHashIterator {
  58.         // 存储着要迭代的下一个元素
  59.         LinkedHashMap.Entry<K,V> next;
  60.         // 储存着当前迭代的元素对象
  61.         LinkedHashMap.Entry<K,V> current;
  62.         // 修改次数。作用见下方。
  63.         int expectedModCount;
  65.         // 第一次进来。默认将next节点指向头结点。
  66.         LinkedHashIterator() {
  67.             // 将next节点默认指向head结点
  68.             next = head;
  69.             expectedModCount = modCount;
  70.             // 将current 置为null
  71.             current = null;
  72.         }
  74.         // 判断：下一个节点是否为空
  75.         public final boolean hasNext() {
  76.             return next != null;
  77.         }
  79.         final LinkedHashMap.Entry<K,V> nextNode() {
  80.             LinkedHashMap.Entry<K,V> e = next;
  81.             // 如果在初始化迭代器的过程到初始化结束之前这段时间，集合发生了添加、删除等操作 ，抛出异常
  82.             if (modCount != expectedModCount)
  83.                 throw new ConcurrentModificationException();
  84.             if (e == null)
  85.                 throw new NoSuchElementException();
  86.             // 对象current和next节点进行初始化操作，并返回当前结点    
  87.             current = e;
  88.             next = e.after;
  89.             return e;
  90.         }
  92.         public final void remove() {
  93.             Node<K,V> p = current;
  94.             if (p == null)
  95.                 throw new IllegalStateException();
  96.             if (modCount != expectedModCount)
  97.                 throw new ConcurrentModificationException();
  98.             current = null;
  99.             K key = p.key;
  100.             removeNode(hash(key), key, null, false, false);
  101.             expectedModCount = modCount;
  102.         }
  103.     }

三、结语

  • 学习LinkedHashMap一定要在 理解HashMap的基础上，如果不了解HashMap的请看下HashMap的源码实现这篇文章。

  • 思考

    1. LinkedHashMap是怎么保证元素有序的？
    2. LinkedHashMap和HashMap的有什么异同点？
    3. LinkedHashMap的在设置时用到了哪些Java的思想或设计模式？
      看到以上问题，脑子能有清晰的认识和思路。说明真的掌握了LinkedHashMap的源码实现。具体思路在下一章回答。

发表评论

表情：
评论列表 （有 0 条评论，313人围观）

还没有评论，来说两句吧...

相关阅读