1、LinkedHashMap-底层数据结构

  1. 1、LinkedHashMap-底层数据结构：与HanshMap一样，只是实现细节上有所区别。
  3. 2、LinkedHashMap-属性有：
  4.     /**
  5.      * 双向链表的头节点
  6.      */
  7.     transient LinkedHashMap.Entry<K,V> head;
  9.     /**
  10.      * 双向链表的尾节点
  11.      */
  12.     transient LinkedHashMap.Entry<K,V> tail;
  14.     /**
  15.      * Ttrue表示最近最少使用次序(访问顺序)，false表示插入顺序
  16.      *
  17.      * @serial
  18.      */
  19.     final boolean accessOrder;

2、LinkedHashMap-构造方法

  1. 1、LinkedHashMap有多个构造方法：所有构造方法都是通过调用父类的构造方法来创建对象的。
  2. 2、源代码：
  3.     /**
  4.         无参构造函数：
  5.             LinkedHashMap存储数据是有序的，而且分为两种：插入顺序(默认值)和访问顺序。
  6.     */
  7.     public LinkedHashMap() {
  8.         //.super()调用了父类HashMap的构造方法，其实就是根据初始容量、负载因子去初始化Entry[] table
  9.         super();
  10.         //把accessOrder设置为false-存储顺序为插入顺序，默认值
  11.         accessOrder = false;
  12.     }
  14.     /**
  15.         指定初始容量的构造函数
  16.     */
  17.     public LinkedHashMap(int initialCapacity) {
  18.         super(initialCapacity);
  19.         accessOrder = false;
  20.     }
  22.     /**
  23.         指定初始容量和加载因子的构造函数
  24.     */
  25.     public LinkedHashMap(int initialCapacity, float loadFactor) {
  26.         super(initialCapacity, loadFactor);
  27.         accessOrder = false;
  28.     }
  30.     /**
  31.         传入Map为参数的构造函数
  32.     */
  33.     public LinkedHashMap(Map<? extends K, ? extends V> m) {
  34.         super();
  35.         accessOrder = false;
  36.         putMapEntries(m, false);
  37.     }
  39.     /**
  40.         指定初始容量、加载因子、存储顺序的构造函数
  41.     */
  42.     public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
  43.         super(initialCapacity, loadFactor);
  44.         this.accessOrder = accessOrder;
  45.     }

3、LinkedHashMap-Entry类

  1. 1、Entry类-简介
  2.     1-1、JDK8之前
  3.         1-1-1、LinkedHashMap的Entry元素继承HashMap的Entry，提供了双向链表的功能。在上述HashMap的构造器中，最后会调用init()方法，进行相关的初始化，这个方法在HashMap的实现中并无意义，只是提供给子类实现相关的初始化调用。
  4.         1-1-2、LinkedHashMap重写了init()方法，在调用父类的构造方法完成构造后，进一步实现了对其元素Entry的初始化操作。
  5.     1-2、JDK8之后
  6.         1-2-1、LinkedHashMap的Entry元素继承HashMap的Node,HashMap中的Node实现了Entry，
  7.         1-2-2、源代码：
  8.                /**
  9.              * 继承了HashMap的Node，Node基础上添加了before和after两个指针，
  10.              */
  11.             static class Entry<K,V> extends HashMap.Node<K,V> {
  12.                 //用于维护Entry插入的先后顺序的，即：用于维护双向链表。
  13.                 Entry<K,V> before, after;
  14.                 //Node<K,V> next : 是用于维护HashMap指定table位置上连接的Entry的顺序的
  15.                 Entry(int hash, K key, V value, Node<K,V> next) {
  16.                     super(hash, key, value, next);
  17.                 }
  18.             }
  20.             /**
  21.              * Basic hash bin node, used for most entries.  
  22.              * TreeNode子类，并在LinkedHashMap中为其Entry子类创建
  23.              */
  24.             static class Node<K,V> implements Map.Entry<K,V> {
  25.                 final int hash;
  26.                 final K key;
  27.                 V value;
  28.                 Node<K,V> next;
  30.                 Node(int hash, K key, V value, Node<K,V> next) {
  31.                     this.hash = hash;
  32.                     this.key = key;
  33.                     this.value = value;
  34.                     this.next = next;
  35.                 }
  37.                 public final K getKey()        { return key; }
  38.                 public final V getValue()      { return value; }
  39.                 public final String toString() { return key + "=" + value; }
  41.                 public final int hashCode() {
  42.                     return Objects.hashCode(key) ^ Objects.hashCode(value);
  43.                 }
  45.                 public final V setValue(V newValue) {
  46.                     V oldValue = value;
  47.                     value = newValue;
  48.                     return oldValue;
  49.                 }
  51.                 public final boolean equals(Object o) {
  52.                     if (o == this)
  53.                         return true;
  54.                     if (o instanceof Map.Entry) {
  55.                         Map.Entry<?,?> e = (Map.Entry<?,?>)o;
  56.                         if (Objects.equals(key, e.getKey()) &&
  57.                             Objects.equals(value, e.getValue()))
  58.                             return true;
  59.                     }
  60.                     return false;
  61.                 }
  62.             }
  64. 2、当你插入元素时它会将节点插入双向链表的链尾，如果key重复，则也会将节点移动至链尾，当用get()方法获取value时也会将节点移动至链尾。

