死磕 java集合之HashMap源码分析

原创
2020/06/26 08:03
阅读数 168

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

简介

HashMap采用key/value存储结构,每个key对应唯一的value,查询和修改的速度都很快,能达到O(1)的平均时间复杂度。它是非线程安全的,且不保证元素存储的顺序。

继承体系

HashMap实现了Cloneable,可以被克隆。

HashMap实现了Serializable,可以被序列化。

HashMap继承自AbstractMap,实现了Map接口,具有Map的所有功能。

存储结构

在Java中,HashMap的实现采用了(数组 + 链表 + 红黑树)的复杂结构,数组的一个元素又称作桶。

在添加元素时,会根据hash值算出元素在数组中的位置,如果该位置没有元素,则直接把元素放置在此处,如果该位置有元素了,则把元素以链表的形式放置在链表的尾部。

当一个链表的元素个数达到一定的数量(且数组的长度达到一定的长度)后,则把链表转化为红黑树,从而提高效率。

数组的查询效率为O(1),链表的查询效率是O(k),红黑树的查询效率是O(log k),k为桶中的元素个数,所以当元素数量非常多的时候,转化为红黑树能极大地提高效率。

源码解析

属性

  
  
  
  1. /**

  2. * 默认的初始容量为16

  3. */

  4. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;


  5. /**

  6. * 最大的容量为2的30次方

  7. */

  8. static final int MAXIMUM_CAPACITY = 1 << 30;


  9. /**

  10. * 默认的装载因子

  11. */

  12. static final float DEFAULT_LOAD_FACTOR = 0.75f;


  13. /**

  14. * 当一个桶中的元素个数大于等于8时进行树化

  15. */

  16. static final int TREEIFY_THRESHOLD = 8;


  17. /**

  18. * 当一个桶中的元素个数小于等于6时把树转化为链表

  19. */

  20. static final int UNTREEIFY_THRESHOLD = 6;


  21. /**

  22. * 当桶的个数达到64的时候才进行树化

  23. */

  24. static final int MIN_TREEIFY_CAPACITY = 64;


  25. /**

  26. * 数组,又叫作桶(bucket)

  27. */

  28. transient Node<K,V>[] table;


  29. /**

  30. * 作为entrySet()的缓存

  31. */

  32. transient Set<Map.Entry<K,V>> entrySet;


  33. /**

  34. * 元素的数量

  35. */

  36. transient int size;


  37. /**

  38. * 修改次数,用于在迭代的时候执行快速失败策略

  39. */

  40. transient int modCount;


  41. /**

  42. * 当桶的使用数量达到多少时进行扩容,threshold = capacity * loadFactor

  43. */

  44. int threshold;


  45. /**

  46. * 装载因子

  47. */

  48. final float loadFactor;

(1)容量

容量为数组的长度,亦即桶的个数,默认为16,最大为2的30次方,当容量达到64时才可以树化。

(2)装载因子

装载因子用来计算容量达到多少时才进行扩容,默认装载因子为0.75。

(3)树化

树化,当容量达到64且链表的长度达到8时进行树化,当链表的长度小于6时反树化。

Node内部类

Node是一个典型的单链表节点,其中,hash用来存储key计算得来的hash值。

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

  2. final int hash;

  3. final K key;

  4. V value;

  5. Node<K,V> next;

  6. }

TreeNode内部类

这是一个神奇的类,它继承自LinkedHashMap中的Entry类,关于LInkedHashMap.Entry这个类我们后面再讲。

TreeNode是一个典型的树型节点,其中,prev是链表中的节点,用于在删除元素的时候可以快速找到它的前置节点。

  
  
  
  1. // 位于HashMap中

  2. static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

  3. TreeNode<K,V> parent; // red-black tree links

  4. TreeNode<K,V> left;

  5. TreeNode<K,V> right;

  6. TreeNode<K,V> prev; // needed to unlink next upon deletion

  7. boolean red;

  8. }


  9. // 位于LinkedHashMap中,典型的双向链表节点

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

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

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

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

  14. }

  15. }

HashMap()构造方法

空参构造方法,全部使用默认值。

  
  
  
  1. public HashMap() {

  2. this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

  3. }

