快捷搜索:  汽车  科技

hashmap的实现原理(HashMapConcurrentHashMap数据结构底层原理)

hashmap的实现原理(HashMapConcurrentHashMap数据结构底层原理)底层原理转为红黑树后,链表的结构仍然会存在,通过next属性维持,红黑树节点在进行操作时都会维护链表的结构。如果发生hash冲突,HashMap会将同一个桶中的数据以链表的形式存储,但是如果发生hash冲突的概率比较高,就会导致同一个桶中的链表长度过长,遍历效率降低。JDK1.8HashMap由数组 单向链表/红黑树组成,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。

  • HashMap

数据结构

JDK1.7

HashMap由数组 单向链表组成,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的。

什么是哈希冲突?由于哈希算法被计算的数据是无限的,而计算后的结果范围有限,因此总会存在不同的数据经过计算后得到的值相同,这就是哈希冲突。

如果发生hash冲突,HashMap会将同一个桶中的数据以链表的形式存储,但是如果发生hash冲突的概率比较高,就会导致同一个桶中的链表长度过长,遍历效率降低。

hashmap的实现原理(HashMapConcurrentHashMap数据结构底层原理)(1)

JDK1.8

HashMap由数组 单向链表/红黑树组成,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。

hashmap的实现原理(HashMapConcurrentHashMap数据结构底层原理)(2)

转为红黑树后,链表的结构仍然会存在,通过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)

  • put

View Code

  • get

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<K V>,在一些特定情况会扩容。

最后(求关注,别白嫖我)

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

hashmap的实现原理(HashMapConcurrentHashMap数据结构底层原理)(3)

猜您喜欢: