HashTable与ConcurrentHashMap比较

1.HashTable与ConcurrentHashMap都是线程安全的Map集合。

2.HashTable与ConcurrentHashMap的键和值都不能为空。

3.HashTable并发度低，整个HashTable对应一把锁，同一时刻，只能有一个线程操作它。并发度很低。

4._1.8之前ConcurrentHashMap使用了Segment+数组+链表的结构，每个Segment对应一把锁，如果多个线程访问不同的Segment，则不会冲突。

5._1.8开始ConcurrentHashMap将数组的每个头节点作为锁，如果多个线程访问的头节点不同，则不会冲突。

扩容

HashTable初始容量为11，每次扩容都是上次的容量*2+1；

1.7 初始化：饿汉式。

ConcurrentHashMap是一个Segment数组，Segment数组每个元素中都会套一个小数组，如果小数组中有索引冲突，则会构成一个链表。Segment数组（并发度）不能扩容。

Segment索引计算：线程key——>原始hash——>二次hash——>找二次hash值的二进制的高n位（n为数组容量的指数），转换成十进制，得到Segment下标。——>桶下标：小数组位置（找二次哈希值的二进制最低n位，n为小数组长度的指数）

小数组扩容：元素个数超过容量的3/4，容量翻倍。插入元素使用头插法，但是因为加了锁，所以不会造成死链。

1.8 初始化：懒汉式。

尾插法。只要满3/4就会扩容。

ConcurrentHashMap容量 * 3/4 > 元素个数。

只要操作的不是同一个链表头，就可以并发执行，提高性能。

扩容：到达扩容阈值后，创建出新数组，容量翻倍，将旧数组每个链表的数据迁移到新链表（从后往前），形成新的链表。旧的链表头部变成ForwardingNode，显示此链表已被处理过。旧数组的所有链表头部全都变成ForwardingNode后，表示数组全部处理完成，替换为新的数组。

扩容时的并发问题：

get：当链表还未替换完成时，新的线程要读取链表数据？通过链表头是否为ForwardingNode判断链表内容是否被替换。如果链表还未被替换，则直接get到旧的链表数据；如果要get的数据已经迁移到新的table，查询线程去get替换过的新的链表数据。扩容线程在进行链表迁移时，next指向发生变化，需要重新创建节点对象。

put：当要put的对象还未被替换且节点不需要变化，put可以并发执行；当要put的对象节点需要变化，会被链表头加锁阻塞；当要put的节点已经完成了变化，不能去新的表中去put，而是会帮忙迁移未替换完的数据。