Map集合源码阅读

ConcurrentHashMap-JDK1.7

1. ConcurrentHashMap不可有null的key或null的value
2. Segment数组无法扩容，Segment中的Hash表可以扩容
3. Segment继承ReentrantLock

初始化方法

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)

• 目的
  • 计算出segmentShift(以concurrencyLevel=16为例，此值为：32-4=28)
  • 计算出segmentMask(以concurrencyLevel=16为例，此值为：1111)
  • 计算每个Segment的桶数（cap）或者说key-value容量数（cap的最小值为：2）
  • 构建Segment数组，大小是 ssize，并初始化第0号Segment

• segmentShift和segmentMask的作用：计算key-value落在Segment数组的哪个下标号上

  CocurrentHashMap的put方法

  public V put(K key, V value)

• 计算key的hash值，通过segmentShift和sementMask将其映射到一个Segment上

• 若Segment没有初始化，则通过CAS方式进行初始化

• 执行Segment的put()方法

  Segment的put方法

  final V put(K key, int hash, V value, boolean onlyIfAbsent)

• 获取锁

  • 若直接获取锁，接着走下面的方法
  • 若没有立刻获得锁，循环重试获取锁，超过重试次数直接以lock()方式等待锁
• 定位key应该落在哪个桶上
• 执行插入逻辑
  • 若桶没有值，则直接插入即可
  • 若桶中有值，则需要遍历链表，需要插入时进行头插法，之后立即判断是否需要扩容

• 解锁

  get方法

  public V get(Object key)

• 定位Segment位置（这块源码有个SSHIFT不理解）

  • 若Segment还为null，或者key所在的Segment的Hash表的桶内无元素，直接返回null
• 遍历Segment的Hash表的桶内链表

  小结

1. ConcurrentHashMap由Segment数组组成，每个Segment数组里是个Hash表的结构
2. ConcurrentHashMap主要通过Segment（继承ReetrantLock）来实现分段加锁，提高并发

ConcurrentHashMap-JDK1.8

1. ConcurrentHashMap不可有null的key或null的value
2. 结构和JDK1.8的HashMap一致，
3. 通过代码控制并发

   初始化方法

   public ConcurrentHashMap(int initialCapacity) public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel)

• 这里我没有看懂具体计算cap的位操作。
• 但是最终的计算结果，都赋予 sizeCtl，其作用：用来控制table的初始化和扩容操作
• 具体Hash表的初始化均延迟到第一put操作

  put()方法

  public V put(K key, V value) final V putVal(K key, V value, boolean onlyIfAbsent)

1. 校验key和value不为null
2. 获取key的hash值
3. 进入一个死循环
   1. 若table没有被初始化，则执行initTable()操作
   2. 若table存在，但是key所落在的hash桶中无值，则CAS将这对key-value放入桶中
   3. 若table存在，但是头节点的hash值为-1（移动的状态），则帮助移动helpTransfer
   4. 若table存在，无上述问题，则synchronized锁住这个桶执行插入逻辑
      1. 头结点的hash值>=0,则是链表，可以正常遍历插入（尾插法）。
      2. 否则，必是一棵红黑树，则执行红黑树插入
      3. 上述 i 和 ii，执行完后。若桶是链表且到达8个节点时，则执行桶的树化操作treeifyBin
4. 最后，累加key-value数量，到达阈值则扩容

树化treeifyBin()

private final void treeifyBin(Node[] tab, int index)

• 想强调的是树化需要当表长度>64时树化

• 否则，只是tryPresize(n << 1)扩容

  get()方法

  public V get(Object key)

• 定位桶的位置

• 头节点hash>=0,遍历链表即可
• 否则，通过红黑树查找

  小结

1. JDK1.8的ConcurrentHashMap之后源码要再读一下。扩容，初始化问题都没有搞明白

参考文章

• https://javadoop.com/post/hashmap