查看: 1983|回复: 0

[Java语言] LinkedHashMap 源码详细分析(JDK1.8)

发表于 2018-2-3 08:00:05
1. 概述

LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。除此之外,LinkedHashMap 对访问顺序也提供了相关支持。在一些场景下,该特性很有用,比如缓存。在实现上,LinkedHashMap 很多方法直接继承自 HashMap,仅为维护双向链表覆写了部分方法。所以,要看懂 LinkedHashMap 的源码,需要先看懂 HashMap 的源码。关于 HashMap 的源码分析,本文并不打算展开讲了。大家可以参考我之前的一篇文章“HashMap 源码详细分析(JDK1.8)”。在那篇文章中,我配了十多张图帮助大家学习 HashMap 源码。

本篇文章的结构与我之前两篇关于 Java 集合类(集合框架)的源码分析文章不同,本文将不再分析集合类的基本操作(查找、遍历、插入、删除),而是把重点放在双向链表的维护上。包括链表的建立过程,删除节点的过程,以及访问顺序维护的过程等。好了,接下里开始分析吧。

2. 原理

上一章说了 LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列结构。该结构由数组和链表或红黑树组成,结构示意图大致如下:

LinkedHashMap 在上面结构的基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。其结构可能如下图:

上图中,淡蓝色的箭头表示前驱引用,红色箭头表示后继引用。每当有新键值对节点插入,新节点最终会接在 tail 引用指向的节点后面。而 tail 引用则会移动到新的节点上,这样一个双向链表就建立起来了。

上面的结构并不是很难理解,虽然引入了红黑树,导致结构看起来略为复杂了一些。但大家完全可以忽略红黑树,而只关注链表结构本身。好了,接下来进入细节分析吧。

3. 源码分析 3.1 Entry 的继承体系

在对核心内容展开分析之前,这里先插队分析一下键值对节点的继承体系。先来看看继承体系结构图:

上面的继承体系乍一看还是有点复杂的,同时也有点让人迷惑。HashMap 的内部类 TreeNode 不继承它的了一个内部类 Node,却继承自 Node 的子类 LinkedHashMap 内部类 Entry。这里这样做是有一定原因的,这里先不说。先来简单说明一下上面的继承体系。LinkedHashMap 内部类 Entry 继承自 HashMap 内部类 Node,并新增了两个引用,分别是 before 和 after。这两个引用的用途不难理解,也就是用于维护双向链表。同时,TreeNode 继承 LinkedHashMap 的内部类 Entry 后,就具备了和其他 Entry 一起组成链表的能力。但是这里需要大家考虑一个问题。当我们使用 HashMap 时,TreeNode 并不需要具备组成链表能力。如果继承 LinkedHashMap 内部类 Entry ,TreeNode 就多了两个用不到的引用,这样做不是会浪费空间吗?简单说明一下这个问题(水平有限,不保证完全正确),这里这么做确实会浪费空间,但与 TreeNode 通过继承获取的组成链表的能力相比,这点浪费是值得的。在 HashMap 的设计思路注释中,有这样一段话:

Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins. In
usages with well-distributed user hashCodes, tree bins are
rarely used.

大致的意思是 TreeNode 对象的大小约是普通 Node 对象的2倍,我们仅在桶(bin)中包含足够多的节点时再使用。当桶中的节点数量变少时(取决于删除和扩容),TreeNode 会被转成 Node。当用户实现的 hashCode 方法具有良好分布性时,树类型的桶将会很少被使用。

通过上面的注释,我们可以了解到。一般情况下,只要 hashCode 的实现不糟糕,Node 组成的链表很少会被转成由 TreeNode 组成的红黑树。也就是说 TreeNode 使用的并不多,浪费那点空间是可接受的。假如 TreeNode 机制继承自 Node 类,那么它要想具备组成链表的能力,就需要 Node 去继承 LinkedHashMap 的内部类 Entry。这个时候就得不偿失了,浪费很多空间去获取不一定用得到的能力。

说到这里,大家应该能明白节点类型的继承体系了。这里单独拿出来说一下,为下面的分析做铺垫。叙述略为啰嗦,见谅。

3.1 链表的建立过程

链表的建立过程是在插入键值对节点时开始的,初始情况下,让 LinkedHashMap 的 head 和 tail 引用同时指向新节点,链表就算建立起来了。随后不断有新节点插入,通过将新节点接在 tail 引用指向节点的后面,即可实现链表的更新。

