集合番@HashMap一文通(1.8版)

阅读 410
收藏 27
2017-08-03
原文链接:www.zybuluo.com

1.HashMap1.7的不足

  • 1.7采用数组+链表的结构,即使哈希函数取得再好,也很难达到元素百分百均匀分布
  • 当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表,这个时候 HashMap 就相当于一个单链表,假如单链表有 n 个元素,遍历的时间复杂度就是 O(n),完全失去了它的优势

2.HashMap1.8的优化

  • HashMap1.8版本基于 集合番@HashMap一文通(1.7版) 进行优化,这里只谈论改进的地方
  • 改进最大不同在于 : 基于提高性能的目的,1.7采用数组+链表的结构,而1.8采用了更高效的数组+链表+红黑树(查找时间复杂度为 O(logn))的结构
  • 在笔者看来,由于底层数据结构变动,实际上HashMap1.8几乎被重写,可以认为是个新的类
  • 1.8版本的红黑树实现跟TreeMap基本一致(情况一样,只是代码有些差别)读者可参见 集合番@TreeMap一文通(1.7版)

3.HashMap的数据结构

  • 重要新增变量
  1. /**
  2. * The bin count threshold for using a tree rather than list for a bin.
  3. * Bins are converted to trees when adding an element to a bin with at least this many nodes.
  4. * The value must be greater than 2 and should be at least 8 to mesh with assumptions in tree
  5. * removal about conversion back to plain bins upon shrinkage.
  6. * 一个桶的树化阈值:
  7. * 1.当桶中元素个数超过这个值时,会将链表转换为红黑树
  8. * 2.该值必须大于2且至少为8,避免频繁转换导致效率不高
  9. * 3.默认为8,即当新增元素造成链表长度变成8时,自动转换为红黑树
  10. */
  11. static final int TREEIFY_THRESHOLD = 8;
  12. /**
  13. * The bin count threshold for untreeifying a (split) bin during a
  14. * resize operation. Should be less than TREEIFY_THRESHOLD, and at
  15. * most 6 to mesh with shrinkage detection under removal.
  16. * 一个树的链表还原阈值:
  17. * 1.当扩容时,桶中元素个数小于这个值,就会把树形的桶元素还原(切分)为链表
  18. * 2.该值应小于TREEIFY_THRESHOLD且至少为 6,避免频繁转换导致效率不高
  19. */
  20. static final int UNTREEIFY_THRESHOLD = 6;
  21. /**
  22. * The smallest table capacity for which bins may be treeified.
  23. * (Otherwise the table is resized if too many nodes in a bin.)
  24. * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
  25. * between resizing and treeification thresholds.
  26. * 哈希表的最小树形化容量:
  27. * 1.当哈希表中的容量大于该值时,表中的桶才能进行树形化,否则桶内元素太多时会扩容,而不是树形化
  28. * 2.为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD
  29. */
  30. static final int MIN_TREEIFY_CAPACITY = 64;
  • 构造器
  1. /**
  2. * 1.7版本
  3. */
  4. public HashMap(int initialCapacity, float loadFactor) {
  5. if (initialCapacity < 0)
  6. throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
  7. if (initialCapacity > MAXIMUM_CAPACITY)
  8. initialCapacity = MAXIMUM_CAPACITY;
  9. if (loadFactor <= 0 || Float.isNaN(loadFactor))
  10. throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
  11. this.loadFactor = loadFactor;
  12. //以下是与1.8不同之处
  13. // Find a power of 2 >= initialCapacity 效果等同于 1.8的tableSizeFor()
  14. int capacity = 1;
  15. while (capacity < initialCapacity)
  16. capacity <<= 1;
  17. threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
  18. table = new Entry[capacity];
  19. useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
  20. init();
  21. }
  22. /**
  23. * 1.8版本 区别于1.7
  24. * 1.构造器阶段并没有初始化数组(而是改成在第一次put时执行resize初始化数组)
  25. * 2.容量根据阈值进行换算而不是阈值根据容量再换算(initial capacity was placed in threshold)
  26. */
  27. public HashMap(int initialCapacity, float loadFactor) {
  28. if (initialCapacity < 0)
  29. throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
  30. if (initialCapacity > MAXIMUM_CAPACITY)
  31. initialCapacity = MAXIMUM_CAPACITY;
  32. if (loadFactor <= 0 || Float.isNaN(loadFactor))
  33. throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
  34. this.loadFactor = loadFactor;
  35. //构造器阶段阈值等同于容量,保证为2次幂(resize时生效)
  36. this.threshold = tableSizeFor(initialCapacity);
  37. }
  • Node
  1. /**
  2. * Basic hash bin node, used for most entries. (See below for
  3. * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
  4. * 1.8中将Entry改成Node(内部结构不变)
  5. * 虽然只是改了名字,但名字的变更体现出HashMap对于`节点`概念的重视
  6. */
  7. static class Node<K,V> implements Map.Entry<K,V> {
  8. final int hash;//新增final属性,表明hash值也不可变了,更加严谨
  9. final K key;
  10. V value;
  11. Node<K,V> next;//单向链表
  12. Node(int hash, K key, V value, Node<K,V> next) {
  13. this.hash = hash;
  14. this.key = key;
  15. this.value = value;
  16. this.next = next;
  17. }
  18. ...
  19. }
  • TreeNode
  1. /**
  2. * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn extends Node)
  3. * so can be used as extension of either regular or linked node.
  4. * 红黑树节点 相比于TreeMap,
  5. * 1.增加pre来记录前一个节点
  6. * 2.继承LinkedHashMap.Entry<K,V>,而LinkedHashMap.Entry<K,V>又继承HashMap.Node:
  7. * 1.拥有了Node和链表Node的所有功能
  8. * 2.具有额外6个属性Entry<K,V> before, after;final int hash;final K key;V value;Node<K,V> next;
  9. */
  10. static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
  11. TreeNode<K,V> parent; // 父节点
  12. TreeNode<K,V> left;//左子节点
  13. TreeNode<K,V> right;//右子节点
  14. TreeNode<K,V> prev; // 前一个元素的节点
  15. boolean red;//是否是红节点
  16. TreeNode(int hash, K key, V val, Node<K,V> next) {
  17. super(hash, key, val, next);
  18. }
  19. ...
  20. }
  21. /**
  22. * LinkedHashMap.Entry的实现
  23. * HashMap.Node subclass for normal LinkedHashMap entries.
  24. * 可以发现,最终TreeNode还是继承了HashMap.Node的所有功能,底层实现还是Node
  25. */
  26. static class Entry<K,V> extends HashMap.Node<K,V> {
  27. Entry<K,V> before, after;
  28. Entry(int hash, K key, V value, Node<K,V> next) {
  29. super(hash, key, value, next);
  30. }
  31. }

