死磕 java集合之LinkedHashMap源码分析

原创
2020/06/17 15:09
阅读数 169

🖕欢迎关注我的公众号“彤哥读源码”,查看更多源码系列文章, 与彤哥一起畅游源码的海洋。

简介

LinkedHashMap内部维护了一个双向链表,能保证元素按插入的顺序访问,也能以访问顺序访问,可以用来实现LRU缓存策略。

LinkedHashMap可以看成是 LinkedList + HashMap。

继承体系

LinkedHashMap继承HashMap,拥有HashMap的所有特性,并且额外增加了按一定顺序访问的特性。

存储结构

我们知道HashMap使用(数组 + 单链表 + 红黑树)的存储结构,那LinkedHashMap是怎么存储的呢?

通过上面的继承体系,我们知道它继承了HashMap,所以它的内部也有这三种结构,但是它还额外添加了一种“双向链表”的结构存储所有元素的顺序。

添加删除元素的时候需要同时维护在HashMap中的存储,也要维护在LinkedList中的存储,所以性能上来说会比HashMap稍慢。

源码解析

属性

  
  
  
  1. /**

  2. * 双向链表头节点

  3. */

  4. transient LinkedHashMap.Entry<K,V> head;


  5. /**

  6. * 双向链表尾节点

  7. */

  8. transient LinkedHashMap.Entry<K,V> tail;


  9. /**

  10. * 是否按访问顺序排序

  11. */

  12. final boolean accessOrder;

(1)head

双向链表的头节点,旧数据存在头节点。

(2)tail

双向链表的尾节点,新数据存在尾节点。

(3)accessOrder

是否需要按访问顺序排序,如果为false则按插入顺序存储元素,如果是true则按访问顺序存储元素。

内部类

  
  
  
  1. // 位于LinkedHashMap中

  2. static class Entry<K,V> extends HashMap.Node<K,V> {

  3. Entry<K,V> before, after;

  4. Entry(int hash, K key, V value, Node<K,V> next) {

  5. super(hash, key, value, next);

  6. }

  7. }


  8. // 位于HashMap中

  9. static class Node<K, V> implements Map.Entry<K, V> {

  10. final int hash;

  11. final K key;

  12. V value;

  13. Node<K, V> next;

  14. }

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

构造方法

  
  
  
  1. public LinkedHashMap(int initialCapacity, float loadFactor) {

  2. super(initialCapacity, loadFactor);

  3. accessOrder = false;

  4. }


  5. public LinkedHashMap(int initialCapacity) {

  6. super(initialCapacity);

  7. accessOrder = false;

  8. }


  9. public LinkedHashMap() {

  10. super();

  11. accessOrder = false;

  12. }


  13. public LinkedHashMap(Map<? extends K, ? extends V> m) {

  14. super();

  15. accessOrder = false;

  16. putMapEntries(m, false);

  17. }


  18. public LinkedHashMap(int initialCapacity,

  19. float loadFactor,

  20. boolean accessOrder) {

  21. super(initialCapacity, loadFactor);

  22. this.accessOrder = accessOrder;

  23. }

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

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

afterNodeInsertion(boolean evict)方法

在节点插入之后做些什么,在HashMap中的putVal()方法中被调用,可以看到HashMap中这个方法的实现为空。

  
  
  
  1. void afterNodeInsertion(boolean evict) { // possibly remove eldest

  2. LinkedHashMap.Entry<K,V> first;

  3. if (evict && (first = head) != null && removeEldestEntry(first)) {

  4. K key = first.key;

  5. removeNode(hash(key), key, null, false, true);

  6. }

  7. }


  8. protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {

  9. return false;

  10. }

evict,驱逐的意思。

(1)如果evict为true,且头节点不为空,且确定移除最老的元素,那么就调用HashMap.removeNode()把头节点移除(这里的头节点是双向链表的头节点,而不是某个桶中的第一个元素);

(2)HashMap.removeNode()从HashMap中把这个节点移除之后,会调用afterNodeRemoval()方法;

(3)afterNodeRemoval()方法在LinkedHashMap中也有实现,用来在移除元素后修改双向链表,见下文;

(4)默认removeEldestEntry()方法返回false,也就是不删除元素。

