1.7中的ConcurrentHashMap整体上可以看作是一个双层数组的结构。外层是Segment数组，每个Segment内是一个HashEntry数组，类似于一个HashMap，数组的每个Segment在操作时都相对独立。Segment在初始化后不允许扩容，HashEntry允许扩容。在加锁的过程中只会对某个Segment加锁而不是整个数组。

构造方法

  1. //无参构造器会用默认参数调用该构造器
  2. //默认参数为initialCapacity=16，loadFactor=0.75f，concurrencyLevel=16
  3. public ConcurrentHashMap(int initialCapacity,
  4.                              float loadFactor, int concurrencyLevel) {
  5.         if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
  6.             throw new IllegalArgumentException();
  7.         if (concurrencyLevel > MAX_SEGMENTS)
  8.             concurrencyLevel = MAX_SEGMENTS;
  9.         // Find power-of-two sizes best matching arguments
  10.         int sshift = 0;
  11.         //Segment数组的长度
  12.         int ssize = 1;
  13.         //Segment数组的长度要为2的n次幂且大于等于concurrencyLevel
  14.         while (ssize < concurrencyLevel) {
  15.             ++sshift;
  16.             ssize <<= 1;
  17.         }
  18.         this.segmentShift = 32 - sshift;
  19.         this.segmentMask = ssize - 1;
  20.         if (initialCapacity > MAXIMUM_CAPACITY)
  21.             initialCapacity = MAXIMUM_CAPACITY;
  22.         //c用来计算Segment内数组的大小
  23.         int c = initialCapacity / ssize;
  24.         if (c * ssize < initialCapacity)
  25.             ++c;
  26.         //cap为真正的Segment内的数组大小 需要调整为2的n次幂
  27.         int cap = MIN_SEGMENT_TABLE_CAPACITY;
  28.         while (cap < c)
  29.             cap <<= 1;
  30.         //创建0位置的Segment
  31.         Segment<K,V> s0 =
  32.             new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
  33.                              (HashEntry<K,V>[])new HashEntry[cap]);
  34.         //创建Segment数组
  35.         Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
  36.         //将s0赋值给Segment[0]
  37.         UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
  38.         this.segments = ss;
  39.     }

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);
  6.         //j是找到的Segment数组索引
  7.         int j = (hash >>> segmentShift) & segmentMask;
  8.         //判断插入的位置是否为null，为null则创建一个Segment
  9.         if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
  10.              (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
  11.             s = ensureSegment(j);
  12.         return s.put(key, hash, value, false);
  13.     }
  15. private Segment<K,V> ensureSegment(int k) {
  16.         final Segment<K,V>[] ss = this.segments;
  17.         long u = (k << SSHIFT) + SBASE; // raw offset
  18.         Segment<K,V> seg;
  19.         //为保证在当前位置只能有一个Segment被创建，这里用UNSAFE，
  20.         if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
  21.             Segment<K,V> proto = ss[0]; // use segment 0 as prototype
  22.             //从Segment[0]获取参数 HashEntry数组的大小和加载因子
  23.             int cap = proto.table.length;
  24.             float lf = proto.loadFactor;
  25.             //计算扩容阈值
  26.             int threshold = (int)(cap * lf);
  27.             HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
  28.             //再次检测当前位置是否已经有其他线程创造的Segment
  29.             if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
  30.                 == null) { // recheck
  31.                 Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
  32.                 //这里用cas保证写入成功
  33.                 while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
  34.                        == null) {
  35.                     if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
  36.                         break;
  37.                 }
  38.             }
  39.         }
  40.         return seg;
  41.     }
  43. final V put(K key, int hash, V value, boolean onlyIfAbsent) {
  44.             //tryLock 尝试获取锁，即使获取失败，后面的代码也会继续执行
  45.             //Lock 获取锁，若获取失败，则进入阻塞状态
  46.             //此时若尝试获取锁失败，则会引入自旋锁，在scanAndLockForPut实现
  47.             HashEntry<K,V> node = tryLock() ? null :
  48.                 scanAndLockForPut(key, hash, value);
  49.             V oldValue;
  50.             //是HashEntry链表插入，和hashMap差不多
  51.             try {
  52.                 HashEntry<K,V>[] tab = table;
  53.                 int index = (tab.length - 1) & hash;
  54.                 HashEntry<K,V> first = entryAt(tab, index);
  55.                 for (HashEntry<K,V> e = first;;) {
  56.                     if (e != null) {
  57.                         K k;
  58.                         if ((k = e.key) == key ||
  59.                             (e.hash == hash && key.equals(k))) {
  60.                             oldValue = e.value;
  61.                             if (!onlyIfAbsent) {
  62.                                 e.value = value;
  63.                                 ++modCount;
  64.                             }
  65.                             break;
  66.                         }
  67.                         e = e.next;
  68.                     }
  69.                     else {
  70.                         if (node != null)
  71.                             node.setNext(first);
  72.                         else
  73.                             node = new HashEntry<K,V>(hash, key, value, first);
  74.                         int c = count + 1;
  75.                         if (c > threshold && tab.length < MAXIMUM_CAPACITY)
  76.                             rehash(node);
  77.                         else
  78.                             setEntryAt(tab, index, node);
  79.                         ++modCount;
  80.                         count = c;
  81.                         oldValue = null;
  82.                         break;
  83.                     }
  84.                 }
  85.             } finally {
  86.                 unlock();
  87.             }
  88.             return oldValue;
  89.         }
  91. private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
  92.             //获取要插入的Segment的第一个节点
  93.             HashEntry<K,V> first = entryForHash(this, hash);
  94.             HashEntry<K,V> e = first;
  95.             HashEntry<K,V> node = null;
  96.             //while循环为一直尝试获取锁 使用tryLock可以在未获取锁的时候进行
  97.             //一些其它操作提高效率
  98.             //retries变量起到引导作用 判断当前应该进行什么操作
  99.             int retries = -1; // negative while locating node
  100.             while (!tryLock()) {
  101.                 HashEntry<K,V> f; // to recheck first below
  102.                 //若retries小于0 则进行遍历链表操作
  103.                 if (retries < 0) {
  104.                     if (e == null) {//若遍历到表尾则创建HashEntry
  105.                         if (node == null) // speculatively create node
  106.                             node = new HashEntry<K,V>(hash, key, value, null);
  107.                         retries = 0;
  108.                     }
  109.                     else if (key.equals(e.key))//找到key相同的HashEntry 将retries置为0
  110.                         retries = 0;
  111.                     else
  112.                         e = e.next;
  113.                 }
  114.                 //此时为遍历链表的操作已经结束还未获取到锁 不能一直处于循环状态占用CPU内存
  115.                 //每进行一次循环会让retries变量+1 当retries大于64时 调用Lock方法阻塞
  116.                 else if (++retries > MAX_SCAN_RETRIES) {
  117.                     lock();
  118.                     break;
  119.                 }
  120.                 ////判断在循环等待的过程中 链表结构是否发生了变化即头结点发生改变
  121.                 //若改变则将retries置为-1 重新进行遍历链表操作
  122.                 //为了避免在判断头结点是否改变的过程中 释放的锁被其它线程抢走 只在retries为奇数时判断
  123.                 else if ((retries & 1) == 0 &&
  124.                          (f = entryForHash(this, hash)) != first) {
  125.                     e = first = f; // re-traverse if entry changed
  126.                     retries = -1;
  127.                 }
  128.             }
  129.             return node;
  130.         }