HashMap和ConcurrentHashMap

1、HashMap非线程安全，ConcurrentHashMap线程安全

HashMap为什么非线程安全，我们暂且不考虑ConcurrentModificationException这一并发异常。

• 死循环

在HashMap扩容临界点时，如果两个线程都执行put操作，均进行扩容操作，并都遍历到同一个下标下的头结点，然后其中一个线程在完成指针赋值操作后挂起，另一个线程先顺利完成扩容，最终在两个线程都进行完transfer后，容易出现环形链表，而当线程再次get一个该链表中不存在的值时，就会陷入死循环。

• 数据丢失

再者，若两个线程均进行put操作，并且都取到了相同数组小标的链表头结点，那么后插入的将覆盖先插入的值，造成值丢失（实际应该像单线程时解决碰撞冲突）。

而ConcurrentHashMap则采用Node CAS Synchronized来保证并发安全。具体见：
https://blog.csdn.net/weixin_43878293/article/details/103516647

2、数据结构

HashMap使用底层使用一个数组，数组每个位置是一个链表，可以称之为一个哈希桶数组，链表的每个节点为一个Node，当拉链长度达到8时，Node节点链表便转换成红黑树节点TreeNode。

ConcurrentHashMap在数据结构方面和HashMap的差别在于，ConcurrentHashMap的红黑树对象是TreeBin，TreeBin中有TreeNode。

使用红黑树的一个考虑是空间换时间，当碰撞增多，拉链不断变长的情况下，链表遍历性能急剧下降，使用红黑树能够带来更高效的查询性能。

链表的查询复杂度为O(n)，红黑树的查询复杂度为O(log(n))，在n比较小时，使用链表遍历起来也比较快。

3、底层数组初始长度、扩容大小、负载因子、链表和红黑树转化

1）底层数组的初始长度默认均为16
2）扩容之后数组长度变为原来的2倍
3）负载因子默认为0.75
4）链表节点达到8个并且数组大小不小于64时，链表节点转化为红黑树节点
5）链表节点数下降为6时，红黑树节点转化为链表节点

容量的大小和hash函数的质量决定着数据分布上的均匀程度。初始长度默认为16、扩容之后数组长度变为2倍，这是有讲究的，可以看到长度一定是2的幂，这么做是出于在通过哈希值计算数组下标时，通过以下方式：

h & (table.length -1)

用于计算对象该放入的下标位置。2的幂减1的二进制形式全为1，在进行&操作时，其各个位均能起到做用，而不会浪费table的使用空间。

负载因子为0.75这是对时间和空间效率的一种平衡选择。

为什么使用8作为链表转化成红黑树的临界值，这里参考了概率学当中泊松分布，发生碰撞个数及其相应的概率

• 0: 0.60653066

• 1: 0.30326533

• 2: 0.07581633

• 3: 0.01263606

• 4: 0.00157952

• 5: 0.00015795

• 6: 0.00001316

• 7: 0.00000094

• 8: 0.00000006

也就是说，发生碰撞个数为8的概率为千万分之六。概率很小，在平常使用的HashMap中，碰撞个数基本不会达到这个值，如果真的达到了，基本说明哈希方法存在问题。

而在链表节点减少，为什么又是到6才转为链表？注意这样的话中间有一个过渡值7，这么做是为了避免因为一个值的增加和减少而导致频繁的转换。