3.HashMap1.8的新增方法解析

3.1 tableSizeFor方法解析

  1. /**
  2. * Returns a power of two size for the given target capacity.
  3. * 方法的意义在于 找到大于等于指定容量(capacity)参数的2次幂
  4. */
  5. static final int tableSizeFor(int cap) {
  6. int n = cap - 1;//cap-1在于要变成都是1的这种情况,防止变两倍 [实例论证3]
  7. //一个数介于邻近的两个2次幂之间时,这个数从高位出现第一个1的位置与离它最近的且小于它的2次幂的高位1的位置是一致
  8. //[实例论证1]
  9. // >>> 表示无符号向右移动N位 ; | 表示与操作:任何一个数与1进行与操作,结果都是1
  10. //算法论证[实例论证2] : 此算法最重要是找到距离n最近且大于n的二次幂-1的值(即二进制都是1的值)
  11. n |= n >>> 1;
  12. n |= n >>> 2;
  13. n |= n >>> 4;
  14. n |= n >>> 8;
  15. n |= n >>> 16;
  16. //此时n+1一定是cap的2次幂
  17. //从高位第一个出现1的位置开始向右连续32位时已经超越了int的最大值,所以不用在进行位移操作,只到16位即可
  18. return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;//二次幂,但最小为1
  19. }
  • 实例论证1
  • 论证:一个数介于邻近的两个2次幂之间时,这个数从高位出现第一个1的位置与离它最近的且小于它的2次幂的高位1的位置是一致
  • 假设我们要寻找的数是离9最近的且大于它的2次幂,可知该值应为2^4=16
    同时再找到离它最近且小于它的2次幂,可知该值应为2^3=8
    • 8的2进制: 0000 1000
    • 9的2进制: 0000 1001
    • 16的2进制: 0001 0000
      根据以上读者是否发现,9从高位开始第一次出现的位置1与8是一致的,因此可得结论:
      一个数介于邻近的两个2次幂之间时,这个数从高位出现第一个1的位置与离它最近的且小于它的2次幂的高位1的位置是一致
  • 实例论证2
  • 论证:找到距离n最近且大于n的二次幂-1的值
  • 假设我们要寻找离17最近且比他大的2次幂,可知该值应该是2^6=32,下面根据算法可推算出如下过程
    QQ截图20170802143421.png-14.2kB注意1的填充
    • 首先32 = 2^6 = 0010 0000 = 0001 1111 + 0000 0001 = 31 + 1
    • 由图和上面的公式可知,此算法能有效的找到距离n最近且大于n的二次幂-1的值(即二进制都是1的值),或者说是 n从最高位开始后面全是1的值,之后+1即可得到距离n最近且大于n的二次幂
    • 之所有每次位移会2次幂级别的变动,是因为第一次右移1位且与操作后高位2位均为1,所以此次操作是向右位移2位,下次就是高4位都为1,即变动x位是根据位运算之后高x位已经有几个1决定的,最终是要利用任何一个数与1进行与操作,结果都是1的特性把所有位置都变成1
  • 实例论证3
  • 论证:cap-1在于要变成都是1的这种情况,防止变两倍
  • 2^0=1=0000 0001,而该值无论右移1,2,4,8,16位后与本身与操作,依然还是1,没有什么效果
  • 如果一个数恰恰本身就是2的幂的时候,如果不进行减1操作,直接右移的话会导致最后求得的值扩大一倍,比如直接取4(0100),后面位全部填充1可得7 (0111),而7+1=8,即变成2倍,显然不符合我们的预期要求

