HashMap和ConcurrentHashMap

1. HashMap

1.1 HashMap 结构

HashMap 底层是一个数组结构，而每一个数组元素后面又是一个链表，HashMap有两个参数影响他的性能，一个是初始容量和加载因子，当HashMap中的条目数量达到了初始容量与加载因子的乘积之后就会发生rehash（扩容），默认的初始容量是16，加载因子是0.75f，即条目数达到了12后，将会发生扩容。

HashMap的寻址方式：对于一个新插入的数据，需将他的Key按照一定的Hash规则计算出的值并对数组长度进行取模运算，得到它插在数组长度中的index，在计算机中取模的代价远远高于位运算代价，因此HashMap要求我们数组的长度为2^n，此时它将key的hash值与2^(n-1)进行与运算得到的结果跟与2^n进行取模元素的值相同。但HashMap并不要求用户在初始化时要求用户传入一个2^n的整数，而在初始化时根据传入的值计算（tableSizefor方法）出一个2^n的整数。

1.2 HashMap正常扩容

最开始是key为5和9的元素在索引1的链表上，当插入key为11的元素后，将发生扩容，此时数组长度加倍，假设5和9的rehash值还为1，而11的rehash值为3，最后构成最后的一个新的HashMap。

1.3 HashMap扩容时出现死循环问题

假设有两个线程同时执行了put操作并同时触发了扩容操作，上面为线程一，下面为线程二，假设线程一执行到了申请两倍容量数组，准备处理第一个元素5，并将的下一个指针指向了他的下一个元素9。因为线程分配的时间片用完，线程暂停，而线程二开始执行，并执行完了整个操作，如上图所示。

此时线程一唤醒了，将5放在线程一申请的数组的索引1的首部，并将指针指向下一个要处理的元素9。

线程一处理完5后继续处理9，此时将线程一创建的数组的索引1指向9，并将next指向线程二新增的下一个元素5。

接着线程一继续处理5，并将数组索引1指向5，这个时候就会出现循环链表，因为刚刚9是指向5的，现在5又指向9。而11这个元素无法加入线程一这个数组里面了。

2. ConcurrentHashMap

Java7的ConcurrentHashMap最外层是一个Segment数组，每个Segment里面又包含了一个和HashMap类似的结构。segment继承至ReentrantLock，理论上允许的并发数和segment相同。

Java8为了进一步提高并发性，废弃了segment数组，直接使用一个大的数组，Java8在链表长度超过8时，将链表转换成红黑树，时间复杂度由O(n)变成了O(logn)。

3. HashMap和ConcurrentHashMap区别

1. HashMap不是线程安全的，ConcurrentHashMap是线程安全的。
2. HashMap运行key和value为空，而ConcurrentHashMap是不允许的。
3. HashMap在通过iterator遍历的同时，不允许HashMap修改，而ConcurrentHashMap遍历的时候，是允许的，而且对后续操作是可见的。