Map 类型的集合类是通过 put(K,V) 方法插入键值对,LinkedHashMap 本身并没有覆写父类的 put 方法,而是直接使用了父类的实现。但在 HashMap 中,put 方法插入的是 HashMap 内部类 Node 类型的节点,该类型的节点并不具备与 LinkedHashMap 内部类 Entry 及其子类型节点组成链表的能力。那么,LinkedHashMap 是怎样建立链表的呢?在展开说明之前,我们先看一下 LinkedHashMap 插入操作相关的代码:

  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. // 通过节点 hash 定位节点所在的桶位置,并检测桶中是否包含节点引用
  11. if ((p = tab[i = (n - 1) & hash]) == null) {...}
  12. else {
  13. Node<K,V> e; K k;
  14. if (p.hash == hash &&
  15. ((k = p.key) == key || (key != null && key.equals(k))))
  16. e = p;
  17. else if (p instanceof TreeNode) {...}
  18. else {
  19. // 遍历链表,并统计链表长度
  20. for (int binCount = 0; ; ++binCount) {
  21. // 未在单链表中找到要插入的节点,将新节点接在单链表的后面
  22. if ((e = p.next) == null) {
  23. p.next = newNode(hash, key, value, null);
  24. if (binCount >= TREEIFY_THRESHOLD - 1) {...}
  25. break;
  26. }
  27. // 插入的节点已经存在于单链表中
  28. if (e.hash == hash &&
  29. ((k = e.key) == key || (key != null && key.equals(k))))
  30. break;
  31. p = e;
  32. }
  33. }
  34. if (e != null) { // existing mapping for key
  35. V oldValue = e.value;
  36. if (!onlyIfAbsent || oldValue == null) {...}
  37. afterNodeAccess(e); // 回调方法,后续说明
  38. return oldValue;
  39. }
  40. }
  41. ++modCount;
  42. if (++size > threshold) {...}
  43. afterNodeInsertion(evict); // 回调方法,后续说明
  44. return null;
  45. }
  46. // HashMap 中实现
  47. Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
  48. return new Node<>(hash, key, value, next);
  49. }
  50. // LinkedHashMap 中覆写
  51. Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
  52. LinkedHashMap.Entry<K,V> p =
  53. new LinkedHashMap.Entry<K,V>(hash, key, value, e);
  54. // 将 Entry 接在双向链表的尾部
  55. linkNodeLast(p);
  56. return p;
  57. }
  58. // LinkedHashMap 中实现
  59. private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
  60. LinkedHashMap.Entry<K,V> last = tail;
  61. tail = p;
  62. // last 为 null,表明链表还未建立
  63. if (last == null)
  64. head = p;
  65. else {
  66. // 将新节点 p 接在链表尾部
  67. p.before = last;
  68. last.after = p;
  69. }
  70. }
复制代码

上面就是 LinkedHashMap 插入相关的源码,这里省略了部分非关键的代码。我根据上面的代码,可以知道 LinkedHashMap 插入操作的调用过程。如下:

我把 newNode 方法红色背景标注了出来,这一步比较关键。LinkedHashMap 覆写了该方法。在这个方法中,LinkedHashMap 创建了 Entry,并通过 linkNodeLast 方法将 Entry 接在双向链表的尾部,实现了双向链表的建立。双向链表建立之后,我们就可以按照插入顺序去遍历 LinkedHashMap,大家可以自己写点测试代码验证一下插入顺序。

以上就是 LinkedHashMap 维护插入顺序的相关分析。本节的最后,再额外补充一些东西。大家如果仔细看上面的代码的话,会发现有两个以after开头方法,在上文中没有被提及。在 JDK 1.8 HashMap 的源码中,相关的方法有3个:

  1. // Callbacks to allow LinkedHashMap post-actions
  2. void afterNodeAccess(Node<K,V> p) { }
  3. void afterNodeInsertion(boolean evict) { }
  4. void afterNodeRemoval(Node<K,V> p) { }
复制代码

根据这三个方法的注释可以看出,这些方法的用途是在增删查等操作后,通过回调的方式,让 LinkedHashMap 有机会做一些后置操作。上述三个方法的具体实现在 LinkedHashMap 中,本节先不分析这些实现,相关分析会在后续章节中进行。

3.2 链表节点的删除过程