HashMap(int initialCapacity)构造方法

调用HashMap(int initialCapacity, float loadFactor)构造方法,传入默认装载因子。

  
  
  
  1. public HashMap(int initialCapacity) {

  2. this(initialCapacity, DEFAULT_LOAD_FACTOR);

  3. }

HashMap(int initialCapacity)构造方法

判断传入的初始容量和装载因子是否合法,并计算扩容门槛,扩容门槛为传入的初始容量往上取最近的2的n次方。

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

  2. // 检查传入的初始容量是否合法

  3. if (initialCapacity < 0)

  4. throw new IllegalArgumentException("Illegal initial capacity: " +

  5. initialCapacity);

  6. if (initialCapacity > MAXIMUM_CAPACITY)

  7. initialCapacity = MAXIMUM_CAPACITY;

  8. // 检查装载因子是否合法

  9. if (loadFactor <= 0 || Float.isNaN(loadFactor))

  10. throw new IllegalArgumentException("Illegal load factor: " +

  11. loadFactor);

  12. this.loadFactor = loadFactor;

  13. // 计算扩容门槛

  14. this.threshold = tableSizeFor(initialCapacity);

  15. }


  16. static final int tableSizeFor(int cap) {

  17. // 扩容门槛为传入的初始容量往上取最近的2的n次方

  18. int n = cap - 1;

  19. n |= n >>> 1;

  20. n |= n >>> 2;

  21. n |= n >>> 4;

  22. n |= n >>> 8;

  23. n |= n >>> 16;

  24. return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

  25. }

put(K key, V value)方法

添加元素的入口。

  
  
  
  1. public V put(K key, V value) {

  2. // 调用hash(key)计算出key的hash值

  3. return putVal(hash(key), key, value, false, true);

  4. }


  5. static final int hash(Object key) {

  6. int h;

  7. // 如果key为null,则hash值为0,否则调用key的hashCode()方法

  8. // 并让高16位与整个hash异或,这样做是为了使计算出的hash更分散

  9. return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

  10. }


  11. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

  12. boolean evict) {

  13. Node<K, V>[] tab;

  14. Node<K, V> p;

  15. int n, i;

  16. // 如果桶的数量为0,则初始化

  17. if ((tab = table) == null || (n = tab.length) == 0)

  18. // 调用resize()初始化

  19. n = (tab = resize()).length;

  20. // (n - 1) & hash 计算元素在哪个桶中

  21. // 如果这个桶中还没有元素,则把这个元素放在桶中的第一个位置

  22. if ((p = tab[i = (n - 1) & hash]) == null)

  23. // 新建一个节点放在桶中

  24. tab[i] = newNode(hash, key, value, null);

  25. else {

  26. // 如果桶中已经有元素存在了

  27. Node<K, V> e;

  28. K k;

  29. // 如果桶中第一个元素的key与待插入元素的key相同,保存到e中用于后续修改value值

  30. if (p.hash == hash &&

  31. ((k = p.key) == key || (key != null && key.equals(k))))

  32. e = p;

  33. else if (p instanceof TreeNode)

  34. // 如果第一个元素是树节点,则调用树节点的putTreeVal插入元素

  35. e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);

  36. else {

  37. // 遍历这个桶对应的链表,binCount用于存储链表中元素的个数

  38. for (int binCount = 0; ; ++binCount) {

  39. // 如果链表遍历完了都没有找到相同key的元素,说明该key对应的元素不存在,则在链表最后插入一个新节点

  40. if ((e = p.next) == null) {

  41. p.next = newNode(hash, key, value, null);

  42. // 如果插入新节点后链表长度大于8,则判断是否需要树化,因为第一个元素没有加到binCount中,所以这里-1

  43. if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

  44. treeifyBin(tab, hash);

  45. break;

  46. }

  47. // 如果待插入的key在链表中找到了,则退出循环

  48. if (e.hash == hash &&

  49. ((k = e.key) == key || (key != null && key.equals(k))))

  50. break;

  51. p = e;

  52. }

  53. }

  54. // 如果找到了对应key的元素

  55. if (e != null) { // existing mapping for key

  56. // 记录下旧值

  57. V oldValue = e.value;

  58. // 判断是否需要替换旧值

  59. if (!onlyIfAbsent || oldValue == null)

  60. // 替换旧值为新值

  61. e.value = value;

  62. // 在节点被访问后做点什么事,在LinkedHashMap中用到

  63. afterNodeAccess(e);

  64. // 返回旧值

  65. return oldValue;

  66. }

  67. }

  68. // 到这里了说明没有找到元素

  69. // 修改次数加1

  70. ++modCount;

  71. // 元素数量加1,判断是否需要扩容

  72. if (++size > threshold)

  73. // 扩容

  74. resize();

  75. // 在节点插入后做点什么事,在LinkedHashMap中用到

  76. afterNodeInsertion(evict);

  77. // 没找到元素返回null

  78. return null;

  79. }

