Java map介绍

HashMap介绍

基本实现原理

• jdk1.7是数组+链表实现。
• jdk1.8是数组+链表+红黑树实现，链表长度达到8会转成红黑树。

一些扩展知识

• 为啥使用红黑树不用AVL树：红黑树的平衡性相对avl来说稍差，但是旋转操作更少，插入和删除效率更高。
• 为啥每次扩容2倍：方便位运算，以及降低hash冲突（初始容量是16）。
• 为啥并发下会出现死循环：1.7版本之前hash冲突是使用头插法，在多线程并发同时扩容时可能会出现死循环。1.8版本使用尾插法解决。

ConcurrentHashMap介绍

基本实现原理

• jdk1.7采用分段锁，内部是是个Segment数组，Segment里面是一个数组+链表。Segment继承了ReentrantLock。往map里面put数据的时候，会先定位数据在哪个Segment上，然后对这个Segment进行加锁
• jdk1.8是采用cas+synchronized，在没有hash冲突时，使用cas将元素放到数组对应的位置上中。当出现hash冲突时，会使用synchronized对数组中对应位置上的node节点加锁。

一些扩展知识

• 扩容加速：扩容时其它线程写操作会协助扩容，而不是阻塞等待
• 计数器优化：采用了longadder的思想，空间换时间，将个数分散到一个数组中，不同线程对不同的槽位进行累加，减少并发度，从而达到更高的性能
• 为什么key和val不允许为null：在多线程并发情况下，null会带来二义性。当我们通过get获取到key的value为null时，你无法判断是put的时候value为null，还是这个key本身就不在map里面