3.2 putVal方法解析

  1. public V put(K key, V value) {
  2. return putVal(hash(key), key, value, false, true);
  3. }
  4. /**
  5. * Implements Map.put and related methods
  6. * 新增键值对
  7. * @param hash hash for key
  8. * @param key the key
  9. * @param value the value to put
  10. * @param onlyIfAbsent if true, don't change existing value
  11. * @param evict if false, the table is in creation mode.
  12. * @return previous value, or null if none
  13. */
  14. //注意 不可以被继承重载 如果使用hashMap的方式的话
  15. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
  16. Node<K, V>[] tab;
  17. Node<K, V> p;
  18. int n, i;
  19. //当数组为空时
  20. if ((tab = table) == null || (n = tab.length) == 0) {
  21. n = (tab = resize()).length;//当初始化或者当前数组长度为0时,需要重新resize并返回新的长度
  22. }
  23. //相当于通过 h & (length-1) 计算下标并获取元素
  24. if ((p = tab[i = (n - 1) & hash]) == null){
  25. //若当前下标位置空置(即该key不存在),就新建一个普通(non-tree)节点
  26. tab[i] = newNode(hash, key, value, null);
  27. }else {
  28. //当该key存在或者发生hash冲突时
  29. Node<K,V> e; K k;
  30. //若在数组中通过hash和equals比较能够直接找到该值,就覆盖旧值
  31. //即当前桶即非链表也非红黑树
  32. if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){
  33. e = p;//覆盖
  34. }
  35. //否则需要先判断节点是否是红黑树节点
  36. else if (p instanceof TreeNode){//若是红黑树类型,执行树节点putTreeVal操作
  37. e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  38. }
  39. else {
  40. //此时发生了冲突
  41. for (int binCount = 0; ; ++binCount) {
  42. //如果此时的桶还不是链表,需要转变为链表 或者 如果在链表中没有,那就新增一个节点
  43. if ((e = p.next) == null) {
  44. //注意链表插入时1.7与1.8是不同的
  45. //1.7:是头插入法,后来的留在数组上,先来的链在尾上(遍历时是先进后出)
  46. //1.8:是尾插入法,先来的留在数组上,后来的链在尾上(遍历时是先进先出)
  47. p.next = newNode(hash, key, value, null);
  48. //如果桶的链表长度>=桶的树化阈值,需要将链表转变为红黑树
  49. //这里需要注意:是先新增元素之后再判断树化条件,而不是先树化再新增
  50. if (binCount >= TREEIFY_THRESHOLD - 1)
  51. treeifyBin(tab, hash); //当前桶树化
  52. break;
  53. }
  54. //如果在链表中已经存在该值,就覆盖旧值
  55. if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
  56. break;
  57. p = e;
  58. }
  59. }
  60. //原则:用新值覆盖旧值
  61. if (e != null) { // existing mapping for key
  62. V oldValue = e.value;
  63. //onlyIfAbsent 若是true,不允许覆盖
  64. if (!onlyIfAbsent || oldValue == null)
  65. e.value = value;
  66. afterNodeAccess(e);//相当于1.7的afterNodeAccess,LinkedHashMap专用,用于有序控制
  67. return oldValue;
  68. }
  69. }
  70. ++modCount;
  71. if (++size > threshold)//超过阈值就扩容
  72. resize();
  73. afterNodeInsertion(evict);//LinkedHashMap专用,用于删除最旧元素 (remove eldest)
  74. return null;
  75. }
  76. // Create a regular (non-tree) node 创建一个普通的非树节点
  77. Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
  78. return new Node<>(hash, key, value, next);
  79. }

