底层实现原理
++1.7++HashMap底层是使用数组+链表实现
++1.8++HashMap底层是使用数组+链表+红黑树实现
- table[] 的默认大小是16
- 负载因子的默认大小是0.75
当数据量达到16 * 0.75 = 12
就会对数组容量进行扩容。
JDK1.7存放数据的过程:
- 根据key计算出一个hashcode
- 根据计算出的hashcode定位出所在的数组位置
- 如果这个数组位置是一个链表,则遍历判断里面key是否与传入key相同
- 内容相等:进行覆盖,返回原来的值
- 不相等:在链表头部添加新key
- 如果这个数组位置为空,这说明当前位置没有存数据,就可以新增一个Entry对象。
- 如果这个数组位置是一个链表,则遍历判断里面key是否与传入key相同
- 当新增Entry时,会判断是否需要扩容。扩容时会为链表中的key重新hash,根据新hashcode加入的新扩容的数组中(避免链表过长)
JDK1.8存放数据的过程优化:
- 如果数组位置有链表了,是将新key加在链表尾部
- 在添加时,如果链表大小大于预设阈值,则将链表转换为红黑树(查找更高效)
HashMap线程安全问题
HashMap并发访问的时候容易出现死循环,
原因是在进行扩容的时候会调用resize()方法。
ConcurrentHashMap专门用于解决并发问题的HashMap集合
JDK1.7的ConcurrentHashMap实现
ConcurrentHashMap是由Segment数组和HastEntry组成,和HashMap一样,仍然是数据+链表
采用分段锁技术:
CurrencyLevel = 16 (Segment数组的数量)
每当一个线程占用锁访问一个Segment时,不会影响到其他的Segment
在获取的时候,因为value的属性是用volatile关键字修饰的,保证了内存可见性,所以每次获取时都是最新值。(因为不需要枷锁,所以get方法非常高效)
JDK1.8的ConcurrentHashMap优化
1.7虽然已经解决了并发问题,但是查询遍历链表效率太低。
1.8抛弃了原有的Segment分段锁设计,而采用了CAS+synchronized
来保证并发安全性