4、LinkedHashMap-添加元素

  1. 1、添加元素：.put()方法。
  2.     1-1、LinkedHashMap的put()方法是调用的HashMap的put()方法。???
  3.         HashMap中.put()
  4.             public V put(K key, V value) {
  5.                 return putVal(hash(key), key, value, false, true);
  6.             }
  8.             final V putVal(int hash, K key, V value, boolean onlyIfAbsent,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.                     tab[i] = newNode(hash, key, value, null);
  15.                 else {
  16.                     Node<K,V> e; K k;
  17.                     if (p.hash == hash &&
  18.                         ((k = p.key) == key || (key != null && key.equals(k))))
  19.                         e = p;
  20.                     else if (p instanceof TreeNode)
  21.                         e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  22.                     else {
  23.                         for (int binCount = 0; ; ++binCount) {
  24.                             if ((e = p.next) == null) {
  25.                                 p.next = newNode(hash, key, value, null);
  26.                                 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  27.                                     treeifyBin(tab, hash);
  28.                                 break;
  29.                             }
  30.                             if (e.hash == hash &&
  31.                                 ((k = e.key) == key || (key != null && key.equals(k))))
  32.                                 break;
  33.                             p = e;
  34.                         }
  35.                     }
  36.                     if (e != null) { // existing mapping for key
  37.                         V oldValue = e.value;
  38.                         if (!onlyIfAbsent || oldValue == null)
  39.                             e.value = value;
  40.                         //在节点被访问后移动链尾,LinkedHashMap中实现了该方法
  41.                         afterNodeAccess(e);
  42.                         return oldValue;
  43.                     }
  44.                 }
  45.                 ++modCount;
  46.                 if (++size > threshold)
  47.                     resize();
  48.                 //完成新数据put后调用,LinkedHashMap实现了该方法
  49.                 afterNodeInsertion(evict);
  50.                 return null;
  51.             }
  52. 2、源代码：
  53.     //LinkedHashMap中重写了.newNode()方法
  54.     Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
  55.         LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
  56.         //将节点插入链尾
  57.         linkNodeLast(p);
  58.         return p;
  59.     }
  61.     // link at the end of list
  62.     private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
  63.         LinkedHashMap.Entry<K,V> last = tail;
  64.         tail = p;2
  65.         // 如果链尾为空，则双向链表为空，则p即为头结点也为尾节点
  66.         if (last == null)
  67.             head = p;
  68.         else {
  69.             //否则的话修改指针，让之前链尾的after指针指向p，p的before指向之前链尾
  70.             p.before = last;
  71.             last.after = p;
  72.         }
  73.     }
  74.      /**
  75.       *        .afterNodeAccess()方法执行过程解析：
  76.       *      p将引用移除
  77.       *              b          |          p            |          a
  78.       *       -------------     |     -------------     |     -------------
  79.       *      |before| after| <==|==> |before| after| <==|==> |before| after|
  80.       *       -------------     |     -------------     |     -------------
  81.       *     
  82.       *     1.b为NULL时,则a变为头结点
  83.       *                           head
  84.       *                             a                          p
  85.       *       (b)             -------------                ------------- 
  86.       *      NULL    <------ |before| after|  ......      |before| after| (p最后将插入链尾)
  87.       *                       -------------                -------------              
  88.       *     2.a为NULL时，则b变为链尾节点
  89.       *
  90.       *             tail
  91.       *              b                                           p
  92.       *       -------------             (a)                ------------- 
  93.       *      |before| after|  ------->  NULL   ......     |before| after| (p最后将插入链尾)
  94.       *       -------------                                -------------  
  95.       *     3.a,b都为NULL时，p即为头结点，又为尾节点
  96.       *     
  97.       *     因为p前后都没有元素，则双向链表中只有p一个节点
  98.       *       
  99.       */
  100.     //在节点被访问后移动链尾,LinkedHashMap中实现了HashMap.afterNodeAccess()方法
  101.     //在按插入顺序时，在有相同key时，对当前节点将其移到链表末尾。
  102.     //通过before、after指针，将新访问节点链接为链表尾节点
  103.     void afterNodeAccess(Node<K,V> e) { // move node to last
  104.         LinkedHashMap.Entry<K,V> last;
  105.         //accessOrder为true && 访问节点不等于为节点
  106.         if (accessOrder && (last = tail) != e) {
  107.             LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  108.             //因为要移动到链尾，所以先至尾指针为空
  109.             p.after = null;
  110.             //如果前面没有元素，则p之前为头结点，直接让a成为头结点
  111.             if (b == null)
  112.                 head = a;
  113.             else
  114.                 // 否则b的尾指针指向a
  115.                 b.after = a;
  116.             //如果a不为空，则a的头指针指向b
  117.             if (a != null)
  118.                 a.before = b;
  119.             else
  120.                 //否则 p之前就为尾指针，则令b成为尾指针
  121.                 last = b;
  122.             //如果双向链表中只有p一个节点，则令p即为头结点，也为尾节点
  123.             if (last == null)
  124.                 head = p;
  125.             else {
  126.                 //否则 将p插入链尾
  127.                 p.before = last;
  128.                 last.after = p;
  129.             }
  130.             tail = p;
  131.             ++modCount;
  132.         }
  133.     }
  135.     //节点插入，完成新数据put后调用
  136.     //removeEldestEntry()默认是返回false的，需要子类继承重写removeEldestEntry()方法。
  137.     void afterNodeInsertion(boolean evict) { // possibly remove eldest
  138.         LinkedHashMap.Entry<K,V> first;
  139.         if (evict && (first = head) != null && removeEldestEntry(first)) {
  140.             K key = first.key;
  141.             //当插入时，将双向链表的头结点移除
  142.             removeNode(hash(key), key, null, false, true);
  143.         }
  144.     }
  146.     //removeEldestEntry()默认是返回false的，需要子类继承重写removeEldestEntry()方法。
  147.     //通过覆盖此方法可实现不同策略的缓存，实现缓存机制【!!!】
  148.     /**
  149.         LinkedHashMap自带的移除最头（最老）数据的方法：
  150.             removeElestEntry用于定义删除最老元素的规则。一旦需要删除最老节点，那么将会调用removeNode删除节点。 举个例子，如果一个链表只能维持100个元素，那么当插入了第101个元素时，以如下方式重写removeEldestEntry的话，那么将会删除最老的一个元素。
  151.     */
  152.     protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
  153.         return false;
  154.     }