HashMap1.8版本存储流程图

3.3 resize方法解析

  1. /**
  2. * Initializes or doubles table size. If null, allocates in accord with initial capacity
  3. * target held in field threshold. Otherwise, because we are using power-of-two expansion,
  4. * the elements from each bin must either stay at same index, or move with a power of two
  5. * offset in the new table.
  6. * 初始化Map或2倍扩容,且会均匀的把之前的冲突的节点分散到新的桶中
  7. * 当Map为空时,将分配与阈值一样大小的容量
  8. * 当Map不为空时,由于2次幂扩容,元素位置会产生两种情况
  9. * 1.要么元素所在位置不变
  10. * 2.要么元素所在位置变动:向右位移2次幂位置
  11. * 注意:由于1.8中容量是根据阈值得来的,因此读者会在1.8中看到很多对阈值的判断和处理,这点一定要清楚
  12. * @return the table
  13. */
  14. final Node<K,V>[] resize() {
  15. Node<K,V>[] oldTab = table;//由于新数组会覆盖旧数组,所以要临时先备份一份,用于对新数组重新赋值
  16. int oldCap = (oldTab == null) ? 0 : oldTab.length;
  17. int oldThr = threshold;
  18. int newCap, newThr = 0;
  19. if (oldCap > 0) {//当Map不为空时
  20. //临界处理:最大值
  21. if (oldCap >= MAXIMUM_CAPACITY) {
  22. threshold = Integer.MAX_VALUE;//最大值其实是Integer的最大值
  23. return oldTab;
  24. }
  25. //若2倍容量 < MAXIMUM_CAPACITY 同时 原容量>=默认容量(即16),那么就扩容2倍
  26. else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
  27. newThr = oldThr << 1; // double threshold 阈值直接两倍(容量都是根据阈值来的)
  28. } else if (oldThr > 0){//当Map为空时,需要判断阈值是否>0
  29. newCap = oldThr;//阈值即新容量(注意:初始化时候就是执行该操作完成容量赋值)
  30. // initial capacity was placed in threshold(容量都是根据阈值来的)
  31. } else {
  32. //当Map为空,且阈值不是大于0(即无效阈值),那么就使用默认值
  33. // zero initial threshold signifies using defaults
  34. newCap = DEFAULT_INITIAL_CAPACITY;//1 << 4 = 16
  35. newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//0.75 * 16 = 12
  36. }
  37. //当新阈值没有被重置时,需要根据 新容量和负载因子 重新计算出新的阈值
  38. //注意:初始化的时候,阈值会被重置,即此时 阈值!=容量 ,容量已经在(oldThr > 0)时重置过了
  39. if (newThr == 0) {
  40. //等同于1.7版本:threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
  41. float ft = (float)newCap * loadFactor;
  42. newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  43. (int)ft : Integer.MAX_VALUE);
  44. }
  45. threshold = newThr;//重置给真实阈值
  46. @SuppressWarnings({"rawtypes","unchecked"})
  47. Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建一个新容量的Node数组
  48. table = newTab;//覆盖原数组(第一行已经备份了)
  49. //当原数组非空,需要对新数组重新填充
  50. if (oldTab != null) {
  51. //遍历
  52. for (int j = 0; j < oldCap; ++j) {
  53. Node<K,V> e;//用于备份当前节点
  54. //若该数组下标位置非空
  55. if ((e = oldTab[j]) != null) {
  56. oldTab[j] = null;//先把原数组的当前位置清空,因为已经备份了 help gc
  57. if (e.next == null)//当前桶即非链表也非红黑树
  58. newTab[e.hash & (newCap - 1)] = e;//位置可能不变或移动2次幂,跟newCap-1有关
  59. else if (e instanceof TreeNode)//若当前桶是树节点,需要对树进行切分
  60. ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  61. else { // preserve order 当前桶是链表,要保持顺序 1.7的会倒置
  62. //扩容后,新数组中的链表顺序依然与旧数组中的链表顺序保持一致!!!
  63. Node<K,V> loHead = null, loTail = null;//lo=low,表示低位(即数组前半部分的链表)
  64. Node<K,V> hiHead = null, hiTail = null;//hi=high,表示高位(即数组后半部分的链表)
  65. Node<K,V> next;
  66. //遍历当前桶的链表
  67. //1.8:是尾插入法,先来的留在数组上,后来的链在尾上(遍历时是先进先出)
  68. do {
  69. next = e.next;
  70. //根据e.hash & oldCap是否为零将原链表拆分成2个链表
  71. //判断当前位置是否发生变动 0则没变 即保留在原链表中不需要移动
  72. if ((e.hash & oldCap) == 0) {
  73. //原索引 在数组前半部分处理
  74. //若队尾为空,当前元素即是队首元素(也就是第一个插入的元素),保证先进先出
  75. if (loTail == null)
  76. loHead = e;
  77. else
  78. //若队尾不为空,当前元素链接到原队尾元素后面,保证先进先出
  79. loTail.next = e;
  80. loTail = e;//为了保证插入顺序不变,当前元素都需先设置为队尾元素
  81. }
  82. //原索引+oldCap 否则移动到"原索引+oldCap"的新链表中
  83. else {
  84. //在数组后半部分处理
  85. if (hiTail == null)
  86. hiHead = e;
  87. else
  88. hiTail.next = e;
  89. hiTail = e;//为了保证插入顺序不变,当前元素都需先设置为队尾元素
  90. }
  91. } while ((e = next) != null);
  92. //原索引放到原桶中
  93. if (loTail != null) {//如果队尾元素非空
  94. loTail.next = null;//loTail此时就是队尾元素
  95. newTab[j] = loHead;//队首是放在数组里面的
  96. }
  97. //原索引+oldCap放到新桶中
  98. if (hiTail != null) {//如果队尾元素非空
  99. hiTail.next = null;//hiTail此时就是队尾元素
  100. newTab[j + oldCap] = hiHead;//队首是放在数组里面的
  101. }
  102. }
  103. }
  104. }
  105. }
  106. return newTab;
  107. }
  • 为何1.8在resize时不需要重新计算索引下标?
  • 注意:是不需要计算索引下标,节点的Hash值是不会发生变化的!!!
  • &运算的定义:两位同时为"1",结果才为"1",否则为0
  • 首先,我们先根据下标计算公式得出扩容前后索引的变化
    QQ截图20170803134943.png-11.2kB
  • 根据图片可知,扩容后的21的索引下标比扩容前的索引下标多了一个1,且这个1位于newCap-1的掩码最高位
  • 结论:元素在重新计算hash后,因为n变为2倍,那么n-1的mask范围在高位多1bit,即多了个原容量的距离
  • 优化:无需重新计算Hash,节省了时间,新索引=原索引+原容量
  • 那么问题来了,e.hash & oldCap 从何而来???
  • 作用:确认newCap-1最高位对应的hash(key)位是0还是1
  • 由于扩容前后hash不变,由容量2次幂index=(n-1)&hash 可知:
    新的index的决定因素为:(newCap-1)二进制最高位对应的hash位上是0还是1
  • 因此源码作者巧妙的拉关系,以"oldCap等价于newTab的(n-1)的最高位"进而得出e.hash & oldCap
    QQ截图20170803143331.png-10.5kB
  • 优化:由于所计算的hash(key)位是1是0可以认为是随机的,所以将一个冲突长链表"均分"成了两个链表,减少碰撞

