ConcurrentHashMap
HashMap和ConcurrentHashMap的区别
主要区别就是hashmap线程不安全，ConcurrentHashMap线程安全
HashMap线程不安全，有以下两个问题
put覆盖问题
比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。
死循环问题
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历数组，仅遍历数组下标元素
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
// 只有产生了新的hash表才需要重新计算hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 这里读者可以验证：i = oldIndex 或 i = oldIndex + oldCapacity
int i = indexFor(e.hash, newCapacity);
// 链表前插法
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
死循环问题是指如果两个线程同时对hashmap进行扩容，因为hashmap进行元素复制的方法是头插法，会产生next指针成环的问题，导致后面的数据无法访问到。
这个视频讲得很清楚
HashTable的效率又太低
因为hashtable的方法用synchronized修饰，相当于synchronized(this)，导致只能有一个线程访问hashtable，效率太低
ConcurrentHashMap原理
在JDK7中原理，采用数组+Segment的段锁的数据结构，其中Segment继承ReentrantLock
在JDK8中，采用数组+链表+红黑树的数据结构，采用CAS+synchronized保证线程安全
JDK7对Segment进行加锁，JDK8对数组中每个元素(Node)加锁
查询时间复杂度 遍历链表O(N), 红黑树(O(logN))
具体原理请参考下文
https://blog.csdn.net/cai519678181/article/details/105165853/?utm_medium=distribute.pc_relevant.none-task-blog-2defaultbaidujs_baidulandingword~default-4--blog-89047318.235v43pc_blog_bottom_relevance_base4&spm=1001.2101.3001.4242.3&utm_relevant_index=7
https://www.cnblogs.com/jxxblogs/p/12517197.html
标签：ConcurrentHashMap,Java,插入,next,链表,并发,线程,hash From： https://www.cnblogs.com/DCFV/p/18263603