文章来源
1. 谈谈你理解的 HashMap，讲讲其中的 get put 过程
HashMap的结构是数组table + 链表Entry。
put过程：
(1) 对key进行hash；
(2) 通过hash定位数据应该在数组中的下标index，获取链表Entry；
(3) 如果Entry为null，需要新增一个Entry，指向index这个位置；
(4) Entry不为null，遍历Entry，如果找到key相同，hash相同，则覆盖原值，否则新建一个Entry节点，指向index位置，next指向之前的Entry节点。
get过程：
(1) 对key进行hash；
(2) 通过hash获取到在数组中的下标index，获取到链表Entry；
(3) 如果Entry为null，直接返回null；
(4) Entry不为null，遍历Entry，如果key相同且hash相同，返回Entry的value。
2. 1.8 做了什么优化？
1.7的缺点：
当Hash冲突严重的时候，在桶上形成的链表会越来越长，查询的效率极低，时间复杂度退化到O(N)。
1.8优化：
1.8存储过程类似上面步骤，但是存储结构有变化，增加了一个链表长度的阈值字段，值为8，如果链表长度超过8，就将链表转为红黑树结构。
3. HashMap是线程安全的嘛？不安全会导致哪些问题？
HashMap是非线程安全的。
高并发的时候会形成环形链表，这样遍历的时候会导致死循环。
4. 有没有线程安全的并发容器？
ConcurrentHashMap。
5. ConcurrentHashMap 是如何实现的？ 1.7、1.8 实现有何不同？为什么这么做？
1.7采用分段锁。
put过程：
(1) 获取Segment锁，如果没有获取到，自旋等待，确保能获取到锁；
(2) 通过key的hash定位到当前Segment下table的Entry；
(3) Entry为null，新建一个加入到table下；
(4) 不为null，遍历找到key相同hash相同的Entry，返回Entry的value，没找到新建一个Entry，加到table下，next指向之前的Entry；
(5) 释放锁。
get过程：
(1) 通过key的hash定位到Segment；
(2) 在Segment下通过hash定位到Entry，遍历Entry，如果key相同并且hash相同，返回value。
1.8采用CAS + synchronized。
同样是对查询效率做了优化。和HashMap一样，当链表长度大于阈值的时候转为红黑树保存数据。
好处：
红黑树保证了查询效率时间复杂度O(logN)。
网友评论