HashTable

ConcurrentHashMap

结构

1.7

• Segment 数组 + HashEntry 数组 + 链表
• put头插法

每个segment都是一个锁ReentrantLock对象。

1.8

• Node 数组 + 链表 / 红黑树
• 尾插法

sizeCtl

sizeCtl为0，代表数组未初始化， 且数组的初始容量为16 sizeCtl为正数，如果数组未初始化，那么其记录的是数组的初始容量，如果数组已经初始化，那么其记录的是数组的扩容阈值 sizeCtl为-1，表示数组正在进行初始化 sizeCtl小于0，并且不是-1，表示数组正在扩容， -(1+n)，表示此时有n个线程正在共同完成数组的扩容操作

初始容量

1.7

• 默认容量16 * 2 = 32

  1.8

• 默认容量16

• 传入32，其实容量是64。
• put时候初始化

加锁逻辑

1.7加锁

先去加锁segment，tryLock，失败的话先去创建Entry对象。等拿到锁直接放到位置上。
如果cpu是多核就自旋64次，如果单核就直接lock()不自旋。

1.8加锁

锁node头结点

扩容

1.7

• 扩容：Segment 的个数一旦初始化就不能改变

  lastrun的作用

  

  1.8

• 多线程协助扩容

• 先put，然后判断是否树化，是否扩容
• 多线程协助扩容，任务最小是16个单元。
• 迁移过后节点放入forward节点

获取集合长度

1.7

1.8

• CounterCel初始容量是2.

• 有baseCount和一个CounterCell数组。各线程尝试去ConterCell上加一操作。
• 元素个数就累加求和

ConcurrentSkipListMap：结果排序（跳表）

ConcurrentSkipListMap 的key是有序的

set

CopyOnWriteArraySet

ConcurrentSkipListSet