数据结构

由 Segment数组 + HashEntry 数组 构成 HashEntry 存键值对

一个concurrentHashMap 饱和Segment数组
一个Segmengt包含一个HashEntry数组
一个HashEntry元素是一个链表
锁的获取时在 segment 上的竞争
图示：
image.png

HashEntry

  1. static final class HashEntry<K,V> {
  2.         final int hash;
  3.         final K key;
  4.         volatile V value;
  5.         volatile HashEntry<K,V> next;
  7.         HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
  8.             this.hash = hash;
  9.             this.key = key;
  10.             this.value = value;
  11.             this.next = next;
  12.         }

put操作

  1. public V put(K key, V value) {
  2.     Segment<K,V> s;
  3.     if (value == null)
  4.         throw new NullPointerException();
  5.     int hash = hash(key);
  7.     // 通过位运算确定哪个segment,
  8.     int j = (hash >>> segmentShift) & segmentMask;
  11.     // 通过unsafe 获取
  12.     if ((s = (Segment<K,V>)UNSAFE.getObject          
  13.          (segments, (j << SSHIFT) + SBASE)) == null) 
  14.         s = ensureSegment(j);//初始化一个segment
  16.     //调用Segment的put方法
  17.     return s.put(key, hash, value, false);
  18. }
  1. 先算hash
  2. 确定segment的下表

  3. 获取segment，没有就会创建，CAS的方式获取

    Segment的put方法

    ```java final V put(K key, int hash, V value, boolean onlyIfAbsent) { //对segment加锁 HashEntry node = tryLock() ? null :

    1.  scanAndLockForPut(key, hash, value);

    V oldValue; try {

    1.  //
    2.  HashEntry<K,V>[] tab = table;
    3.  int index = (tab.length - 1) & hash;
    5.  //获取头结点
    6.  HashEntry<K,V> first = entryAt(tab, index);
    8.  for (HashEntry<K,V> e = first;;) {//开始遍历first为头结点的链表
    9.      if (e != null) {//<1>
    10.          //
    11.          //依据onlyIfAbsent来判断是否覆盖已有的value值
    12.          K k;
    13.          if ((k = e.key) == key ||
    14.              (e.hash == hash && key.equals(k))) {  
    15.              oldValue = e.value;
    16.              if (!onlyIfAbsent) {
    17.                  e.value = value;
    18.                  ++modCount;
    19.              }
    20.              break;
    21.          }
    22.          e = e.next;//说明当前e节点对应的key不是需要的
    23.      }
    24.      else {//头插法
    25.          if (node != null) 
    26.              node.setNext(first);
    27.          else     
    28.              node = new HashEntry<K,V>(hash, key, value, first);
    29.          int c = count + 1; 
    30.          if (c > threshold && tab.length < MAXIMUM_CAPACITY)//判断是否需要进行扩容
    32.              //扩容，node插入到新的数组中。
    34.              rehash(node);
    35.          else
    36.              setEntryAt(tab, index, node);
    37.          ++modCount;
    38.          count = c;
    39.          oldValue = null;
    40.          break;
    41.      }
    42.  }

    } finally {

    1.  unlock();

    } return oldValue; }

```

  1. 先获取segment的锁
  2. 找到k所在HashEntry 数组的下表
  3. 获取这个HashEntry 的头节点
  4. 开始遍历
  5. 采用头插法