0. HashMap和HashTable

• HashMap线程不安全
  多线程下HashMap的put操作可能导致Entry链表形成环形数据结构，next节点永不为空，就形成了死循环获取Entry，例如：

final HashMap<String, String> map = new HashMap<>(2);
        Thread t = new Thread(() -> {
            for (int i = 0; i < 10000; i++) {
                new Thread(() -> map.put(UUID.randomUUID().toString(), ""), "ftf" + i).start();
            }
        }, "tft");
        t.start();
        t.join();

• HashTable用Synchronized保证线程安全，线程激烈竞争时效率低下。

1. ConcurrentHashMap的结构

• 由Segment数组和HashEntry数组组成
  • Segment
    • 一种ReentrantLock
    • 作为锁的角色
    • 数组结构，链表结构
  • HashEntry
    • 用于存储键值对
    • 一个Segment包含一个HashEntry
    • 一个HashEntry是一个链表结构的元素

• 每个Segment守护着一个HashEntry数组的元素，修改HashSet前要现获取对应的Segment锁。

  
  image.png

2. ConcurrentHashMap初始化

• 用initialCapacity，loadFactor，ConcurrencyLevel几个参数来初始化Segment数组，段偏移量segmentShift，段掩码segmentMask和每个segment里面的HashEntry来实现的

2.1 初始化segment数组

• segment数组长度通过concurrencyLevel计算得到
• 数组长度是大于concurrencyLevel的最小2的N次方
• 长度最大值是2^16 = 65536

2.2 segmentShift和segmentMask初始化

• sshift等于ssize从1左移的位数，默认等于4（concurrencyLevel默认等于16，左移4位）
• segmentShift用于定位参与散列运算的位数，等于32 - sshift，默认也就是28
• segmentMask是散列运算的掩码，等于ssize - 1，默认也就是15
• ssize最大值65536，所以segmentShift最大值16，segmentMask最大值65535

2.3 初始化每个segment

• 以两个参数初始化每个segment
  • initialCapacity是ConcurrentHashMap的初始化容量
  • loadfactor是每个segment的负载因子
• HashEntry数组长度cap等于initialCapacity除以ssize的倍数c，c大于1就取大于等于c的2^N
• segment容量threshold = (int) cap * loadFactory，默认initialCapacity=16，loadfactory=0.75，cap=1，threshold=0

2.4 定位Segment

• 插入和获取元素的时候，需要先通过Hash算法定位Segment
• ConcurrentHashMap会对元素的hashCode进行再一次Hash，目的是减少Hash冲突
• 定位segment的hash算法：(hash >>> segmentShift) & segmentMask

3. ConcurrentHashMap的操作

• get操作
  • 经过一次再散列，通过这个散列值定位到Segment，再通过散列算法定位到元素。
  • 高效，不需要加锁，除非读到了空值再加锁重读
  • get方法用到的共享变量都定义为volatile类型，例如Segment大小，存储HashEntry的value
• put操作
  • put操作要加锁
  • 两步：
    • 判断是否需要扩容
    • 扩容：
      • 先创建一个容量是原容量两倍的数组，再将原数组元素散列后插入新数组
      • 不会对整个容器扩容，只对某个segment扩容
• size操作
  • 先尝试2次通过不所处Segment的方式统计各Segment大小，如果统计过程中容器count发生了变化，再通过加锁的方式统计所有Segment大小
  • 判断count发生变化用了，modCount变量（就是CAS咯）