(1)计算key的hash值;

(2)如果桶(数组)数量为0,则初始化桶;

(3)如果key所在的桶没有元素,则直接插入;

(4)如果key所在的桶中的第一个元素的key与待插入的key相同,说明找到了元素,转后续流程(9)处理;

(5)如果第一个元素是树节点,则调用树节点的putTreeVal()寻找元素或插入树节点;

(6)如果不是以上三种情况,则遍历桶对应的链表查找key是否存在于链表中;

(7)如果找到了对应key的元素,则转后续流程(9)处理;

(8)如果没找到对应key的元素,则在链表最后插入一个新节点并判断是否需要树化;

(9)如果找到了对应key的元素,则判断是否需要替换旧值,并直接返回旧值;

(10)如果插入了元素,则数量加1并判断是否需要扩容;

resize()方法

扩容方法。

  
  
  
  1. final Node<K, V>[] resize() {

  2. // 旧数组

  3. Node<K, V>[] oldTab = table;

  4. // 旧容量

  5. int oldCap = (oldTab == null) ? 0 : oldTab.length;

  6. // 旧扩容门槛

  7. int oldThr = threshold;

  8. int newCap, newThr = 0;

  9. if (oldCap > 0) {

  10. if (oldCap >= MAXIMUM_CAPACITY) {

  11. // 如果旧容量达到了最大容量,则不再进行扩容

  12. threshold = Integer.MAX_VALUE;

  13. return oldTab;

  14. } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

  15. oldCap >= DEFAULT_INITIAL_CAPACITY)

  16. // 如果旧容量的两倍小于最大容量并且旧容量大于默认初始容量(16),则容量扩大为两部,扩容门槛也扩大为两倍

  17. newThr = oldThr << 1; // double threshold

  18. } else if (oldThr > 0) // initial capacity was placed in threshold

  19. // 使用非默认构造方法创建的map,第一次插入元素会走到这里

  20. // 如果旧容量为0且旧扩容门槛大于0,则把新容量赋值为旧门槛

  21. newCap = oldThr;

  22. else { // zero initial threshold signifies using defaults

  23. // 调用默认构造方法创建的map,第一次插入元素会走到这里

  24. // 如果旧容量旧扩容门槛都是0,说明还未初始化过,则初始化容量为默认容量,扩容门槛为默认容量*默认装载因子

  25. newCap = DEFAULT_INITIAL_CAPACITY;

  26. newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

  27. }

  28. if (newThr == 0) {

  29. // 如果新扩容门槛为0,则计算为容量*装载因子,但不能超过最大容量

  30. float ft = (float) newCap * loadFactor;

  31. newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?

  32. (int) ft : Integer.MAX_VALUE);

  33. }

  34. // 赋值扩容门槛为新门槛

  35. threshold = newThr;

  36. // 新建一个新容量的数组

  37. @SuppressWarnings({"rawtypes", "unchecked"})

  38. Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];

  39. // 把桶赋值为新数组

  40. table = newTab;

  41. // 如果旧数组不为空,则搬移元素

  42. if (oldTab != null) {

  43. // 遍历旧数组

  44. for (int j = 0; j < oldCap; ++j) {

  45. Node<K, V> e;

  46. // 如果桶中第一个元素不为空,赋值给e

  47. if ((e = oldTab[j]) != null) {

  48. // 清空旧桶,便于GC回收

  49. oldTab[j] = null;

  50. // 如果这个桶中只有一个元素,则计算它在新桶中的位置并把它搬移到新桶中

  51. // 因为每次都扩容两倍,所以这里的第一个元素搬移到新桶的时候新桶肯定还没有元素

  52. if (e.next == null)

  53. newTab[e.hash & (newCap - 1)] = e;

  54. else if (e instanceof TreeNode)

  55. // 如果第一个元素是树节点,则把这颗树打散成两颗树插入到新桶中去

  56. ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);

  57. else { // preserve order

  58. // 如果这个链表不止一个元素且不是一颗树

  59. // 则分化成两个链表插入到新的桶中去

  60. // 比如,假如原来容量为4,3、7、11、15这四个元素都在三号桶中

  61. // 现在扩容到8,则3和11还是在三号桶,7和15要搬移到七号桶中去

  62. // 也就是分化成了两个链表

  63. Node<K, V> loHead = null, loTail = null;

  64. Node<K, V> hiHead = null, hiTail = null;

  65. Node<K, V> next;

  66. do {

  67. next = e.next;

  68. // (e.hash & oldCap) == 0的元素放在低位链表中

  69. // 比如,3 & 4 == 0

  70. if ((e.hash & oldCap) == 0) {

  71. if (loTail == null)

  72. loHead = e;

  73. else

  74. loTail.next = e;

  75. loTail = e;

  76. } else {

  77. // (e.hash & oldCap) != 0的元素放在高位链表中

  78. // 比如,7 & 4 != 0

  79. if (hiTail == null)

  80. hiHead = e;

  81. else

  82. hiTail.next = e;

  83. hiTail = e;

  84. }

  85. } while ((e = next) != null);

  86. // 遍历完成分化成两个链表了

  87. // 低位链表在新桶中的位置与旧桶一样(即3和11还在三号桶中)

  88. if (loTail != null) {

  89. loTail.next = null;

  90. newTab[j] = loHead;

  91. }

  92. // 高位链表在新桶中的位置正好是原来的位置加上旧容量(即7和15搬移到七号桶了)

  93. if (hiTail != null) {

  94. hiTail.next = null;

  95. newTab[j + oldCap] = hiHead;

  96. }

  97. }

  98. }

  99. }

  100. }

  101. return newTab;

  102. }

