HashMap,ConcurrentHashMap的常见面试题
常见问题如下:
- 谈谈你理解的 HashMap,讲讲其中的
get
put
过程。 - JDK 1.8 对 HashMap 做了什么优化?
- HashMap是线程安全的吗?
- 不安全会导致哪些问题?
- 如何解决?有没有线程安全的并发容器?
- ConcurrentHashMap 是如何实现的? 1.7、1.8 实现上有什么不同?为什么要这么做?
首先,我们知道 HashMap 的底层是基于数组+链表的方式。
而 JDK 1.7 和 1.8在实现上是不相同的。
HahsMap put过程
- 判断当前数组是否初始化。
- 如果 key 为空,则 put 一个空值进去。
- 根据 key 计算出 hashcode。
- 根据 hashcode 定位所在桶。
- 如果桶是一个链表则遍历里面的 hashcode,判断key是否和传入 key 相等。如果相等则进行覆盖,并返回原来的值。
- 如果桶是空的,说明当前位置没有数据存入,新增一个 entry 对象写入当前位置。
HashMap get过程
- 根据 key 计算出 hahscode,然后定位具体的桶。
- 判断该位置是否为链表。
- 不是链表就根据 key, hashcode 是否相等返回值。
- 若为链表则遍历直到key、hashcode相等返回值。
- 如果size为0直接返回null。
1.7的缺点是:当 hash 冲突严重时,在桶上形成的链表会变得越来越长,导致查询效率越来越低,时候就复杂的为 O(n) 。
1.8重点优化了这个查询效率。
当链表长度达到指定的阈值时,链表就被转换为红黑树。修改为红黑树之后查询效率提高到了 O(logn) 。
原因是:并发操作在 HashMap 扩容时会调用 resize()
方法,这样容易形成环形链表。
ConcurrentHashMap
专门用于解决并发问题。
ConcurrentHashMap 在1.7和1.8的实现上也有不同。
其底层结构和HashMap一样,都是数组+链表。
和HashMap区别是:
其 value
和链表都是 volatile
修饰的,保证了获取时代可见性。
从原理上讲:ConcurrentHashMap采用了分段锁技术。不像HashTable那样不管是put还是get操作都是同步处理。
ConcurrentHashMap在1.7中的问题:查询遍历链表效率太低。
1.8中抛弃了原有的Segment分段锁,而采用CAS + synchronized 来保证并发安全性。
独占锁是一种悲观锁,synchronized就是一种独占锁,会导致其它所有需要锁的线程挂起,等待持有锁的线程释放锁。
而另一个更加有效的锁就是乐观锁。所谓乐观锁就是,每次不加锁而是假设没有冲突而去完成某项操作,如果因为冲突失败就重试,直到成功为止。乐观锁用到的机制就是CAS,Compare and Swap(比较与交换)。
参考链接: HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你!
LinkedHashMap 原理
LinkedHashMap 是基于数据+双向链表实现的。
LinkedHashMap虽然增加了时间和空间的开销,但是通过维护一个运行于所有条目的双向链表,LinkedHashMap保证了元素的迭代顺序。
LinkedHashMap key 和value 允许为空,key重复后覆盖, 有序,非现场安全。
Entry有四个属性是从HashMap继承而来,分别如下:
- K key
- V value
- Entry<K, V> next
- int hash
其另外两个属性如下:
- Entry<K, V> before
- Entry<K, V> after
next
是用于维护HashMap指定table位置上连接Entry的顺序的。before
、After
用于维护Entry插入的先后顺序。
注意:循环双向链表头部存储的是最久访问的节点或是最先插入的节点,尾部为最近访问的或最近插入的节点。迭代器遍历方向是从链表头部开始到链表尾部结束。在链表尾部有一个空的header节点,该节点不存放key-value,为LinkedHashMap类的成员属性,循环双向链表的入口。
HashMap实现中有个init()方法,该方法只是提供子类实现相关的初始化调用。
LinekedHashMap 重写了init()方法,供其实现对Entry的初始化操作。
void init() {
header = new Entry<K,V>(-1, null, null, null);
header.before = header.after = header;
}
打赏: 微信
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。