5、LinkedHashMap-获取元素

  1. 1、获取元素：.get()方法：LinkedHashMap重写了get()方法，实现了LRU
  2. 2、源代码：
  3.     public V get(Object key) {
  4.         Node<K,V> e;
  5.         //.getNode()，调用父类HashMap的.getNode()方法
  6.         if ((e = getNode(hash(key), key)) == null)
  7.             return null;
  8.         // accessOder为true时，被访问的节点被置于双向链表尾部
  9.         if (accessOrder)
  10.             afterNodeAccess(e);
  11.         return e.value;
  12.     }

6、LinkedHashMap-删除元素

  1. 1、获取元素：.remove()方法：调用的HashMap的remove()方法，LinkedHashMap中重写了.afterNodeRemoval()方法。
  3. 2、源代码：
  4.     //HashMap.removeNode()
  5.     final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, 
  6.                                boolean movable) {
  7.         Node<K,V>[] tab; Node<K,V> p; int n, index;
  8.         if ((tab = table) != null && (n = tab.length) > 0 &&
  9.             (p = tab[index = (n - 1) & hash]) != null) {
  10.             Node<K,V> node = null, e; K k; V v;
  11.             if (p.hash == hash &&
  12.                 ((k = p.key) == key || (key != null && key.equals(k))))
  13.                 node = p;
  14.             else if ((e = p.next) != null) {
  15.                 if (p instanceof TreeNode)
  16.                     node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
  17.                 else {
  18.                     do {
  19.                         if (e.hash == hash &&
  20.                             ((k = e.key) == key ||
  21.                              (key != null && key.equals(k)))) {
  22.                             node = e;
  23.                             break;
  24.                         }
  25.                         p = e;
  26.                     } while ((e = e.next) != null);
  27.                 }
  28.             }
  29.             if (node != null && (!matchValue || (v = node.value) == value ||
  30.                                  (value != null && value.equals(v)))) {
  31.                 if (node instanceof TreeNode)
  32.                     ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
  33.                 else if (node == p)
  34.                     tab[index] = node.next;
  35.                 else
  36.                     p.next = node.next;
  37.                 ++modCount;
  38.                 --size;
  39.                 //回调从双向链表中移除node，用于将节点从双向链表移除。LinkedHashMap实现了该方法。
  40.                 afterNodeRemoval(node);
  41.                 return node;
  42.             }
  43.         }
  44.         return null;
  45.     }
  47.     //LinkedHashMap实现了HashMap中的afterNodeRemoval()方法
  48.     //在该方法中完成了移除被删除节点的操作
  49.     void afterNodeRemoval(Node<K,V> e) { // unlink
  50.         LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  51.         // 将 p 节点的前驱后后继引用置空
  52.         p.before = p.after = null;
  53.         // b 为 null，表明 p 是头节点
  54.         if (b == null)
  55.             head = a;
  56.         else
  57.             b.after = a;
  58.         // a 为 null，表明 p 是尾节点
  59.         if (a == null)
  60.             tail = b;
  61.         else
  62.             a.before = b;
  63.     }