(1)如果使用是默认构造方法,则第一次插入元素时初始化为默认值,容量为16,扩容门槛为12;

(2)如果使用的是非默认构造方法,则第一次插入元素时初始化容量等于扩容门槛,扩容门槛在构造方法里等于传入容量向上最近的2的n次方;

(3)如果旧容量大于0,则新容量等于旧容量的2倍,但不超过最大容量2的30次方,新扩容门槛为旧扩容门槛的2倍;

(4)创建一个新容量的桶;

(5)搬移元素,原链表分化成两个链表,低位链表存储在原来桶的位置,高位链表搬移到原来桶的位置加旧容量的位置;

TreeNode.putTreeVal(...)方法

插入元素到红黑树中的方法。

  
  
  
  1. final TreeNode<K, V> putTreeVal(HashMap<K, V> map, Node<K, V>[] tab,

  2. int h, K k, V v) {

  3. Class<?> kc = null;

  4. // 标记是否找到这个key的节点

  5. boolean searched = false;

  6. // 找到树的根节点

  7. TreeNode<K, V> root = (parent != null) ? root() : this;

  8. // 从树的根节点开始遍历

  9. for (TreeNode<K, V> p = root; ; ) {

  10. // dir=direction,标记是在左边还是右边

  11. // ph=p.hash,当前节点的hash值

  12. int dir, ph;

  13. // pk=p.key,当前节点的key值

  14. K pk;

  15. if ((ph = p.hash) > h) {

  16. // 当前hash比目标hash大,说明在左边

  17. dir = -1;

  18. }

  19. else if (ph < h)

  20. // 当前hash比目标hash小,说明在右边

  21. dir = 1;

  22. else if ((pk = p.key) == k || (k != null && k.equals(pk)))

  23. // 两者hash相同且key相等,说明找到了节点,直接返回该节点

  24. // 回到putVal()中判断是否需要修改其value值

  25. return p;

  26. else if ((kc == null &&

  27. // 如果k是Comparable的子类则返回其真实的类,否则返回null

  28. (kc = comparableClassFor(k)) == null) ||

  29. // 如果k和pk不是同样的类型则返回0,否则返回两者比较的结果

  30. (dir = compareComparables(kc, k, pk)) == 0) {

  31. // 这个条件表示两者hash相同但是其中一个不是Comparable类型或者两者类型不同

  32. // 比如key是Object类型,这时可以传String也可以传Integer,两者hash值可能相同

  33. // 在红黑树中把同样hash值的元素存储在同一颗子树,这里相当于找到了这颗子树的顶点

  34. // 从这个顶点分别遍历其左右子树去寻找有没有跟待插入的key相同的元素

  35. if (!searched) {

  36. TreeNode<K, V> q, ch;

  37. searched = true;

  38. // 遍历左右子树找到了直接返回

  39. if (((ch = p.left) != null &&

  40. (q = ch.find(h, k, kc)) != null) ||

  41. ((ch = p.right) != null &&

  42. (q = ch.find(h, k, kc)) != null))

  43. return q;

  44. }

  45. // 如果两者类型相同,再根据它们的内存地址计算hash值进行比较

  46. dir = tieBreakOrder(k, pk);

  47. }


  48. TreeNode<K, V> xp = p;

  49. if ((p = (dir <= 0) ? p.left : p.right) == null) {

  50. // 如果最后确实没找到对应key的元素,则新建一个节点

  51. Node<K, V> xpn = xp.next;

  52. TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn);

  53. if (dir <= 0)

  54. xp.left = x;

  55. else

  56. xp.right = x;

  57. xp.next = x;

  58. x.parent = x.prev = xp;

  59. if (xpn != null)

  60. ((TreeNode<K, V>) xpn).prev = x;

  61. // 插入树节点后平衡

  62. // 把root节点移动到链表的第一个节点

  63. moveRootToFront(tab, balanceInsertion(root, x));

  64. return null;

  65. }

  66. }

  67. }