与插入操作一样,LinkedHashMap 删除操作相关的代码也是直接用父类的实现。在删除节点时,父类的删除逻辑并不会修复 LinkedHashMap 所维护的双向链表,这不是它的职责。那么删除及节点后,被删除的节点该如何从双链表中移除呢?当然,办法还算是有的。上一节最后提到 HashMap 中三个回调方法运行 LinkedHashMap 对一些操作做出响应。所以,在删除及节点后,回调方法 afterNodeRemoval 会被调用。LinkedHashMap 覆写该方法,并在该方法中完成了移除被删除节点的操作。相关源码如下:

  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. // HashMap 中实现
  8. final Node<K,V> removeNode(int hash, Object key, Object value,
  9. boolean matchValue, boolean movable) {
  10. Node<K,V>[] tab; Node<K,V> p; int n, index;
  11. if ((tab = table) != null && (n = tab.length) > 0 &&
  12. (p = tab[index = (n - 1) & hash]) != null) {
  13. Node<K,V> node = null, e; K k; V v;
  14. if (p.hash == hash &&
  15. ((k = p.key) == key || (key != null && key.equals(k))))
  16. node = p;
  17. else if ((e = p.next) != null) {
  18. if (p instanceof TreeNode) {...}
  19. else {
  20. // 遍历单链表,寻找要删除的节点,并赋值给 node 变量
  21. do {
  22. if (e.hash == hash &&
  23. ((k = e.key) == key ||
  24. (key != null && key.equals(k)))) {
  25. node = e;
  26. break;
  27. }
  28. p = e;
  29. } while ((e = e.next) != null);
  30. }
  31. }
  32. if (node != null && (!matchValue || (v = node.value) == value ||
  33. (value != null && value.equals(v)))) {
  34. if (node instanceof TreeNode) {...}
  35. // 将要删除的节点从单链表中移除
  36. else if (node == p)
  37. tab[index] = node.next;
  38. else
  39. p.next = node.next;
  40. ++modCount;
  41. --size;
  42. afterNodeRemoval(node); // 调用删除回调方法进行后续操作
  43. return node;
  44. }
  45. }
  46. return null;
  47. }
  48. // LinkedHashMap 中覆写
  49. void afterNodeRemoval(Node<K,V> e) { // unlink
  50. LinkedHashMap.Entry<K,V> p =
  51. (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  52. // 将 p 节点的前驱后后继引用置空
  53. p.before = p.after = null;
  54. // b 为 null,表明 p 是头节点
  55. if (b == null)
  56. head = a;
  57. else
  58. b.after = a;
  59. // a 为 null,表明 p 是尾节点
  60. if (a == null)
  61. tail = b;
  62. else
  63. a.before = b;
  64. }
复制代码

删除的过程并不复杂,上面这么多代码其实就做了三件事:

根据 hash 定位到桶位置 遍历链表或调用红黑树相关的删除方法 从 LinkedHashMap 维护的双链表中移除要删除的节点

举个例子说明一下,假如我们要删除下图键值为 3 的节点。

根据 hash 定位到该节点属于3号桶,然后在对3号桶保存的单链表进行遍历。找到要删除的节点后,先从单链表中移除该节点。如下:

然后再双向链表中移除该节点:

删除及相关修复过程并不复杂,结合上面的图片,大家应该很容易就能理解,这里就不多说了。

3.3 访问顺序的维护过程

前面说了插入顺序的实现,本节来讲讲访问顺序。默认情况下,LinkedHashMap 是按插入顺序维护链表。不过我们可以在初始化 LinkedHashMap,指定 accessOrder 参数为 true,即可让它按访问顺序维护链表。访问顺序的原理上并不复杂,当我们调用get/getOrDefault/replace等方法时,只需要将这些方法访问的节点移动到链表的尾部即可。相应的源码如下:

  1. // LinkedHashMap 中覆写
  2. public V get(Object key) {
  3. Node<K,V> e;
  4. if ((e = getNode(hash(key), key)) == null)
  5. return null;
  6. // 如果 accessOrder 为 true,则调用 afterNodeAccess 将被访问节点移动到链表最后
  7. if (accessOrder)
  8. afterNodeAccess(e);
  9. return e.value;
  10. }
  11. // LinkedHashMap 中覆写
  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. p.after = null;
  18. // 如果 b 为 null,表明 p 为头节点
  19. if (b == null)
  20. head = a;
  21. else
  22. b.after = a;
  23. if (a != null)
  24. a.before = b;
  25. /*
  26. * 这里存疑,父条件分支已经确保节点 e 不会是尾节点,
  27. * 那么 e.after 必然不会为 null,不知道 else 分支有什么作用
  28. */
  29. else
  30. last = b;
  31. if (last == null)
  32. head = p;
  33. else {
  34. // 将 p 接在链表的最后
  35. p.before = last;
  36. last.after = p;
  37. }
  38. tail = p;
  39. ++modCount;
  40. }
  41. }
复制代码

上面就是访问顺序的实现代码,并不复杂。下面举例演示一下,帮助大家理解。假设我们访问下图键值为3的节点,访问前结构为:

访问后,键值为3的节点将会被移动到双向链表的最后位置,其前驱和后继也会跟着更新。访问后的结构如下:

3.4 基于 LinkedHashMap 实现缓存

前面介绍了 LinkedHashMap 是如何维护插入和访问顺序的,大家对 LinkedHashMap 的原理应该有了一定的认识。本节我们来写一些代码实践一下,这里通过继承 LinkedHashMap 实现了一个简单的 LRU 策略的缓存。在写代码之前,先介绍一下前置知识。