3.4 treeifyBin方法解析

  1. /**
  2. * Replaces all linked nodes in bin at index for given hash unless
  3. * table is too small, in which case resizes instead.
  4. * 桶内链表树化:将桶内所有的链表节点替换成红黑树节点,当元素数量不够树化时会重新resize
  5. * 注意:不是整个Map转换,只是当前桶!
  6. */
  7. final void treeifyBin(Node<K,V>[] tab, int hash) {
  8. int n, index; Node<K,V> e;
  9. //当数组为空 或者 数组长度 < 树化阈值(64)时需要执行resize方法,重新决定内部的数据结构类型
  10. if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
  11. resize();
  12. //否则,需要树化
  13. else if ((e = tab[index = (n - 1) & hash]) != null) {
  14. TreeNode<K,V> hd = null, tl = null;//hd指的是head,tl指的是tail,分别指向红黑树的头、尾节点
  15. //从链表头节点开始遍历链表,头节点是存放在数组中的
  16. do {
  17. //新建一个树形节点,内容和当前链表节点e保持一致
  18. //此时next默认为null,会在后面按顺序重新对next赋值
  19. TreeNode<K,V> p = replacementTreeNode(e, null);
  20. if (tl == null)//当尾节点为空,即当前节点应为头节点(因为就这一个节点)
  21. hd = p;
  22. else {
  23. p.prev = tl;//prev被赋值,主要是记录当前节点的上一个节点
  24. tl.next = p;//p指向之前尾节点的next,保持插入顺序
  25. }
  26. tl = p;//当前节点设置为尾节点,保持插入顺序
  27. } while ((e = e.next) != null);
  28. //桶内第一个元素即链表头节点,并放在数组中
  29. if ((tab[index] = hd) != null)
  30. hd.treeify(tab);//从头节点开始遍历,将整个桶树化
  31. //注意头节点并不一定是树的根节点:树化后的根节点会重新设置为头节点,即tab[index]=root
  32. //具体参见moveRootToFront()
  33. }
  34. }
  35. // For treeifyBin 新建一个树形节点
  36. TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
  37. return new TreeNode<>(p.hash, p.key, p.value, next);
  38. }
  39. /**
  40. * Forms tree of the nodes linked from this node.
  41. * 塑造红黑树
  42. * @return root of tree 这里比较有意思,明明时void但有注释@return,不知大神们何意
  43. */
  44. final void treeify(Node<K,V>[] tab) {
  45. TreeNode<K,V> root = null;//根节点需要排序后重新设置(之前链表的头节点不一定是树的根节点)
  46. //this指的是当前二叉树的头节点,从头节点开始遍历
  47. for (TreeNode<K,V> x = this, next; x != null; x = next) {
  48. next = (TreeNode<K,V>)x.next;
  49. x.left = x.right = null;
  50. //当根节点为空时,先设置根节点为黑色,同时当前节点先当作根节点(即自上而下插入)
  51. if (root == null) {
  52. x.parent = null;
  53. x.red = false;//红黑树的根节点为黑色
  54. root = x;
  55. }
  56. else {
  57. //后面进入循环走的逻辑,x 指向树中的某个节点
  58. K k = x.key;
  59. int h = x.hash;
  60. Class<?> kc = null;
  61. //重新循环,从根节点开始,遍历所有节点与当前节点x比较,重新调整位置,类似冒泡排序
  62. for (TreeNode<K,V> p = root;;) {
  63. int dir, ph;
  64. K pk = p.key;
  65. if ((ph = p.hash) > h)//如果比较节点的hash比当前节点的hash大,查左子树
  66. dir = -1;
  67. else if (ph < h)
  68. dir = 1;//如果比较节点的hash比当前节点的hash小,查右子树
  69. else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
  70. (dir = compareComparables(kc, k, pk)) == 0 )
  71. //tieBreakOrder 用于hash相同时且key无法比较时,直接根据引用比较
  72. //这里指的是如果当前比较节点的哈希值比x大,返回-1,否则返回1
  73. dir = tieBreakOrder(k, pk);
  74. //经过前面的计算,得到了当前节点和要插入节点x的一个大小关系
  75. //如果当前比较节点的哈希值比x大,x就是左子节点,否则x是右子节点
  76. TreeNode<K,V> xp = p;
  77. if ((p = (dir <= 0) ? p.left : p.right) == null) {
  78. x.parent = xp;//把当前节点变成x的父节点
  79. if (dir <= 0)
  80. xp.left = x;
  81. else
  82. xp.right = x;
  83. root = balanceInsertion(root, x);
  84. break;
  85. }
  86. }
  87. }
  88. }
  89. moveRootToFront(tab, root);//将根节点设置为头节点
  90. }