(1)寻找根节点;

(2)从根节点开始查找;

(3)比较hash值及key值,如果都相同,直接返回,在putVal()方法中决定是否要替换value值;

(4)根据hash值及key值确定在树的左子树还是右子树查找,找到了直接返回;

(5)如果最后没有找到则在树的相应位置插入元素,并做平衡;

treeifyBin()方法

如果插入元素后链表的长度大于等于8则判断是否需要树化。

  
  
  
  1. final void treeifyBin(Node<K, V>[] tab, int hash) {

  2. int n, index;

  3. Node<K, V> e;

  4. if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

  5. // 如果桶数量小于64,直接扩容而不用树化

  6. // 因为扩容之后,链表会分化成两个链表,达到减少元素的作用

  7. // 当然也不一定,比如容量为4,里面存的全是除以4余数等于3的元素

  8. // 这样即使扩容也无法减少链表的长度

  9. resize();

  10. else if ((e = tab[index = (n - 1) & hash]) != null) {

  11. TreeNode<K, V> hd = null, tl = null;

  12. // 把所有节点换成树节点

  13. do {

  14. TreeNode<K, V> p = replacementTreeNode(e, null);

  15. if (tl == null)

  16. hd = p;

  17. else {

  18. p.prev = tl;

  19. tl.next = p;

  20. }

  21. tl = p;

  22. } while ((e = e.next) != null);

  23. // 如果进入过上面的循环,则从头节点开始树化

  24. if ((tab[index] = hd) != null)

  25. hd.treeify(tab);

  26. }

  27. }

TreeNode.treeify()方法