在3.1节分析链表建立过程时,我故意忽略了部分源码分析。本节就把忽略的部分补上,先看源码吧:

  1. void afterNodeInsertion(boolean evict) { // possibly remove eldest
  2. LinkedHashMap.Entry<K,V> first;
  3. // 根据条件判断是否移除最近最少被访问的节点
  4. if (evict && (first = head) != null && removeEldestEntry(first)) {
  5. K key = first.key;
  6. removeNode(hash(key), key, null, false, true);
  7. }
  8. }
  9. // 移除最近最少被访问条件之一,通过覆盖此方法可实现不同策略的缓存
  10. protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
  11. return false;
  12. }
复制代码

上面的源码的核心逻辑在一般情况下都不会被执行,所以之前并没有进行分析。上面的代码做的事情比较简单,就是通过一些条件,判断是否移除最近最少被访问的节点。看到这里,大家应该知道上面两个方法的用途了。当我们基于 LinkedHashMap 实现缓存时,通过覆写removeEldestEntry方法可以实现自定义策略的 LRU 缓存。比如我们可以根据节点数量判断是否移除最近最少被访问的节点,或者根据节点的存活时间判断是否移除该节点等。本节所实现的缓存是基于判断节点数量是否超限的策略。在构造缓存对象时,传入最大节点数。当插入的节点数超过最大节点数时,移除最近最少被访问的节点。实现代码如下:

  1. public class SimpleCache<K, V> extends LinkedHashMap<K, V> {
  2. private static final int MAX_NODE_NUM = 100;
  3. private int limit;
  4. public SimpleCache() {
  5. this(MAX_NODE_NUM);
  6. }
  7. public SimpleCache(int limit) {
  8. super(limit, 0.75f, true);
  9. this.limit = limit;
  10. }
  11. public V save(K key, V val) {
  12. return put(key, val);
  13. }
  14. public V getOne(K key) {
  15. return get(key);
  16. }
  17. public boolean exists(K key) {
  18. return containsKey(key);
  19. }
  20. /**
  21. * 判断节点数是否超限
  22. * @param eldest
  23. * @return 超限返回 true,否则返回 false
  24. */
  25. @Override
  26. protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
  27. return size() > limit;
  28. }
  29. }
复制代码

测试代码如下:

  1. public class SimpleCacheTest {
  2. @Test
  3. public void test() throws Exception {
  4. SimpleCache<Integer, Integer> cache = new SimpleCache<>(3);
  5. for (int i = 0; i < 10; i++) {
  6. cache.save(i, i * i);
  7. }
  8. System.out.println("插入10个键值对后,缓存内容:");
  9. System.out.println(cache + "\n");
  10. System.out.println("访问键值为7的节点后,缓存内容:");
  11. cache.getOne(7);
  12. System.out.println(cache + "\n");
  13. System.out.println("插入键值为1的键值对后,缓存内容:");
  14. cache.save(1, 1);
  15. System.out.println(cache);
  16. }
  17. }
复制代码

测试结果如下:

151670457400271

在测试代码中,设定缓存大小为3。在向缓存中插入10个键值对后,只有最后3个被保存下来了,其他的都被移除了。然后通过访问键值为7的节点,使得该节点被移到双向链表的最后位置。当我们再次插入一个键值对时,键值为7的节点就不会被移除。

本节作为对前面内的补充,简单介绍了 LinkedHashMap 在其他方面的应用。本节内容及相关代码并不难理解,这里就不在赘述了。

4. 总结

本文从 LinkedHashMap 维护双向链表的角度对 LinkedHashMap 的源码进行了分析,并在文章的结尾基于 LinkedHashMap 实现了一个简单的 Cache。在日常开发中,LinkedHashMap 的使用频率虽不及 HashMap,但它也个重要的实现。在 Java 集合框架中,HashMap、LinkedHashMap 和 TreeMap 三个映射类基于不同的数据结构,并实现了不同的功能。HashMap 底层基于拉链式的散列结构,并在 JDK 1.8 中引入红黑树优化过长链表的问题。基于这样结构,HashMap 可提供高效的增删改查操作。LinkedHashMap 在其之上,通过维护一条双向链表,实现了散列数据结构的有序遍历。TreeMap 底层基于红黑树实现,利用红黑树的性质,实现了键值对排序功能。我在前面几篇文章中,对 HashMap 和 TreeMap 以及他们均使用到的红黑树进行了详细的分析,有兴趣的朋友可以去看看。

到此,本篇文章就写完了,感谢大家的阅读!

附录:映射类文章列表 红黑树详细分析 TreeMap源码分析 HashMap 源码详细分析(JDK1.8)

本文在知识共享许可协议 4.0 下发布,转载请注明出处
作者:coolblog
本文同步发布在我的个人博客:http://www.coolblog.xyz

cc
本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。



回复

使用道具 举报