创意电子

标题: HashMap、ConcurrentHashMap数据结构、底层原理、源码分析 [打印本页]

作者: Java码农之路 时间: 2022-5-12 21:26
标题: HashMap、ConcurrentHashMap数据结构、底层原理、源码分析

HashMap

数据结构
JDK1.7
HashMap由数组+单向链表组成，数组是HashMap的主体，链表则是主要为相识决哈希冲突而存在的。
什么是哈希冲突？由于哈希算法被计算的数据是无穷的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突。
如果发生hash冲突，HashMap会将同一个桶中的数据以链表的情势存储，但是如果发生hash冲突的概率比较高，就会导致同一个桶中的链表长度过长，遍历效率降低。

JDK1.8
HashMap由数组+单向链表/红黑树组成，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜刮时间。

转为红黑树后，链表的结构仍然会存在，通过next属性维持，红黑树节点在进行操纵时都会维护链表的结构。
底层原理
怎么实现扩容？（JDK1.7)
hashMap默认的初始容量是16，加载因子是0.75；我们也可以通过构造器 HashMap(int initialCapacity) 来指定初始容量，但需要为2的n次幂，每次扩容都为原来的两倍。
当达到其容量的3/4时，会自动进行扩容，如初始为16，存储第12个元素时，这时候会扩容为32，同时，这时需要创建一张新表，将原表的数据移到新表，可以看resize()和transfer()方法。
View Code
在扩容时，JDK1.8不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的谁人bit是1还是0就好了，是0的话索引没变，是1的话索引酿成“原索引+oldCap”。
怎么实现存取？
key可以存放null，null key总是存放在Entry[]数组的第一个元素，可以看putForNullKey()方法。
HashMap存取时，都需要计算当前key应该对应Entry[]数组哪个元素，通过调用hash()方法，得到hash值，再调用indexFor()得到Entry[]数组下标。
View Code
如果有两个相同的结果，如果hash相同且key对象为同一个，则为同一个对象，直接在该位置替换原对象；否则为不同对象，这时候发生碰撞了，我们通过链表来存储，可以分析createEntry()方法。
View Code
源码分析(JDK1.7)

View Code

ConcurrentHashMap（JDK1.7）

数据结构
JDK1.7仍然是数组+单向链表
底层原理
ConcurrentHashMap怎么实现同步的？和HashMap不同之处，ConcurrentHashMap最外层是多个Segment，每个Segment数据结构和HashMap类似，数组+链表组成。每个Segment 都有一个ReentrantLock锁，之间互不影响。
1、HashEntry内部类里的value ，以及链表next都是volatile 修饰的，能保证获取时的可见性。
View Code
2、采用了分段锁技能，具体可以看Segment内部类，继承于 ReentrantLock。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。
可以看下面的put()方法，put里面第一次尝试加锁，使用自旋获取锁，ReentrantLock提供的tryLock() 方法。
如果如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，ReentrantLock提供的lock()方法，这种方式获取不到则一直休眠等待，直到能获取乐成。
View Code
　　JDK1.8改为了数组+单向链表+红黑树的数据结构，链表长度增加到8时，可能触发变为红黑树，加快查找速度；
　　在JDK1.7中Segment在初始化时默认为16，可以设置初始化但后续不能扩容修改，在JDK1.8中取消了Segment，直接用HashEntry，在一些特定情况会扩容。
最后(求关注，别白嫖我)

如果这篇文章对您有所帮助，或者有所启发的话，欢迎关注我的公众号：程序员黑哥

作者: 热闹清风S 时间: 2022-5-13 05:20
不白嫖，点赞，评论

作者: 晨熹伴读 时间: 2022-5-13 09:10
jdk1.8转红黑树的条件是链表结构大于8，但是如果数组长度小于64优先进行数组扩容，这不专业啊

作者: Marianas 时间: 2022-5-13 10:46
转发了

作者: 懂技术的厨师 时间: 2022-5-13 10:55
转发了

欢迎光临创意电子 (https://wxcydz.cc/)