真正树化的方法。

  
  
  
  1. final void treeify(Node<K, V>[] tab) {

  2. TreeNode<K, V> root = null;

  3. for (TreeNode<K, V> x = this, next; x != null; x = next) {

  4. next = (TreeNode<K, V>) x.next;

  5. x.left = x.right = null;

  6. // 第一个元素作为根节点且为黑节点,其它元素依次插入到树中再做平衡

  7. if (root == null) {

  8. x.parent = null;

  9. x.red = false;

  10. root = x;

  11. } else {

  12. K k = x.key;

  13. int h = x.hash;

  14. Class<?> kc = null;

  15. // 从根节点查找元素插入的位置

  16. for (TreeNode<K, V> p = root; ; ) {

  17. int dir, ph;

  18. K pk = p.key;

  19. if ((ph = p.hash) > h)

  20. dir = -1;

  21. else if (ph < h)

  22. dir = 1;

  23. else if ((kc == null &&

  24. (kc = comparableClassFor(k)) == null) ||

  25. (dir = compareComparables(kc, k, pk)) == 0)

  26. dir = tieBreakOrder(k, pk);


  27. // 如果最后没找到元素,则插入

  28. TreeNode<K, V> xp = p;

  29. if ((p = (dir <= 0) ? p.left : p.right) == null) {

  30. x.parent = xp;

  31. if (dir <= 0)

  32. xp.left = x;

  33. else

  34. xp.right = x;

  35. // 插入后平衡,默认插入的是红节点,在balanceInsertion()方法里

  36. root = balanceInsertion(root, x);

  37. break;

  38. }

  39. }

  40. }

  41. }

  42. // 把根节点移动到链表的头节点,因为经过平衡之后原来的第一个元素不一定是根节点了

  43. moveRootToFront(tab, root);

  44. }

(1)从链表的第一个元素开始遍历;

(2)将第一个元素作为根节点;

(3)其它元素依次插入到红黑树中,再做平衡;

(4)将根节点移到链表第一元素的位置(因为平衡的时候根节点会改变);

get(Object key)方法

  
  
  
  1. public V get(Object key) {

  2. Node<K, V> e;

  3. return (e = getNode(hash(key), key)) == null ? null : e.value;

  4. }


  5. final Node<K, V> getNode(int hash, Object key) {

  6. Node<K, V>[] tab;

  7. Node<K, V> first, e;

  8. int n;

  9. K k;

  10. // 如果桶的数量大于0并且待查找的key所在的桶的第一个元素不为空

  11. if ((tab = table) != null && (n = tab.length) > 0 &&

  12. (first = tab[(n - 1) & hash]) != null) {

  13. // 检查第一个元素是不是要查的元素,如果是直接返回

  14. if (first.hash == hash && // always check first node

  15. ((k = first.key) == key || (key != null && key.equals(k))))

  16. return first;

  17. if ((e = first.next) != null) {

  18. // 如果第一个元素是树节点,则按树的方式查找

  19. if (first instanceof TreeNode)

  20. return ((TreeNode<K, V>) first).getTreeNode(hash, key);


  21. // 否则就遍历整个链表查找该元素

  22. do {

  23. if (e.hash == hash &&

  24. ((k = e.key) == key || (key != null && key.equals(k))))

  25. return e;

  26. } while ((e = e.next) != null);

  27. }

  28. }

  29. return null;

  30. }

(1)计算key的hash值;

(2)找到key所在的桶及其第一个元素;

(3)如果第一个元素的key等于待查找的key,直接返回;

(4)如果第一个元素是树节点就按树的方式来查找,否则按链表方式查找;

TreeNode.getTreeNode(int h, Object k)方法

  
  
  
  1. final TreeNode<K, V> getTreeNode(int h, Object k) {

  2. // 从树的根节点开始查找

  3. return ((parent != null) ? root() : this).find(h, k, null);

  4. }


  5. final TreeNode<K, V> find(int h, Object k, Class<?> kc) {

  6. TreeNode<K, V> p = this;

  7. do {

  8. int ph, dir;

  9. K pk;

  10. TreeNode<K, V> pl = p.left, pr = p.right, q;

  11. if ((ph = p.hash) > h)

  12. // 左子树

  13. p = pl;

  14. else if (ph < h)

  15. // 右子树

  16. p = pr;

  17. else if ((pk = p.key) == k || (k != null && k.equals(pk)))

  18. // 找到了直接返回

  19. return p;

  20. else if (pl == null)

  21. // hash相同但key不同,左子树为空查右子树

  22. p = pr;

  23. else if (pr == null)

  24. // 右子树为空查左子树

  25. p = pl;

  26. else if ((kc != null ||

  27. (kc = comparableClassFor(k)) != null) &&

  28. (dir = compareComparables(kc, k, pk)) != 0)

  29. // 通过compare方法比较key值的大小决定使用左子树还是右子树

  30. p = (dir < 0) ? pl : pr;

  31. else if ((q = pr.find(h, k, kc)) != null)

  32. // 如果以上条件都不通过,则尝试在右子树查找

  33. return q;

  34. else

  35. // 都没找到就在左子树查找

  36. p = pl;

  37. } while (p != null);

  38. return null;

  39. }