3.5 putTreeVal方法解析

  1. /**
  2. * Tree version of putVal. 当桶内为红黑树时,查找该节点,
  3. * 若该节点不存在就新增,返回null
  4. * 若当前节点存在,返回当前节点,用于之后的值覆盖操作
  5. */
  6. //this, tab, hash, key, newValue
  7. final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {
  8. Class<?> kc = null;
  9. boolean searched = false;
  10. TreeNode<K,V> root = (parent != null) ? root() : this;//如果当前node非根节点,需要向上溯源找到根节点
  11. //双重for循环,确定节点位置
  12. for (TreeNode<K,V> p = root;;) {//从根节点开始遍历,确定键值对的位置
  13. int dir, ph; K pk;
  14. if ((ph = p.hash) > h)//对比当前节点和 比较节点的hash大小
  15. dir = -1;// 比较节点hash > 当前节点hash 找左子树
  16. else if (ph < h)
  17. dir = 1;// 比较节点hash < 当前节点hash 找右子树
  18. else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
  19. return p;//如果该节点已经存在,直接返回该节点即可
  20. else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
  21. (dir = compareComparables(kc, k, pk)) == 0) {
  22. //如果当前节点和要添加的节点哈希值相等,但是两个节点的键不是一个类,只能挨个对比左右子节点
  23. if (!searched) {
  24. TreeNode<K,V> q, ch;
  25. searched = true;
  26. //左查 or 右查
  27. if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) ||
  28. ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null))
  29. return q;
  30. }
  31. dir = tieBreakOrder(k, pk);
  32. }
  33. //经过前面的计算,得到了比较节点p和要插入节点x的一个大小关系
  34. //如果比较节点p的哈希值比x大,x就是左子节点,否则x是右子节点
  35. TreeNode<K,V> xp = p;
  36. //如果比较节点还没有左子节点或者右子节点时才能插入,否则就进入下一轮循环(因为是查找二叉树)
  37. if ((p = (dir <= 0) ? p.left : p.right) == null) {
  38. //比较节点的next即是新节点的next,原因是当前x需要作为比较节点p的子节点(树的位置需要调整)
  39. Node<K,V> xpn = xp.next;
  40. TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);//新建一个树形节点
  41. if (dir <= 0)
  42. xp.left = x;//x的hash比比较节点小,即作为比较节点的左子节点
  43. else
  44. xp.right = x;//x的hash比比较节点大,即作为比较节点的右子节点
  45. xp.next = x;
  46. x.parent = x.prev = xp;//比较节点即是当前节点的x的父节点也是上一个节点
  47. if (xpn != null)//当比较节点的原next节点存在时,需要重新设置该节点的上一个节点指向新节点
  48. ((TreeNode<K,V>)xpn).prev = x;
  49. moveRootToFront(tab, balanceInsertion(root, x));//每次都要重新平衡并确定新的根节点
  50. return null;//新增节点返回null
  51. }
  52. }
  53. }
  54. /*
  55. *
  56. * Tie-breaking utility for ordering insertions when equal hashCodes and non-comparable.
  57. * We don't require a total order, just a consistent insertion rule to maintain equivalence
  58. * across rebalancings. Tie-breaking further than necessary simplifies testing a bit.
  59. * 当a和b哈希值相同但是无法比较时,直接根据两个引用的地址进行比较
  60. * 这个树里不要求完全有序,只要插入时使用相同的规则保持平衡即可
  61. */
  62. static int tieBreakOrder(Object a, Object b) {
  63. int d;
  64. if (a == null || b == null || (d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)
  65. d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1);
  66. return d;
  67. }

