1.map类图

image.png

2.hashtable,hashmap,treemap区别

hashtable线程安全，key和value不能为空，concurrenthashmapkey和value也不能为空
hashmap线程不安全，key和value可为空
treemap基于红黑树实现的有序map
linkedhashmap：基于put的顺序排序，场景：我们构建一个空间占用敏感的资源池，希望可 以自动将最不常被访问的对象释放掉，这就可以利用LinkedHashMap 提供的机制来实现。

3. hashmap数据结构

1. 数组+链表，链表长度超过8变成树
2. hashmap如何确认hash桶位置
   key的hashCode值、高位运算、取模运算
   2.1 取模运算是（h & (length-1)）HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率
   2.2 高位运算：这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，参考文章：https://tech.meituan.com/2016/06/24/java-hashmap.html

3. put操作流程

   
   image.png
   

   4.扩容动作
   1.7 扩容，重新计算索引位置，移动元素。元素都插入在链表表头，链表的元素扩容后会倒序
   1.8扩容，过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”

4. hashmap为什么会死循环
   该方法实现的机制就是将每个链表转化到新链表，并且链表中的位置发生反转，而这在多线程情况下是很容易造成链表回路，从而发生 get() 死循环。所以只要保证建新链时还是按照原来的顺序的话就不会产生循环（JDK 8 的改进）

4. FAQ

4.1 知道jdk1.8中hashmap改了啥
由数组+链表的结构改为数组+链表+红黑树。
优化了高位运算的hash算法：h^(h>>>16)
扩容后，元素要么是在原位置，要么是在原位置再移动2次幂的位置，且链表顺序不变
4.2 为什么在解决hash冲突的时候，不直接用红黑树?而选择先用链表，再转红黑树
因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。 当元素小于8个当时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于8个的时候，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了
4.3 我不用红黑树，用二叉查找树可以么
可以。但是二叉查找树在特殊情况下会变成一条线性结构
红黑树说明：https://tech.meituan.com/2016/12/02/redblack-tree.html
https://blog.csdn.net/chen_zhang_yu/article/details/52415077
参考：https://zhuanlan.zhihu.com/p/76735726

4. concurrentHashmap

1. 1.7采用segment分离锁，1.8采取CAS+synchronize模式(initTable用CAS控制只有一个线程初始化，put先通过volitale拿到node数组对应的元素，然后synchronize锁住这个元素进行操作链表)
2. size方法，1.7先尝试统计每个segement的大小，如果中间发生了变化，加锁重新计算size。 1.8 put方法和remove方法都会通过addCount方法维护Map的size。size方法通过sumCount获取由addCount方法维护的Map的size
3. 扩容
   参考：http://zhouqing86.github.io/2019/06/01/java-ConcurrentHashMap/