经典二叉查找树的查找过程,先根据hash值比较,再根据key值比较决定是查左子树还是右子树。

remove(Object key)方法

  
  
  
  1. public V remove(Object key) {

  2. Node<K, V> e;

  3. return (e = removeNode(hash(key), key, null, false, true)) == null ?

  4. null : e.value;

  5. }


  6. final Node<K, V> removeNode(int hash, Object key, Object value,

  7. boolean matchValue, boolean movable) {

  8. Node<K, V>[] tab;

  9. Node<K, V> p;

  10. int n, index;

  11. // 如果桶的数量大于0且待删除的元素所在的桶的第一个元素不为空

  12. if ((tab = table) != null && (n = tab.length) > 0 &&

  13. (p = tab[index = (n - 1) & hash]) != null) {

  14. Node<K, V> node = null, e;

  15. K k;

  16. V v;

  17. if (p.hash == hash &&

  18. ((k = p.key) == key || (key != null && key.equals(k))))

  19. // 如果第一个元素正好就是要找的元素,赋值给node变量后续删除使用

  20. node = p;

  21. else if ((e = p.next) != null) {

  22. if (p instanceof TreeNode)

  23. // 如果第一个元素是树节点,则以树的方式查找节点

  24. node = ((TreeNode<K, V>) p).getTreeNode(hash, key);

  25. else {

  26. // 否则遍历整个链表查找元素

  27. do {

  28. if (e.hash == hash &&

  29. ((k = e.key) == key ||

  30. (key != null && key.equals(k)))) {

  31. node = e;

  32. break;

  33. }

  34. p = e;

  35. } while ((e = e.next) != null);

  36. }

  37. }

  38. // 如果找到了元素,则看参数是否需要匹配value值,如果不需要匹配直接删除,如果需要匹配则看value值是否与传入的value相等

  39. if (node != null && (!matchValue || (v = node.value) == value ||

  40. (value != null && value.equals(v)))) {

  41. if (node instanceof TreeNode)

  42. // 如果是树节点,调用树的删除方法(以node调用的,是删除自己)

  43. ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);

  44. else if (node == p)

  45. // 如果待删除的元素是第一个元素,则把第二个元素移到第一的位置

  46. tab[index] = node.next;

  47. else

  48. // 否则删除node节点

  49. p.next = node.next;

  50. ++modCount;

  51. --size;

  52. // 删除节点后置处理

  53. afterNodeRemoval(node);

  54. return node;

  55. }

  56. }

  57. return null;

  58. }

(1)先查找元素所在的节点;

(2)如果找到的节点是树节点,则按树的移除节点处理;

(3)如果找到的节点是桶中的第一个节点,则把第二个节点移到第一的位置;

(4)否则按链表删除节点处理;

(5)修改size,调用移除节点后置处理等;

TreeNode.removeTreeNode(...)方法

  
  
  
  1. final void removeTreeNode(HashMap<K, V> map, Node<K, V>[] tab,

  2. boolean movable) {

  3. int n;

  4. // 如果桶的数量为0直接返回

  5. if (tab == null || (n = tab.length) == 0)

  6. return;

  7. // 节点在桶中的索引

  8. int index = (n - 1) & hash;

  9. // 第一个节点,根节点,根左子节点

  10. TreeNode<K, V> first = (TreeNode<K, V>) tab[index], root = first, rl;

  11. // 后继节点,前置节点

  12. TreeNode<