Java 集合 (8) -- LinkedHashMap 类_综合

文章目录

- 1. 简介
- 2. 继承体系
- 3. 字段
- 4. 内部类
- 5. 构造器
- 6. 常用方法
- 7. 扩展

1. 简介

public class LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V> {
    }

HashMap 是无序的，也就是说，迭代 HashMap 所得到的元素顺序并不是它们最初放置到 HashMap 的顺序；HashMap 的这一缺点往往会造成诸多不便，因为在有些场景中，我们确需要用到一个可以保持插入顺序的 Map。庆幸的是，JDK 为我们解决了这个问题，它为 HashMap 提供了一个子类：LinkedHashMap。虽然 LinkedHashMap 增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序；需要注意的是，该迭代顺序可以是插入顺序，也可以是访问顺序。因此，根据链表中元素的顺序可以将 LinkedHashMap 分为：保持插入顺序的 LinkedHashMap 和保持访问顺序的 LinkedHashMap，其中 LinkedHashMap 的默认实现是按插入顺序排序的；

LinkedHashMap 其实就是 HashMap 和双向链表的融合体，准确地说，它是一个将所有 Entry 节点链入到一个双向链表的 HashMap，由于 LinkedHashMap 是 HashMap 的子类，所以 LinkedHashMap 自然会拥有 HashMap 的所有特性。比如 LinkedHashMap 的元素存取过程基本与 HashMap 类似，只是在细节的实现上稍有不同。当然，这是由 LinkedHashMap 本身的特性所决定的，因为它额外维护了一个双向链表来用于保持迭代顺序，此外，LinkedHashMap 可以很好的支持 LRU 算法，同时它也是非同步的。

2. 继承体系

在这里插入图片描述

3. 字段

/** * 双向链表头节点，旧数据存在头节点 */
transient LinkedHashMap.Entry<K,V> head;/** * 双向链表尾节点，新数据存在尾节点 */
transient LinkedHashMap.Entry<K,V> tail;/** * 是否按访问顺序排序，如果为false则按插入顺序存储元素，如果是true则按访问顺序存储元素 */
final boolean accessOrder;

4. 内部类

// 位于LinkedHashMap中
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {
    super(hash, key, value, next);}
}// 位于HashMap中
static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;final K key;V value;Node<K, V> next;
}

存储节点，继承自HashMap的Node类，next用于单链表存储于桶中，before和after用于双向链表存储所有元素。

5. 构造器

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);accessOrder = false;
}public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);accessOrder = false;
}public LinkedHashMap() {
    super();accessOrder = false;
}public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();accessOrder = false;putMapEntries(m, false);
}public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
    super(initialCapacity, loadFactor);this.accessOrder = accessOrder;
}

前四个构造方法accessOrder都等于false，说明双向链表是按插入顺序存储元素。

最后一个构造方法accessOrder从构造方法参数传入，如果传入true，则按访问顺序存储元素，这也是实现LRU缓存策略的关键。

6. 常用方法

void afterNodeInsertion(boolean evict)：在节点插入之后做些什么，在HashMap中的putVal()方法中被调用，可以看到HashMap中这个方法的实现为空。
```
void afterNodeInsertion(boolean evict) {
       // evict: 驱逐的意思LinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {
      K key = first.key;removeNode(hash(key), key, null, false, true);}
}protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
      return false;
}
```
如果evict为true，且头节点不为空，且确定移除最老的元素，那么就调用HashMap.removeNode()把头节点移除（这里的头节点是双向链表的头节点，而不是某个桶中的第一个元素）；HashMap.removeNode()从HashMap中把这个节点移除之后，会调用afterNodeRemoval()方法；afterNodeRemoval()方法在LinkedHashMap中也有实现，用来在移除元素后修改双向链表；默认removeEldestEntry()方法返回false，也就是不删除元素。

void afterNodeAccess(Node<K,V> e)：在节点访问之后被调用，主要在put()已经存在的元素或get()时被调用，如果accessOrder为true，调用这个方法把访问到的节点移动到双向链表的末尾。

void afterNodeAccess(Node<K,V> e) {
       // move node to lastLinkedHashMap.Entry<K,V> last;// 如果accessOrder为true，并且访问的节点不是尾节点if (accessOrder && (last = tail) != e) {
      LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;// 把p节点从双向链表中移除p.after = null;if (b == null)head = a;elseb.after = a;if (a != null)a.before = b;elselast = b;// 把p节点放到双向链表的末尾if (last == null)head = p;else {
      p.before = last;last.after = p;}// 尾节点等于ptail = p;++modCount;}
}

如果accessOrder为true，并且访问的节点不是尾节点；从双向链表中移除访问的节点；把访问的节点加到双向链表的末尾；（末尾为最新访问的元素）

void afterNodeRemoval(Node<K,V> e)：在节点被删除之后调用的方法

void afterNodeRemoval(Node<K,V> e) {
       // unlinkLinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;// 把节点p从双向链表中删除。p.before = p.after = null;if (b == null)head = a;elseb.after = a;if (a == null)tail = b;elsea.before = b;
}

把节点从双向链表中删除

public V get(Object key)：获取元素

public V get(Object key) {
      Node<K,V> e;if ((e = getNode(hash(key), key)) == null)return null;if (accessOrder)afterNodeAccess(e);return e.value;
}

如果查找到了元素，且accessOrder为true，则调用afterNodeAccess()方法把访问的节点移到双向链表的末尾

7. 扩展

LinkedHashMap的实现非常精妙，很多方法都是在HashMap中留的钩子（Hook），直接实现这些Hook就可以实现对应的功能了，并不需要再重写put()等方法；
默认的LinkedHashMap并不会移除旧元素，如果需要移除旧元素，则需要重写removeEldestEntry()方法设定移除策略；

LinkedHashMap实现LRU缓存淘汰策略：LRU，Least Recently Used，最近最少使用，也就是优先淘汰最近最少使用的元素。如果使用LinkedHashMap，我们把accessOrder设置为true是不是就差不多能实现这个策略了呢？答案是肯定的。

public class LRUTest {
      public static void main(String[] args) {
      // 创建一个只有5个元素的缓存LRU<Integer, Integer> lru = new LRU<>(5, 0.75f);lru.put(1, 1);lru.put(2, 2);lru.put(3, 3);lru.put(4, 4);lru.put(5, 5);lru.put(6, 6);lru.put(7, 7);System.out.println(lru.get(4)); //结果：4lru.put(6, 666);// 输出: {3=3, 5=5, 7=7, 4=4, 6=666}// 可以看到最旧的元素被删除了// 且最近访问的4被移到了后面System.out.println(lru);}
}class LRU<K, V> extends LinkedHashMap<K, V> {
      // 保存缓存的容量private int capacity;public LRU(int capacity, float loadFactor) {
      super(capacity, loadFactor, true); //accessOrder设置为truethis.capacity = capacity;}/*** 重写removeEldestEntry()方法设置何时移除旧元素* @param eldest* @return*/@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
      // 当元素个数大于了缓存的容量, 就移除元素return size() > this.capacity;}
}