3.6 getNode方法解析

  1. public V get(Object key) {
  2. Node<K,V> e;//getEntry变更为getNode
  3. return (e = getNode(hash(key), key)) == null ? null : e.value;
  4. }
  5. /**
  6. * Implements Map.get and related methods
  7. * get方法主要包括几个步骤:
  8. * 1.优先获取头节点(即放在数组中的元素) -- 好处是:不需要一上来就遍历
  9. * 2.若头节点没有匹配上且头节点next非空,那么就需要遍历
  10. * 3.遍历前需要先判断是否为树形节点,是则根据红黑树遍历否则就根据链表遍历
  11. * 4.若该key对应的节点不存在,默认返回null
  12. * @param hash hash for key
  13. * @param key the key
  14. * @return the node, or null if none
  15. */
  16. final Node<K,V> getNode(int hash, Object key) {
  17. Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  18. if ((tab = table) != null && (n = tab.length) > 0 &&
  19. (first = tab[(n - 1) & hash]) != null) {
  20. if (first.hash == hash && // always check first node 总是优先匹配头节点
  21. ((k = first.key) == key || (key != null && key.equals(k))))
  22. return first;
  23. //若头节点没有匹配上且头节点next非空,那么就需要遍历
  24. if ((e = first.next) != null) {
  25. //优先判断是否树形节点,注意:当桶内已经树化,则桶内节点都是TreeNode类型
  26. if (first instanceof TreeNode)
  27. return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  28. //否则,桶内为链表结构,需要遍历链表(根据插入顺序遍历-FIFO先进先出原则)
  29. do {
  30. if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
  31. return e;
  32. } while ((e = e.next) != null);
  33. }
  34. }
  35. return null;//对应节点不存在,返回null
  36. }

