Java小白一文讲清Java中聚集相关的知识点（六）

接上篇

添加了第二个元素“php”字符串后，debug检察此时的table的空间具体存储情况如下：

于是其将第二个待存放的元素“php”映射放入了9号索引处；接下来我们分析添加第三个重复元素“java”再次实验放进去时，底层发生的一系列动作；

1.     public boolean add(E e) {
2.         return map.put(e, PRESENT)==null;
3.     }
6.     public V put(K key, V value) {
7.         return putVal(hash(key), key, value, false, true);
8.     }
10. // 同样，我们就不讨论先前已经分析过的hash(key)和PRESENT的具体实现
11.     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
12.                    boolean evict) {
13.         Node<K,V>[] tab; Node<K,V> p; int n, i;
14.         //这里的if分支是不会进入的
15.         if ((tab = table) == null || (n = tab.length) == 0)
16.             n = (tab = resize()).length;
17.         //接下来就到了这里了，因为此时的要添加的第三个元素java和第一个元素相同，所以
18.         //此时计算的hash是相等的，这里的[i = (n - 1) & hash]是3，
19.         //最后的p也就不再等于null了，不再进入这里的
20.         //if分支，然后来到else分支处
21.         if ((p = tab[i = (n - 1) & hash]) == null)
22.             tab[i] = newNode(hash, key, value, null);
23.         //来到这儿，这里因为else中情况复杂，总共有三种情况，所以先做个总的逻辑说明及分析，然后
24.         //再进入内部具体阐释
25.         /**
26.         顺便由此分享一个开发技巧：
27.                 在需要局部变量(辅助变量)的时候，再创建；
28. 流程概述：
29. 1.先定义辅助变量
30. 2.第一个if中先判断，(切记p是指向node结点的哈,Node结点中有key,有hash,有value...)，
31.         2.1你先前映射时创造出来的指向其索引位置的p处的hash和当前已有的hash
32.                   做比较，如果当前索引位置对应的链表的第一个元素和现在准备要添加的元素的hash一样;
33.                  
34.                   并且满足下面两个条件之一
35.           2.2(1)你原先p指向的Node结点中的key和当前要加入进去的元素的key是同一个对象
36.           2.2(2)p 指向的Node结点的key(其是个对象噻)的equals()和准备加入的key比较后相同
37.                    举例1：原先的3索引放了个"java"字符串，之后再放个"java"字符串，那么就符合此时的if条件
38.                    举例2：如果key此时是个Dog对象，之后再放一个，但是二者的key可能不相等，是两个不同的对象
39.                              但是，二者的equals经过重写后，发现相等，那么也是符合上述条件的
40.           2.3 如果满足上述的综合条件，即2.1+(2.2中任意一个)，则不能加入
41. 3.第一个if如果判断后，不能加入，就紧接着看else if；
42.         看此时的p是不是一棵红黑树，如果是的话，就按照红黑树的方式去比较
43.         如果是一棵红黑树，就调用putTreeVal()来进行添加
44.         此中的putTreeVal()很复杂，建议暂时不要生啃，会很痛苦
45. 4.如果第二个else if也没满足，则进入最后的else分支
46.         举例：3索引处放了个jack,后面挂载个marry,marry后面挂载个smith;jack->marry->smith
47.         此时想放进来个tom,
48.         其被映射到了3索引处，不满足第一个if条件，其和jack的hash值就不一样，然后看第二个else if,
49.         发现此时的jack处也不是红黑树的结构，故来到了最后的else 分支,
50.         此时的tom先跟jack比较，哎嘿，不一样，然后再跟下一个marry比较，哎嘿，又不一样，心中偷笑
51.         再跟smith一比，发现还是不一样，哎嘿，那tom就可以跟在smith屁股后面了；
52.                 当然，如果循环不断对比，发现有个tom，怎么办，说明先前已经加进来个tom,那我这个假tom
53.                 进来干嘛，纯纯第三者啊，它就 转身离开，你有话说不出来，分手说不出来，海鸟与鱼相爱~~~hhhh
54. 即：如果table对应索引位置，已经是一个链表了，就使用for循环比较，
55.         (1)依次和该链表的每一个元素比较，都不相同，则加入到该链表的最后
56. 注意：在把元素添加到链表后，立即判断，该链表是否已经达到8个结点
57.                         如果已经达到8个结点，则调用treeifyBin() 对当前这个链表进行树化(转成红黑树)
58. 注意：在转成红黑树时，还要进行判断是否table表的长度>=64了，如果不大于等于64，则会先扩容
59.         不会马上进行树化，树化还得满足你的表长度大于等于64；具体代码如下：
60. if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//64
61.             resize();
62. 如果上面条件成立，则先resize()扩容，只有上面条件不成立时，才进行树化，转成红黑树
63.                 //也就是table数组大小已经>=64,且其中的某处挂载已经达到8个时，才会树化                       
64.         (2)依次和该链表的每一个元素比较过程中，如果发现有相同情况，说明你是多余的，就直接转身离开hhhh
65.        
66.         */
67.         else {
68.             Node<K,V> e; K k;
69.             if (p.hash == hash &&
70.                 ((k = p.key) == key || (key != null && key.equals(k))))
71.                 e = p;
72.             else if (p instanceof TreeNode)
73.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
74.             else {
75.                 for (int binCount = 0; ; ++binCount) {
76.                     //假设只有一个Jason,p指向它，然后让e指向p.next，此时为空，有个star
77.                     //要加进来，那么符合此时的if，就把star挂在jason后面
78.                     //这里说下，为什么要直接看p.next，因为在上面2对应的情况中，
79.                     //star和jason就是比过了的
80.                     //所以，直接第一个if看后面是不是null,是的话，就跟了这个单身狗hhhh
81. //那么如果此时是jason-blue-fulture,p指向jason,e指向blue,那么此时的e不为空，所以，
82. //直接跳过下面这个第一个if判断，然后进入第二个if里面判断，轮询，第一个是jason,star和
83. //它hash不一样，不break,p下移，回到第一个if语句，e下移，判断是否为空,不为空，则回到第二个
84. //if,此时的p就是blue,判断二者hash，发现还是不一样，
85. //不break,此时的p继续下移，指向fulture,回到第一个if判断，e指向p.next,此时发现为空，那么此时
86. //就直接p.next = newNode(...)来将此时的star挂载到末尾了，即fulture得后面
87.                     //jason-blue-fulture-star
88.                     //当然如果有相同的，就在第二个break处转身离开，分手的话说不出来了hhhhh
90.                     //总结就是，两个指针p、e来回地移动，比较
91.                     if ((e = p.next) == null) {
92.                         //都比完了，还没找相同的，就扔在屁股后面
93.                         p.next = newNode(hash, key, value, null);
94.                         //TREEIFY_THRESHOLD 是树化阈值，它的默认值是 8
95. /**
96. 在 HashMap 中，当链表的长度超过一个阈值时，出于性能的考虑，链表会被树化，即将链表转换为红黑树。
97. 这是为了避免链表太长导致查询和插入操作的时间复杂度从 O(1) 退化到 O(n)。
98.         TREEIFY_THRESHOLD - 1：这个条件意味着，当链表中的元素个数达到 7（即 TREEIFY_THRESHOLD - 1）时，
99.         下一次插入时就会触发树化。
101. 为什么是 TREEIFY_THRESHOLD - 1 而不是直接用 TREEIFY_THRESHOLD？
102. 这是因为在 if (e = p.next) 之前，p.next 还是 null，也就是还没有把新元素插入到链表中。
103. 因此，这个判断提前在链表中已有 7 个元素时就开始准备树化，当新元素加入后总共有 8 个元素时，
104. 执行 treeifyBin 方法，将链表转换为红黑树。
105. */
106.                         if (binCount >= TREEIFY_THRESHOLD - 1) // 8-1=7
107.                             //如果当前结点已经达到了8个结点，则进行树化
108.                             treeifyBin(tab, hash);
109.                         break;//这里对应着(1)这种情况
110.                     }
111.                     if (e.hash == hash &&
112.                         ((k = e.key) == key || (key != null && key.equals(k))))
113.                         break;//这里对应着(2)这种情况
114.                     p = e;//p不断下移
115.                 }
116.             }
117.             if (e != null) { // 这里的e就是"java",其不为空
118.                 V oldValue = e.value;//这里其实就是PRESENT
119.                 if (!onlyIfAbsent || oldValue == null)
120.                     e.value = value;
121.                 afterNodeAccess(e);
122.                 return oldValue;//最终返回旧值到put函数，put再将其返回给add函数，
123.                 //oldValue!=null,表示键已经存在；add方法通过判断put()返回的结果是否为null
124.                 //来确定是否成功插入新的元素
125.                 //如果返回null,表示键是新的，插入成功，反之，不为null,则表示键已经存在，插入失败
126.             }
127.         }
128.         ++modCount;
129.         if (++size > threshold)
130.             resize();
131.         afterNodeInsertion(evict);
132.         return null;
133.     }
136. //树化的代码如下：
137.     final void treeifyBin(Node<K,V>[] tab, int hash) {
138.         int n, index; Node<K,V> e;
139. //        在转成红黑树时，还要进行判断是否table表的长度>=64了，
140. //如果不大于等于64，则会先扩容，不会马上进行树化，
141.         //树化还得满足你的表长度大于等于64，MIN_TREEIFY_CAPACITY=64
142. //也就是表已经>=64,且其中的某处挂载已经达到8个时，才会树化
143.         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//64
144.             resize();
145.         else if ((e = tab[index = (n - 1) & hash]) != null) {
146.             TreeNode<K,V> hd = null, tl = null;
147.             do {
148.                 TreeNode<K,V> p = replacementTreeNode(e, null);
149.                 if (tl == null)
150.                     hd = p;
151.                 else {
152.                     p.prev = tl;
153.                     tl.next = p;
154.                 }
155.                 tl = p;
156.             } while ((e = e.next) != null);
157.             if ((tab[index] = hd) != null)
158.                 hd.treeify(tab);
159.         }
160.     }

复制代码

再回首复习先前的结论

• HashSet的底层是HashMap
  
• 添加一个元素时，先得到hash值，然后会将其转化成索引值
  
• 找到存储数据表table,看这个索引位置是否已经存放有元素，如果没有，直接加入，如果有，则调用
  equals()比较，如果相同，就放弃添加，如果不相同，则添加到最后
  
• 在Java8中，如果一条链表的元素个数达到TREEIFY_CAPACITY，默认是8，并且table的大小>=MIN_TREEIFY_CAPACITY
  默认64，就会举行树化（转成红黑树）
  

明天完结HashMap源码的分析及总结，拜拜喽！！！！


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。