85
85
86
86
5.hashcode:计算键的hashcode作为存储键信息的数组下标用于查找键对象的存储位置。equals:HashMap 使用 equals() 判断当前的键是否与表中存在的键相同。
87
87
88
+ ## HashMap 的结构
89
+
90
+ 在 JDK 1.7 中 HashMap 是以数组加链表的形式组成的,JDK 1.8 之后新增了红黑树的组成结构,当链表大于 8 并且容量大于 64 时,链表结构会转换成红黑树结构,添加红黑树是因为一旦链表过长,会严重影响 HashMap 的性能,而红黑树具有快速增删改查的特点,这样就可以有效的解决链表过长时操作比较慢的问题。
91
+
88
92
## HashMap 的长度为什么是2的幂次方
89
93
90
94
HashMap为了存取高效,要尽量较少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现就在把数据存到哪个链表中的算法;这个算法实际就是取模,hash%length,计算机中直接求余效率不如位移运算,源码中做了优化hash&(length-1),
91
95
92
96
** hash%length==hash&(length-1)的前提是 length 是2的 n 次方;**
93
97
98
+ ## 什么是 HashMap 的加载因子?加载因子为什么是 0.75?
99
+
100
+ 判断什么时候进行扩容的,假如加载因子是 0.5,HashMap 的初始化容量是 16,那么当 HashMap 中有 16* 0.5=8 个元素时,HashMap 就会进行扩容。
101
+
102
+ 这其实是出于容量和性能之间平衡的结果:
103
+
104
+ * 当加载因子设置比较大的时候,扩容的门槛就被提高了,扩容发生的频率比较低,占用的空间会比较小,但此时发生Hash冲突的几率就会提升,因此需要更复杂的数据结构来存储元素,这样对元素的操作时间就会增加,运行效率也会因此降低;
105
+ * 而当加载因子值比较小的时候,扩容的门槛会比较低,因此会占用更多的空间,多次扩容也会影响性能。
106
+ * HashMap的容量有一个固定的要求就是一定是2的幂次方。所以,如果负载因子是3/4的话,那么和capacity的乘积结果就可以是一个整数。
107
+
108
+
109
+ 所以综合了以上情况就取了一个 0.5 到 1.0 的平均数 0.75 作为加载因子。
110
+
111
+ ## put 方法流程
112
+
113
+ map.put("a","b")的整个流程:
114
+
115
+ 1. 先判断散列表是否没有初始化或者为空,如果是就扩容
116
+ 2. 根据键值 key 计算 hash 值,得到要插入的数组索引
117
+ 3. 判断要插入的那个数组是否为空:
118
+ 1. 如果为空直接插入。
119
+ 2. 如果不为空,判断 key 的值是否是重复(用 equals 方法):
120
+ 1. 如果是就直接覆盖
121
+ 2. 如果不重复就再判断此节点是否已经是红黑树节点:
122
+ 1. 如果是红黑树节点就把新增节点放入树中
123
+ 2. 如果不是,就开始遍历链表:
124
+ 1. 循环判断直到链表最底部,到达底部就插入节点,然后判断是否大于链表长度是否大于8:
125
+ 1. 如果大于8就转换为红黑树
126
+ 2. 如果不大于8就继续下一步
127
+ 2. 到底部之前发现有重复的值,就覆盖。
128
+ 4. 判断是否需要扩容,如果需要就扩容。
129
+
130
+ ## HashMap 的扩容机制
131
+
132
+ 扩容时机:当` size ` 大于` threshold ` 的时候,并不一定会触发扩容机制,只要有一个新建的节点出现哈希冲突,则立刻` resize ` 。
133
+
134
+ - size记录的是map中包含的Entry的数量
135
+ - 而threshold记录的是需要resize的阈值 且 ` threshold = loadFactor * capacity `
136
+ - capacity 其实就是桶的长度
137
+
138
+ 步骤:
139
+
140
+ * 数组,阈值都扩大一倍
141
+ * 如果旧数组不为空,开始遍历旧数组
142
+ * 遍历到的数组上只有一个元素,就直接迁移
143
+ * 如果是红黑树就使用 split 方法
144
+ * 如果是链表就把链表拆成两个,按照高位运算的结果放到新数组中并且保留顺序
145
+
146
+ #### JDK 1.8 在扩容方面对 HashMap 做了哪些优化?
147
+
148
+ 1.7创建一个容量的新数组,重新计算每个元素在数组中的位置并且进行迁移。
149
+
150
+ 1.8中在扩容HashMap的时候,不需要像1.7中去重新计算元素的hash,只需要看看原来的hash值新增的哪个二进制数是1还是0就好了,如果是0的话表示索引没有变,是1的话表示索引变成“oldCap+原索引”,这样即省去了重新计算hash值的时间,并且扩容后链表元素位置不会倒置。
151
+
94
152
## HashMap 1.7和1.8版本区别
95
153
96
154
* ** 数据结构:** 1.7:数组+链表,1.8:数组+链表+红黑树
@@ -99,12 +157,6 @@ HashMap为了存取高效,要尽量较少碰撞,就是要尽量把数据分
99
157
* ** 插入和扩容的判断:** 1.7:先扩容后插入,1.8:先插入后扩容
100
158
* 为什么?1.8增加了判断是否为红黑树节点,先扩容的话不知道到底扩链表节点还是红黑树。
101
159
102
- ## ConcurrentHashMap线程安全的实现方式/数据结构⭐
103
-
104
- 在JDK1.7版本中,ConcurrentHashMap维护了一个Segment数组,Segment这个类继承了重入锁ReentrantLock,在该类里面维护了一个 HashEntry<K,V>[ ] table数组,在写操作put,remove,扩容的时候,会对Segment加锁,所以仅仅影响这个Segment,不同的Segment还是可以并发的,所以解决了线程的安全问题,同时又采用了分段锁也提升了并发的效率。在JDK1.8版本中,ConcurrentHashMap摒弃了Segment的概念,而是直接用Node数组+链表+红黑树的数据结构来实现,并发控制使用Synchronized和CAS来操作,整个看起来就像是优化过且线程安全的HashMap。
105
-
106
- 详见java容器总结篇。
107
-
108
160
## HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标?
109
161
110
162
` hashCode() ` 方法返回的是int整数类型,其范围为-(2 ^ 31)~ (2 ^ 31 - 1), 而HashMap的容量范围是在16(初始化默认值)~ 2 ^ 30, HashMap通常情况下是取不到最大值的,并且设备上也难以提供这么多的存储空间,从而导致通过` hashCode() ` 计算出的哈希值可能不在数组大小范围内,进而无法匹配存储位置;
@@ -119,6 +171,14 @@ HashMap为了存取高效,要尽量较少碰撞,就是要尽量把数据分
119
171
120
172
这样就是加大哈希值低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性&均匀性,最终减少Hash冲突,两次就够了,已经达到了高位低位同时参与运算的目的;
121
173
174
+ ## HashMap1.7为什么不安全?⭐
175
+
176
+ HashMap在rehash的时候,这个会重新将原数组的内容重新hash到新的扩容数组中,在多线程的环境下,存在同时其他put操作,如果hash值相同,把值插入同一个链表,会因为头插法的特性造成闭环,导致在get时会出现死循环,所以HashMap是线程不安全的。
177
+
178
+ #### 高并发下HashMap1.7的环是如何产生的
179
+
180
+ 若当前线程一此时获得ertry节点,但是被线程中断无法继续执行,此时线程二进入transfer函数,并把函数顺利执行,此时新表中的某个位置有了节点,之后线程一获得执行权继续执行,在tranfer方法中会把next指向自己造成闭环,然后在get时会出现死循环。
181
+
122
182
## 为什么HashMap中String、Integer这样的包装类适合作为Key?⭐
123
183
124
184
String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性,能够有效的减少Hash碰撞的几率
@@ -130,35 +190,13 @@ String、Integer等包装类的特性能够保证Hash值的不可更改性和计
130
190
131
191
重写` hashCode() ` 和` equals() ` 方法 。 ** 重写` hashCode() ` 是因为需要计算存储数据的存储位置** , ** 重写` equals() ` 方法** ** 目的是为了保证key在哈希表中的唯一性** ;
132
192
133
- ## HashMap 的扩容机制
134
-
135
- 扩容时机: ** 当` map ` 中包含的` Entry ` 的数量大于等于` threshold = loadFactor \* capacity ` 的时候,且新建的` Entry ` 刚好落在一个非空的桶上,此刻触发扩容机制,将其容量扩大为2倍。**
136
-
137
- 当` size ` 大于等于` threshold ` 的时候,并不一定会触发扩容机制,但是会很可能就触发扩容机制,只要有一个新建的节点出现哈希冲突,则立刻` resize ` 。
138
-
139
- - size记录的是map中包含的Entry的数量
140
- - 而threshold记录的是需要resize的阈值 且 ` threshold = loadFactor * capacity `
141
- - capacity 其实就是桶的长度
142
-
143
- 1.7创建一个容量的新数组,重新计算每个元素在数组中的位置并且进行迁移。
144
-
145
- 1.8中在扩容HashMap的时候,不需要像1.7中去重新计算元素的hash,只需要看看原来的hash值新增的哪个二进制数是1还是0就好了,如果是0的话表示索引没有变,是1的话表示索引变成“oldCap+原索引”,这样即省去了重新计算hash值的时间,并且扩容后链表元素位置不会倒置。
146
193
147
- 步骤:
148
194
149
- * 数组,阈值都扩大一倍
150
- * 如果旧数组不为空,开始遍历旧数组
151
- * 遍历到的数组上只有一个元素,就直接迁移
152
- * 如果是红黑树就使用 split 方法
153
- * 如果是链表就把链表拆成两个,放到新数组中并且保留顺序
154
-
155
- ## HashMap为什么不安全?⭐
156
-
157
- HashMap在put的时候,插入的元素超过了容量(由负载因子决定)的范围就会触发扩容操作,就是rehash,这个会重新将原数组的内容重新hash到新的扩容数组中,在多线程的环境下,存在同时其他的元素也在进行put操作,如果hash值相同,可能出现同时在同一数组下用链表表示,造成闭环,导致在get时会出现死循环,所以HashMap是线程不安全的。
195
+ ## ConcurrentHashMap线程安全的实现方式/数据结构⭐
158
196
159
- ## 高并发下HashMap的环是如何产生的
197
+ 在JDK1.7版本中,ConcurrentHashMap维护了一个Segment数组,Segment这个类继承了重入锁ReentrantLock,在该类里面维护了一个 HashEntry<K,V> [ ] table数组,在写操作put,remove,扩容的时候,会对Segment加锁,所以仅仅影响这个Segment,不同的Segment还是可以并发的,所以解决了线程的安全问题,同时又采用了分段锁也提升了并发的效率。在JDK1.8版本中,ConcurrentHashMap摒弃了Segment的概念,而是直接用Node数组+链表+红黑树的数据结构来实现,并发控制使用Synchronized和CAS来操作,整个看起来就像是优化过且线程安全的HashMap。
160
198
161
- 若当前线程此时获得ertry节点,但是被线程中断无法继续执行,此时线程二进入transfer函数,并把函数顺利执行,此时新表中的某个位置有了节点,之后线程一获得执行权继续执行,因为并发transfer,所以两者都是扩容的同一个链表,当线程一执行到e.next = new table [ i ] 的时候,由于线程二之前数据迁移的原因导致此时new table [ i ] 上就有ertry存在,所以线程一执行的时候,会将next节点,设置为自己,导致自己互相使用next引用对方,因此产生链表,导致死循环。
199
+ 详见java容器总结篇。
162
200
163
201
## BlockingQueue是什么?
164
202
0 commit comments