Skip to content

Commit 55e0841

Browse files
authored
Update 集合框架面试知识点.md
1 parent 5c8ed36 commit 55e0841

File tree

1 file changed

+69
-31
lines changed

1 file changed

+69
-31
lines changed

docs/集合框架面试知识点.md

Lines changed: 69 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -85,12 +85,70 @@
8585

8686
5.hashcode:计算键的hashcode作为存储键信息的数组下标用于查找键对象的存储位置。equals:HashMap 使用 equals() 判断当前的键是否与表中存在的键相同。
8787

88+
## HashMap 的结构
89+
90+
在 JDK 1.7 中 HashMap 是以数组加链表的形式组成的,JDK 1.8 之后新增了红黑树的组成结构,当链表大于 8 并且容量大于 64 时,链表结构会转换成红黑树结构,添加红黑树是因为一旦链表过长,会严重影响 HashMap 的性能,而红黑树具有快速增删改查的特点,这样就可以有效的解决链表过长时操作比较慢的问题。
91+
8892
## HashMap 的长度为什么是2的幂次方
8993

9094
HashMap为了存取高效,要尽量较少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现就在把数据存到哪个链表中的算法;这个算法实际就是取模,hash%length,计算机中直接求余效率不如位移运算,源码中做了优化hash&(length-1),
9195

9296
**hash%length==hash&(length-1)的前提是 length 是2的 n 次方;**
9397

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+
94152
## HashMap 1.7和1.8版本区别
95153

96154
* **数据结构:**1.7:数组+链表,1.8:数组+链表+红黑树
@@ -99,12 +157,6 @@ HashMap为了存取高效,要尽量较少碰撞,就是要尽量把数据分
99157
* **插入和扩容的判断:**1.7:先扩容后插入,1.8:先插入后扩容
100158
* 为什么?1.8增加了判断是否为红黑树节点,先扩容的话不知道到底扩链表节点还是红黑树。
101159

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-
108160
## HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标?
109161

110162
`hashCode()`方法返回的是int整数类型,其范围为-(2 ^ 31)~(2 ^ 31 - 1), 而HashMap的容量范围是在16(初始化默认值)~2 ^ 30, HashMap通常情况下是取不到最大值的,并且设备上也难以提供这么多的存储空间,从而导致通过`hashCode()`计算出的哈希值可能不在数组大小范围内,进而无法匹配存储位置;
@@ -119,6 +171,14 @@ HashMap为了存取高效,要尽量较少碰撞,就是要尽量把数据分
119171

120172
这样就是加大哈希值低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性&均匀性,最终减少Hash冲突,两次就够了,已经达到了高位低位同时参与运算的目的;
121173

174+
## HashMap1.7为什么不安全?⭐
175+
176+
HashMap在rehash的时候,这个会重新将原数组的内容重新hash到新的扩容数组中,在多线程的环境下,存在同时其他put操作,如果hash值相同,把值插入同一个链表,会因为头插法的特性造成闭环,导致在get时会出现死循环,所以HashMap是线程不安全的。
177+
178+
#### 高并发下HashMap1.7的环是如何产生的
179+
180+
若当前线程一此时获得ertry节点,但是被线程中断无法继续执行,此时线程二进入transfer函数,并把函数顺利执行,此时新表中的某个位置有了节点,之后线程一获得执行权继续执行,在tranfer方法中会把next指向自己造成闭环,然后在get时会出现死循环。
181+
122182
## 为什么HashMap中String、Integer这样的包装类适合作为Key?⭐
123183

124184
String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性,能够有效的减少Hash碰撞的几率
@@ -130,35 +190,13 @@ String、Integer等包装类的特性能够保证Hash值的不可更改性和计
130190

131191
重写`hashCode()``equals()`方法 。 **重写`hashCode()`是因为需要计算存储数据的存储位置****重写`equals()`方法** **目的是为了保证key在哈希表中的唯一性**
132192

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值的时间,并且扩容后链表元素位置不会倒置。
146193

147-
步骤:
148194

149-
* 数组,阈值都扩大一倍
150-
* 如果旧数组不为空,开始遍历旧数组
151-
* 遍历到的数组上只有一个元素,就直接迁移
152-
* 如果是红黑树就使用 split 方法
153-
* 如果是链表就把链表拆成两个,放到新数组中并且保留顺序
154-
155-
## HashMap为什么不安全?⭐
156-
157-
HashMap在put的时候,插入的元素超过了容量(由负载因子决定)的范围就会触发扩容操作,就是rehash,这个会重新将原数组的内容重新hash到新的扩容数组中,在多线程的环境下,存在同时其他的元素也在进行put操作,如果hash值相同,可能出现同时在同一数组下用链表表示,造成闭环,导致在get时会出现死循环,所以HashMap是线程不安全的。
195+
## ConcurrentHashMap线程安全的实现方式/数据结构⭐
158196

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。
160198

161-
若当前线程此时获得ertry节点,但是被线程中断无法继续执行,此时线程二进入transfer函数,并把函数顺利执行,此时新表中的某个位置有了节点,之后线程一获得执行权继续执行,因为并发transfer,所以两者都是扩容的同一个链表,当线程一执行到e.next = new table[i] 的时候,由于线程二之前数据迁移的原因导致此时new table[i] 上就有ertry存在,所以线程一执行的时候,会将next节点,设置为自己,导致自己互相使用next引用对方,因此产生链表,导致死循环。
199+
详见java容器总结篇。
162200

163201
## BlockingQueue是什么?
164202

0 commit comments

Comments
 (0)