3.7 getTreeNode方法解析

  1. /**
  2. * Calls find for root node.
  3. * 红黑树 总是从根节点开始查找
  4. */
  5. final TreeNode<K,V> getTreeNode(int h, Object k) {
  6. return ((parent != null) ? root() : this).find(h, k, null);
  7. }
  8. /**
  9. * Finds the node starting at root p with the given hash and key.
  10. * The kc argument caches comparableClassFor(key) upon first use comparing keys.
  11. * 查找指定key,并从根节点开始递归
  12. */
  13. final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
  14. TreeNode<K,V> p = this;//这里的this指的是root,参见getTreeNode
  15. do {
  16. int ph, dir; K pk;
  17. TreeNode<K,V> pl = p.left, pr = p.right, q;
  18. //查找原则:左子树都比自身小,右子树都比自身大,二分查找即可
  19. //比较hash,当前节点hash小,继续查左子树,否则查右子数
  20. if ((ph = p.hash) > h)
  21. p = pl;
  22. else if (ph < h)
  23. p = pr;
  24. else if ((pk = p.key) == k || (k != null && k.equals(pk)))
  25. return p;//若找到,直接返回
  26. //哪边子树是空,就查另一边子树
  27. else if (pl == null)
  28. p = pr;
  29. else if (pr == null)
  30. p = pl;
  31. //主要处理hash相同时,key又实现了Compareble的情况(即根据比较器比较)
  32. else if ((kc != null || (kc = comparableClassFor(k)) != null) &&
  33. (dir = compareComparables(kc, k, pk)) != 0)
  34. p = (dir < 0) ? pl : pr;
  35. //先递归右子树,找不到再找左子树(此时左右子树都非空)
  36. else if ((q = pr.find(h, k, kc)) != null)
  37. return q;
  38. else
  39. p = pl;
  40. } while (p != null);
  41. return null;//找不到则返回null
  42. }

3.8 split方法解析

  1. /**
  2. * Splits nodes in a tree bin into lower and upper tree bins,or untreeifies if now too small.
  3. * Called only from resize;see above discussion about split bits and indices.
  4. * 该方法主要有两个作用:
  5. * 1.将桶内元素分成低位链表和高位链表两个部分
  6. * 2.当该桶的元素数量太少时,会执行反树化操作(即链化操作)
  7. * 该方法只能被resize方法使用
  8. * @param map the map 当前map
  9. * @param tab the table for recording bin heads 这里代指newTab
  10. * @param index the index of the table being split 当前数组下标
  11. * @param bit the bit of hash to split on 这里代指oldCap
  12. */
  13. final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
  14. TreeNode<K,V> b = this;//当前node
  15. // Relink into lo and hi lists, preserving order
  16. TreeNode<K,V> loHead = null, loTail = null;//lo=low
  17. TreeNode<K,V> hiHead = null, hiTail = null;//hi=high
  18. int lc = 0, hc = 0;//lc=lowCount 即桶内低位元素个数 hc=highCount 即桶内高位元素个数
  19. for (TreeNode<K,V> e = b, next; e != null; e = next) {
  20. next = (TreeNode<K,V>)e.next;
  21. e.next = null;
  22. //(e.hash & bit) == 0 等价于 resize方法中的 (e.hash & oldCap) == 0,同时效果等效
  23. //即将桶内元素分成低位链表和高位链表两个部分,即红黑树一分为二成两个链表
  24. if ((e.hash & bit) == 0) {
  25. if ((e.prev = loTail) == null)
  26. loHead = e;
  27. else
  28. loTail.next = e;
  29. loTail = e;
  30. ++lc;
  31. }
  32. else {
  33. if ((e.prev = hiTail) == null)
  34. hiHead = e;
  35. else
  36. hiTail.next = e;
  37. hiTail = e;
  38. ++hc;
  39. }
  40. }
  41. //注意:两条链不是直接以链表的形式置于相应的槽位,而是同样根据链的长短进行判断是链化还是树化
  42. //低位链表位置不变,还是在原桶中
  43. if (loHead != null) {
  44. //低位元素数量若<=链表还原阈值,那需要将反树化,将树重新变成链表结构
  45. if (lc <= UNTREEIFY_THRESHOLD)
  46. tab[index] = loHead.untreeify(map);
  47. else {
  48. tab[index] = loHead;//重新设置原桶头节点
  49. //若新桶头节点非空,原桶需要重新树化(因为重新分割了)
  50. if (hiHead != null) // (else is already treeified)
  51. loHead.treeify(tab);
  52. }
  53. }
  54. //高位链表位置变动,变动到新桶,即[index+oldCap]位置
  55. if (hiHead != null) {
  56. //高位元素数量若<=链表还原阈值,那需要将反树化,将树重新变成链表结构
  57. if (hc <= UNTREEIFY_THRESHOLD)
  58. tab[index + bit] = hiHead.untreeify(map);
  59. else {
  60. tab[index + bit] = hiHead;//重新设置新桶头节点
  61. //若原桶头节点非空,新桶需要重新树化(因为重新分割了)
  62. if (loHead != null)
  63. hiHead.treeify(tab);
  64. }
  65. }
  66. }
评论