afterNodeAccess(Node  e)方法

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

  
  
  
  1. void afterNodeAccess(Node<K,V> e) { // move node to last

  2. LinkedHashMap.Entry<K,V> last;

  3. // 如果accessOrder为true,并且访问的节点不是尾节点

  4. if (accessOrder && (last = tail) != e) {

  5. LinkedHashMap.Entry<K,V> p =

  6. (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;

  7. // 把p节点从双向链表中移除

  8. p.after = null;

  9. if (b == null)

  10. head = a;

  11. else

  12. b.after = a;


  13. if (a != null)

  14. a.before = b;

  15. else

  16. last = b;


  17. // 把p节点放到双向链表的末尾

  18. if (last == null)

  19. head = p;

  20. else {

  21. p.before = last;

  22. last.after = p;

  23. }

  24. // 尾节点等于p

  25. tail = p;

  26. ++modCount;

  27. }

  28. }

(1)如果accessOrder为true,并且访问的节点不是尾节点;

(2)从双向链表中移除访问的节点;

(3)把访问的节点加到双向链表的末尾;(末尾为最新访问的元素)

afterNodeRemoval(Node  e)方法

在节点被删除之后调用的方法。

  
  
  
  1. void afterNodeRemoval(Node<K,V> e) { // unlink

  2. LinkedHashMap.Entry<K,V> p =

  3. (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;

  4. // 把节点p从双向链表中删除。

  5. p.before = p.after = null;

  6. if (b == null)

  7. head = a;

  8. else

  9. b.after = a;

  10. if (a == null)

  11. tail = b;

  12. else

  13. a.before = b;

  14. }

经典的把节点从双向链表中删除的方法。

get(Object key)方法

获取元素。

  
  
  
  1. public V get(Object key) {

  2. Node<K,V> e;

  3. if ((e = getNode(hash(key), key)) == null)

  4. return null;

  5. if (accessOrder)

  6. afterNodeAccess(e);

  7. return e.value;

  8. }

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

总结

(1)LinkedHashMap继承自HashMap,具有HashMap的所有特性;

(2)LinkedHashMap内部维护了一个双向链表存储所有的元素;

(3)如果accessOrder为false,则可以按插入元素的顺序遍历元素;

(4)如果accessOrder为true,则可以按访问元素的顺序遍历元素;

(5)LinkedHashMap的实现非常精妙,很多方法都是在HashMap中留的钩子(Hook),直接实现这些Hook就可以实现对应的功能了,并不需要再重写put()等方法;

(6)默认的LinkedHashMap并不会移除旧元素,如果需要移除旧元素,则需要重写removeEldestEntry()方法设定移除策略;

(7)LinkedHashMap可以用来实现LRU缓存淘汰策略;

彩蛋

LinkedHashMap如何实现LRU缓存淘汰策略呢?

首先,我们先来看看LRU是个什么鬼。LRU,Least Recently Used,最近最少使用,也就是优先淘汰最近最少使用的元素。

如果使用LinkedHashMap,我们把accessOrder设置为true是不是就差不多能实现这个策略了呢?答案是肯定的。请看下面的代码:

  
  
  
  1. package com.coolcoding.code;


  2. import java.util.LinkedHashMap;

  3. import java.util.Map;


  4. /**

  5. * @author: tangtong

  6. * @date: 2019/3/18

  7. */

  8. public class LRUTest {

  9. public static void main(String[] args) {

  10. // 创建一个只有5个元素的缓存

  11. LRU<Integer, Integer> lru = new LRU<>(5, 0.75f);

  12. lru.put(1, 1);

  13. lru.put(2, 2);

  14. lru.put(3, 3);

  15. lru.put(4, 4);

  16. lru.put(5, 5);

  17. lru.put(6, 6);

  18. lru.put(7, 7);


  19. System.out.println(lru.get(4));


  20. lru.put(6, 666);


  21. // 输出: {3=3, 5=5, 7=7, 4=4, 6=666}

  22. // 可以看到最旧的元素被删除了

  23. // 且最近访问的4被移到了后面

  24. System.out.println(lru);

  25. }

  26. }


  27. class LRU<K, V> extends LinkedHashMap<K, V> {


  28. // 保存缓存的容量

  29. private int capacity;


  30. public LRU(int capacity, float loadFactor) {

  31. super(capacity, loadFactor, true);

  32. this.capacity = capacity;

  33. }


  34. /**

  35. * 重写removeEldestEntry()方法设置何时移除旧元素

  36. * @param eldest

  37. * @return

  38. */

  39. @Override

  40. protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {

  41. // 当元素个数大于了缓存的容量, 就移除元素

  42. return size() > this.capacity;

  43. }

  44. }


欢迎关注我的公众号“彤哥读源码”,查看更多源码系列文章, 与彤哥一起畅游源码的海洋。

喜欢这篇文章

就点下在看哦


本文分享自微信公众号 - 彤哥读源码(gh_63d1b83b9e01)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部