HashMap、TreeMap、HashTable、ConcurrentHashMap

HashMap、TreeMap、HashTable、ConcurrentHashMap异同及底层实现原理

HashMap、TreeMap、HashTable
1.1 区别：
（1）HashMap没有synchronized修饰，线程不安全，HashTable线程安全
（2）HashMap允许存储null值的key和value，HashTable不允许
（3）Hashtable、HashMap具有无序特性。TreeMap是利用红黑树实现的（树中的每个节点的值都会大于或等于它的左子树中的所有节点的值，并且小于或等于它的右子树中的所有节点的值），实现了SortMap接口，能够对保存的记录根据键进行排序。所以一般需求排序的情况下首选TreeMap，默认按键的升序排序（深度优先搜索），也可以自定义实现Comparator接口实现排序方式。

1.2 底层实现：
数组+链表
jdk8开始当链表高度到8，数组长度超过64时，链表转红黑树，元素以内部类Node结点存储

1.3 存储过程：
- 计算key的hash值，二次hash然后对数组长度取模，对应到数组下标
- 如果没有产生hash冲突（下标位置没有元素），则直接创建Node存入数组
- 如果有hash冲突，先进行equals比较，相同则取代（覆盖）该元素，不同则判断链表高度插入链表，链表高度达到8，并且数组长度到64则转表为红黑树，长度低于6则将红黑树转回链表
- 当key为null时，存储在数组下标为0的位置
1.4 扩容问题
HashMap：数组初始默认长度为16，负载因子0.75，每次扩容为原来的2倍；

1.5 举例说明HashMap为什么线程不安全
- 比如说现在有一个长度为8的map，map已经存了key为1、9的两个值，他们都会在map的table[1]上。
- 首先线程1 put一个key=17的值，当程序运行到判断key=9的下一个节点为null准备把key=17的值设置为它的下一个节点时，线程让出资源
- 此时执行线程2，对map put一个key=25的数据，这个数据正常作为key=9的next正常插入
- 线程1再次拿到资源继续执行，设置key=9的next为key=17，这样线程2设置的key=25就被覆盖了
1.6 jdk7 hashmap死循环问题
- jdk7扩容就是遍历旧的table进新的table中，找到在新的table下的位置，并把新table对应位置的元素设置成当前元素的next，就是所谓的头插法！遍历当前Entry前先把它的next取出来用于下一次遍历（这是造成死循环的关键！因为其他线程可能对next的next进行修改）
- 造成死循环的原因主要在于线程1执行key=9,并取出他的next(key=25)作为下次遍历后，线程1交出了执行权休息去了，而接着线程2吭哧吭哧的执行完扩容，扩容由于采用头插法，此时key=25那个Entry对象的next是key=9
- 所以当线程1继续执行，到遍历next(key=25)时他的next变成了key=9,最终造成了两个Entry互相引用，如果后面调用map.get(41)就会刚好查询table[9]，然后遍历这个链表，造成死循环！
- 而jdk8采用的是尾部插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了，但依然没有解决数据丢失（覆盖）问题，依然线程不安全。

2.ConcurrentHashMap
jdk7：

数据结构：ReentrantLock + Segment + HashEntry，一个Segment中包含一个HashEntry数组，每个HashEntry又是一个链表结构（跟HashMap十分类似，只是多了一个Segment）
锁：Segment分段锁 Segment继承于ReentrantLock，锁定操作的Segment，其他的Segment不受影响，并发度为Segment的个数，可以通过构造函数锁定，数组扩容不会影响其他的Segment
元素查询：两次Hash。第一次Hash定位到Segment（找到属于哪个分段），第二次Hash定位到元素所在的链表的头部（即在数组中的下标）
对于get读操作则不加锁，利用volatile保证可见性

jdk8：

数据结构：synchronized + CAS（乐观锁） + Node + 红黑树
锁：锁的是链表的头结点，不影响其他元素的读写，锁粒度更细效率更高（因为Segment锁的是一个分段，而一个分段可以包含很多个链表），扩容时，阻塞所有的读写操作，并发扩容（synchronized）。
查找、替换、赋值操作都使用CAS，只有在无法保证线程安全的操作（例如扩容、hash冲突）时使用synchronized
读操作无锁：Node的val和next使用volatile修饰，读写线程时对该变量可见
数组用volatile修饰，把证扩容时被读线程感知。
关于CAS：https://blog.csdn.net/u011277123/article/details/90699619
ConcurrentHashMap 的 Put 方法过程，具体到在哪里有 Synchronize 和 CAS 操作（大华面试）
CAS：在判断数组中当前位置为null的时候，使用CAS来把这个新的Node写入数组中对应的位置
synchronized ：当数组中的指定位置不为空时，通过加锁来添加这个节点进入数组(链表<8)或者是红黑树（链表>=8）
源码参考链接：https://blog.csdn.net/willlu10/article/details/106721364/