声明：本文转载自https://my.oschina.net/u/3748347/blog/3080609，转载目的在于传递更多信息，仅供学习交流之用。如有侵权行为，请联系我，我会及时删除。
HashMap是一个线程不安全的类，在并发情况下会产生很多问题，详情可以参考HashMap 源码解析；HashTable是线程安全的类，但是它使用的是synchronized来保证线程安全，线程竞争激烈的情况下效率非常低下。在jdk1.5的时候引入了ConcurrentHashMap，这也是一个线程安全的类，它使用了分段锁的技术来提升并发访问效率。
HashTable容器在竞争激烈的并发环境下表现出效率低下的原因是所有访问HashTable的 线程都必须竞争同一把锁，假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么 当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效提高并 发访问效率，这就是ConcurrentHashMap所使用的锁分段技术。
在jdk1.7及以前ConcurrentHashMap采用Segment数组结构和HashEntry数组结构组成，之后采用的是和HashMap一样的结构。
采用Segment数组结构和HashEntry数组结构组成，Segment数组的大小就是ConcurrentHashMap的并发度。Segment继承自ReentrantLock，所以他本身就是一个锁。Segment数组一旦初始化后就不会再进行扩容，这也是jdk1.8去掉他的原因。Segment里面又包含了一个table数组，这个数组是可以扩容的。
如图我们在定位数据的时候需要对key的hash值进行两次寻址操作，第一次找到在Segment数组的位置，第二次找到在table数组中的位置。
// 直接继承自ReentrantLock，所以一个Segment本身就是一个锁
static final class Segment<K,V> extends ReentrantLock implements Serializable {
...
// table数组
transient volatile HashEntry<K,V>[] table;
// 一个Segment内的元素个数
transient int count;
// 扩容阈值
transient int threshold;
// 扩容因子
final float loadFactor;
Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
this.loadFactor = lf;
this.threshold = threshold;
this.table = tab;
}
...
我们发现Segment直接继承自ReentrantLock，所以一个Segment本身就是一个锁。所以Segment数组的长度大小直接影响了ConcurrentHashMap的并发度。还有每个Segment单独维护了扩容阈值，扩容因子，所以每个Segment的扩容操作时完全独立互不干扰的。
static final class HashEntry<K,V> {
// 不可变
final int hash;
final K key;
// volatile保证可见性，这样我们在get操作时就不用加锁了
volatile V value;
volatile HashEntry<K,V> next;
HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
}
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
// 参数校验
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
// 并发度控制，最大是65535
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// Find power-of-two sizes best matching arguments
// 等于ssize从1向左移位的 次数
int sshift = 0;
int ssize = 1;
// 找出最接近concurrencyLevel的2的n次幂的数值
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
// 这里之所 以用32是因为ConcurrentHashMap里的hash()方法输出的最大数是32位的
this.segmentShift = 32 - sshift;
// 散列运算的掩码，等于ssize减1
this.segmentMask = ssize - 1;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
// 里HashEntry数组的长度度，它等于initialCapacity除以ssize的倍数c，如果c大于1，就会取大于等于c的2的N次方值，所以cap不是1，就是2的N次方。
int cap = MIN_SEGMENT_TABLE_CAPACITY;
// 保证HashEntry数组大小一定是2的n次幂
while (cap < c)
cap <<= 1;
// create segments and segments[0]
// 初始化Segment数组，并实际只填充Segment数组的第0个元素。
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
通过代码我们可以看出，在构造ConcurrentHashMap的时候我们就会完成以下件事情：
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
// 1. 先获取key的hash值
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
// 2. 定位到Segment
s = ensureSegment(j);
// 3.调用Segment的put方法
return s.put(key, hash, value, false);
}
主要流程是：
private int hash(Object k) {
int h = hashSeed;
if ((0 != h) && (k instanceof String)) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// Spread bits to regularize both segment and index locations,
// using variant of single-word Wang/Jenkins hash.
h += (h << 15) ^ 0xffffcd7d;
h ^= (h >>> 10);
h += (h << 3);
h ^= (h >>> 6);
h += (h << 2) + (h << 14);
return h ^ (h >>> 16);
}
这个方法大致思路是：先拿到key的hashCode，然后对这个值进行再散列。
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 1. 加锁
HashEntry<K,V> node = tryLock() ? null :
// scanAndLockForPut在没有获取到锁的情况下，去查询key是否存在，如果不存在就新建一个Node
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
// 确定元素在tabl数组上的位置
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
// 如果原来位置上有值并且key相同，那么直接替换原来的value
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
// 元素总数加一
int c = count + 1;
// 判断是否需要扩容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}
大致过程是：
index，获取到头结点node添加到数组index索引位这里需要注意的是scanAndLockForPut方法，他在没有获取到锁的时候不仅会通过自旋获取锁，还会做一些其他的查找或新增节点的工，以此来提升put性能。
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
//定位HashEntry数组位置，获取第一个节点
HashEntry<K,V> first = entryForHash(this, hash);
HashEntry<K,V> e = first;
HashEntry<K,V> node = null;
//扫描次数，循环标记位
int retries = -1; // negative while locating node
while (!tryLock()) {
HashEntry<K,V> f; // to recheck first below
// 表示遍历链表还没有结束
if (retries < 0) {
if (e == null) {
if (node == null) // speculatively create node
// 完成新节点初始化
node = new HashEntry<K,V>(hash, key, value, null);
// 完成链表的遍历，还是没有找到相同key的节点
retries = 0;
}
// 有hash冲突，开始查找是否有相同的key
else if (key.equals(e.key))
retries = 0;
else
e = e.next;
}
// 断循环次数是否大于最大扫描次数
else if (++retries > MAX_SCAN_RETRIES) {
// 自旋获取锁
lock();
break;
}
// 每间隔一次循环，检查一次first节点是否改变
else if ((retries & 1) == 0 &&
(f = entryForHash(this, hash)) != first) {
// 首节点有变动，更新first，重新扫描
e = first = f; // re-traverse if entry changed
retries = -1;
}
}
return node;
}
scanAndLockForPut方法在当前线程获取不到segment锁的情况下，完成查找或新建节点的工作。当获取到锁后直接将该节点加入链表即可，提升了put操作的性能。大致过程：
private void rehash(HashEntry<K,V> node) {
// 复制老数组
HashEntry<K,V>[] oldTable = table;
int oldCapacity = oldTable.length;
// table数组扩容2倍
int newCapacity = oldCapacity << 1;
// 扩容阈值也增加两倍
threshold = (int)(newCapacity * loadFactor);
// 创建新数组
HashEntry<K,V>[] newTable =
(HashEntry<K,V>[]) new HashEntry[newCapacity];
// 计算新的掩码
int sizeMask = newCapacity - 1;
for (int i = 0; i < oldCapacity ; i++) {
HashEntry<K,V> e = oldTable[i];
if (e != null) {
HashEntry<K,V> next = e.next;
// 计算新的索引位
int idx = e.hash & sizeMask;
// 转移数据
if (next == null) // Single node on list
newTable[idx] = e;
else { // Reuse consecutive sequence at same slot
HashEntry<K,V> lastRun = e;
int lastIdx = idx;
for (HashEntry<K,V> last = next;
last != null;
last = last.next) {
int k = last.hash & sizeMask;
if (k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}
newTable[lastIdx] = lastRun;
// Clone remaining nodes
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
V v = p.value;
int h = p.hash;
int k = h & sizeMask;
HashEntry<K,V> n = newTable[k];
newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
}
}
}
}
// 将新的节点加到对应索引位
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}
在这里我们可以发现每次扩容是针对一个单独的Segment的，在扩容完成之前中不会对扩容前的数组进行修改，这样就可以保证get()不被扩容影响。大致过程是：
e.hash & sizeMask;计算key新的索引位tablepublic V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
int h = hash(key);
// 计算出Segment的索引位
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
// 以原子的方式获取Segment
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
// 原子方式获取HashEntry
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
// key相同
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
// value是volatile所以可以不加锁直接取值返回
return e.value;
}
}
return null;
}
我们可以看到get方法是没有加锁的，因为HashEntry的value和next属性是volatile的，volatile直接保证了可见性，所以读的时候可以不加锁。Java中Unsafe类可以参考这篇博客。
public int size() {
// Try a few times to get accurate count. On failure due to
// continuous async changes in table, resort to locking.
final Segment<K,V>[] segments = this.segments;
int size;
// true表示size溢出32位（大于Integer.MAX_VALUE）
boolean overflow; // true if size overflows 32 bits
long sum; // sum of modCounts
long last = 0L; // previous sum
int retries = -1; // first iteration isn't retry
try {
for (;;) {
// retries 如果retries等于2则对所有Segment加锁
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0;
overflow = false;
// 统计每个Segment元素个数
for (int j = 0; j < segments.length; ++j) {
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null) {
sum += seg.modCount;
int c = seg.count;
if (c < 0 || (size += c) < 0)
overflow = true;
}
}
if (sum == last)
break;
last = sum;
}
} finally {
// 解锁
if (retries > RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
// 如果size大于Integer.MAX_VALUE值则直接返货Integer.MAX_VALUE
return overflow ? Integer.MAX_VALUE : size;
}
size的核心思想是先进性两次不加锁统计，如果两次的值一样则直接返回，否则第三个统计的时候会将所有segment全部锁定，再进行size统计，所以size()尽量少用。因为这是在并发情况下，size其他线程也会改变size大小，所以size()的返回值只能表示当前线程、当时的一个状态，可以算其实是一个预估值。
public boolean isEmpty() {
long sum = 0L;
final Segment<K,V>[] segments = this.segments;
for (int j = 0; j < segments.length; ++j) {
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null) {
// 只要有一个Segment的元素个数不为0则表示不为null
if (seg.count != 0)
return false;
// 统计操作总数
sum += seg.modCount;
}
}
if (sum != 0L) { // recheck unless no modifications
for (int j = 0; j < segments.length; ++j) {
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null) {
if (seg.count != 0)
return false;
sum -= seg.modCount;
}
}
// 说明在统计过程中ConcurrentHashMap又被操作过，
// 因为上面判断了ConcurrentHashMap不可能会有元素，所以这里如果有操作一定是新增节点
if (sum != 0L)
return false;
}
return true;
}
和size方法一样这个方法也是一个若一致方法，最后的结果也是一个预估值。
这个结构和HashMap一样
//最大容量
private static final int MAXIMUM_CAPACITY = 1 << 30;
//初始容量
private static final int DEFAULT_CAPACITY = 16;
//数组最大容量
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//默认并发度，兼容1.7及之前版本
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
//加载/扩容因子，实际使用n - (n >>> 2)
private static final float LOAD_FACTOR = 0.75f;
//链表转红黑树的节点数阀值
static final int TREEIFY_THRESHOLD = 8;
//红黑树转链表的节点数阀值
static final int UNTREEIFY_THRESHOLD = 6;
//当数组长度还未超过64,优先数组的扩容,否则将链表转为红黑树
static final int MIN_TREEIFY_CAPACITY = 64;
//扩容时任务的最小转移节点数
private static final int MIN_TRANSFER_STRIDE = 16;
//sizeCtl中记录stamp的位数
private static int RESIZE_STAMP_BITS = 16;
//帮助扩容的最大线程数
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
//size在sizeCtl中的偏移量
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
// ForwardingNode标记节点的hash值（表示正在扩容）
static final int MOVED = -1; // hash for forwarding nodes
// TreeBin节点的hash值，它是对应桶的根节点
static final int TREEBIN = -2; // hash for roots of trees
static final int RESERVED = -3; // hash for transient reservations
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
//存放Node元素的数组,在第一次插入数据时初始化
transient volatile Node<K,V>[] table;
//一个过渡的table表,只有在扩容的时候才会使用
private transient volatile Node<K,V>[] nextTable;
//基础计数器值(size = baseCount + CounterCell[i].value)
private transient volatile long baseCount;
/**
* 控制table数组的初始化和扩容，不同的值有不同的含义：
* -1:表示正在初始化
* -n:表示正在扩容
* 0:表示还未初始化，默认值
* 大于0：表示下一次扩容的阈值
*/
private transient volatile int sizeCtl;
//节点转移时下一个需要转移的table索引
private transient volatile int transferIndex;
//元素变化时用于控制自旋
private transient volatile int cellsBusy;
// 保存table中的每个节点的元素个数 长度是2的幂次方，初始化是2，每次扩容为原来的2倍
// size = baseCount + CounterCell[i].value
private transient volatile CounterCell[] counterCells;
其他的参考HashMap 源码解析
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
Node(int hash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
...
链表节点，保存着key和value的值。
static final class TreeNode<K,V> extends Node<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next,
TreeNode<K,V> parent) {
super(hash, key, val, next);
this.parent = parent;
}
...
红黑树节点，包含了树的信息。
TreeBins中使用的节点
static final class TreeBin<K,V> extends Node<K,V> {
TreeNode<K,V> root;
volatile TreeNode<K,V> first;
// 锁的持有者
volatile Thread waiter;
// 锁状态
volatile int lockState;
// values for lockState
// 表示持有写锁
static final int WRITER = 1; // set while holding write lock
// 表示等待
static final int WAITER = 2; // set when waiting for write lock
// 表示读锁的增量值
static final int READER = 4; // increment value for setting read lock
...
与HashMap有点区别的是，他不直接使用TreeNode作为数的根节点，而是使用TreeBins对其做了装饰后成为了根节点；同时它还记录了锁的状态；需要注意的是：
putTreeVal()方法里面我们使用cas在加了一次锁。/**
* A node inserted at head of bins during transfer operations.
*/
static final class ForwardingNode<K,V> extends Node<K,V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null, null, null);
this.nextTable = tab;
}
Node<K,V> find(int h, Object k) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
outer: for (Node<K,V>[] tab = nextTable;;) {
Node<K,V> e; int n;
// 1. 判断新的数组是否是null，
// 2. 如果不为NULL给那就找到对应索引位上的头结点
// 3. 判断头节点是否为NULL
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
return null;
// 自旋找节点
for (;;) {
int eh; K ek;
if ((eh = e.hash) == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
if (eh < 0) {
// 如果又变成了ForwardingNode标记节点，那说明有发生了扩容，需要跳出循环从新查找
if (e instanceof ForwardingNode) {
tab = ((ForwardingNode<K,V>)e).nextTable;
continue outer;
}
else
return e.find(h, k);
}
if ((e = e.next) == null)
return null;
}
}
}
}
ForwardingNode 节点是一个扩容标记节点，只要在数组上发现对应索引位上是ForwardingNode 节点时，表示正在扩容。当get方法调用时，如果遇到ForwardingNode 节点，那么它将会到扩容后的数据上查找数据，否则还是在扩容前的数组上查找数据。这个要注意两点：
public ConcurrentHashMap18() {
}
与HashMap一样，构造函数啥都没干，初始化操作是在第一次put完成的。
public V put(K key, V value) {
return putVal(key, value, false);
}
啥都么有
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
计算key.hashCode（）并将更高位的散列扩展（XOR）降低。采用位运算主要是是加快计算速度。
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
// 计算hash值
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 判断是否需要初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 找出key对应的索引位上的第一个节点
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 如果该索引位为null，则直接将数据放到该索引位
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 正在扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// 加内置锁锁定一个数组的索引位，并添加节点
synchronized (f) {
if (tabAt(tab, i) == f) {
// 表示链表节点
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
// key相同直接替换value值
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
// 将新节点添加到链表尾部
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 表示树节点
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
// 添加数节点
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
// 尝试将链表转换成红黑树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
主要流程：
initTable()方法完成初始化fh >= 0根据头结点hash值判断是否是链表节点，如果是新增链表节点，否则新增树节点putTreeVal()需要注意，红黑树的根节点有可能会因为旋转而发生变化，所以我们在添加节点的时候还需要对根节点使用cas在加了一次锁。addCount(1L, binCount);新增count数，并判断是否需要扩容或者帮助扩容private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
// 正在初始化
if ((sc = sizeCtl) < 0)
// 让出CPU执行权，然后自旋
Thread.yield(); // lost initialization race; just spin
// CAS替换标志位（相当于获取锁）
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// 二次判断
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
// 相当于sc=n*3/4
sc = n - (n >>> 2);
}
} finally {
// 扩容阈值
sizeCtl = sc;
}
break;
}
}
return tab;
}
主要过程：
Thread.yield();final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
// ForwardingNode标记节点，表示正在扩容
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
int rs = resizeStamp(tab.length);
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
判断是否正在扩容，如果是就帮助扩容。
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {\
// n原来数组长度
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
// 判断是发起扩容的线程还是帮助扩容的线程，如果是发起扩容的需要初始化新数组
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
int nextn = nextTab.length;
// 扩容期间的数据节点（用于标志位，hash值是-1）
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// 当advance == true时，表明该节点已经处理过了
boolean advance = true;
// 在扩容完成之前保证get不被影响
boolean finishing = false; // to ensure sweep before committing nextTab
// 1. 从右往左找到第一个有数据的索引位节点（有hash冲突的桶）
// 2. 如果找到的节点是NULL节点（没有hash冲突的节点），那么将该索引位的NULL替换成ForwardingNode标记节点，这个节点的hash是-1
// 3. 如果找到不为NULL的节点（有hash冲突的桶），则对这个节点进行加锁
// 4. 开始进进移动节点数据
for (int i = 0, bound = 0;;) {
//f:当前处理i位置的node（头结点或者根节点）;
Node<K,V> f; int fh;
// 通过while循环获取本次需要移动的节点索引i
while (advance) {
// nextIndex:下一个要处理的节点索引; nextBound:下一个需要处理的节点的索引边界
int nextIndex, nextBound;
// i是老数组索引位，通过--i来讲索引位往前一个索引位移动，直到0索引位
if (--i >= bound || finishing)
advance = false;
// 节点已全部转移
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
// transferIndex（初值为最后一个节点的索引），表示从transferIndex开始后面所有的节点都已分配，
// 每次线程领取扩容任务后，需要更新transferIndex的值(transferIndex-stride)。
// CAS修改transferIndex，并更新索引边界
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
// 老数组最后一个索引位置
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
// 已经完成所有节点复制了
if (finishing) {
nextTable = null;
table = nextTab;
// sizeCtl阈值为原来的1.5倍
sizeCtl = (n << 1) - (n >>> 1);
// 结束自旋
return;
}
// CAS 更新扩容阈值，在这里面sizectl值减一，说明新加入一个线程参与到扩容操作
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // recheck before commit
}
}
// 将以前老数组上为NULL的节点（还没有元素的桶或者说成没有hash冲突的数据节点），用ForwardingNode标记节点补齐
// 主要作用是：其他线程在put元素，发现找到的索引位是fwd节点则表示正在扩容，那么该线程会来帮助扩通，而不是在那里等待
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// 表示处理过该节点了
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
// 对应索引位加锁
synchronized (f) {
// 再次校验一下老数组对应索引位节点是否是我们找到的节点f
if (tabAt(tab, i) == f) {
// 低索引位头节点(i位)， 高位索引位头节点（i+tab.length）
Node<K,V> ln, hn;
// fh >=0 表示链表节点，TreeBin节点的hash值-2
if (fh >= 0) {
// fh & n算法可以算出新的节点该分配到那个索引位（runBit要么为0放低位ln，要么为n放高位hn），
// runBit表示链表中最后一个元素的hash值&n的值
int runBit = fh & n;
// lastRun表示链表中最后一个元素
Node<K,V> lastRun = f;
// 找到链表中最后一个节点，并赋值给lastRun
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
// 判断原来的最后一个节点应该添加到高位还是低位
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
// f表示头结点，如果p不是尾节点，则转移节点
// 如果以前节点顺序是 1 2 3 4 转移后就是 3 2 1 4
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
// 转移节点时都是新建节点,以免破坏原来数组结构影响get方法
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
// 设置新数组低索引位头节点(i位)
setTabAt(nextTab, i, ln);
// 设置新数组高位索引位头节点（i+tab.length）
setTabAt(nextTab, i + n, hn);
// 设置老数组i位为标记节点，表示已经处理过了
setTabAt(tab, i, fwd);
advance = true;
}
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
// 设置新数组低索引位头节点(i位)
setTabAt(nextTab, i, ln);
// 设置新数组高位索引位头节点（i+tab.length）
setTabAt(nextTab, i + n, hn);
// 设置老数组i位为标记节点，表示已经处理过了
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
主要过程：
tab为扩容前的数组nextTablefwd = new ForwardingNode<K,V>(nextTab)初始化扩容标记节点tab上从右往左（从高索引位到低索引位）遍历所有头结点，索引位为itab[i]=fwd。synchronized (f)tab[i]=fwd），表示已经处理过了注意：
- 第5点有
tab[i]=fwd有两层含义：1,表示对应索引位已经处理过了；2,当其他线程拿到该头结点的时候能知晓正在扩容，这时在put的时候帮助扩容，在get的时候去扩容后的数组上找相应的keyint runBit = fh & n;算法可以算出新的节点该分配到那个索引位（runBit要么为0放低位ln，要么为n放高位hn）- 如果是链表节点，以前节点顺序是 1 2 3 4 扩容后会变成 3 2 1 4
扩容的大致过程图解：
发起扩容，扩容前数组tab
在扩容前的数组tab上从右往左（从高索引位到低索引位）遍历所有头结点，索引位为i，如果找到的头结点是NULL则直接赋值成````fwd``` 标记节点。
扩容前的数组上找到不为NULL的节点，则还是移动节点到扩容后的额数组
private final void addCount(long x, int check) {
// CounterCell[] as;使用计数器数组因该是为了提升并发量，减小冲突概率
CounterCell[] as; long b, s;
// 计数器表不为NULL（counterCells当修改baseCount有冲突时，需要将size增量放到这个计数器数组里面）
if ((as = counterCells) != null ||
// 使用CAS更新baseCount的值（+1）如果失败说明存在竞争
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
// CounterCell是否存在竞争的标记位
boolean uncontended = true;
// CounterCell[] as为NULL表示as没有竞争
if (as == null || (m = as.length - 1) < 0 ||
// 随机一个数组位置来验证是否为NULL，如果a是null表示没有竞争，随机也是为了减小冲突概率
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
// CAS替换a的value，如果失败表示存在竞争
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
// 将size增量值存到as上
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
// 统计size
s = sumCount();
}
// 检查是否需要扩容
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
// size大于阈值sizeCtl，tab数组长度小于最大值1<<30
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
// 表示正在扩容
if (sc < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
// 帮助扩容
transfer(tab, nt);
}
// sc = (rs << RESIZE_STAMP_SHIFT) + 2，移位后是负数
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
// 发起扩容，此时nextTable=null
transfer(tab, null);
s = sumCount();
}
}
}
在put()方法执行最后会对当前Map的size+1，ConcurrentHashMap中size由baseCount和CounterCell[] as组成，size=baseCount+as[i].value。addCount的大致过程如下：
size++）存在竞争CounterCell[] as数组as[ThreadLocalRandom.getProbe() & m]随机取一个索引位，使用CAS完成size++as[i]也存在竞争会调用fullAddCount(x, uncontended);方法完成size++size++完成后通过size=baseCount+as[i].value公式计算出元素总数注意：
- CounterCell[] as：这个的只要目的是分散对
baseCount的单一竞争，提示size++的并发率，这里和table数组一样使用了锁分离技术，as的长度也是2的n次方，初始长度是2- 在第三步中使用随机数也是为了提升并发效率，
ThreadLocalRandom类是JDK7在JUC包下新增的随机数生成器，它解决了Random类在多线程下，多个线程竞争内部唯一的原子性种子变量，而导致大量线程自旋重试的不足fullAddCount(x, uncontended);方法里面完成了as的初始化和扩容- 元素总数的计算公式是
size=baseCount+as[i].value
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
元素总数的计算公式是size=baseCount+as[i].value
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
// table 不为NULL并且对饮索引位不为NULL
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
// 头节点key相同
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// 树节点或者ForwardingNode标记节点
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
// 链表节点
while ((e = e.next) != null) {
// key相同
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
主要流程：
注意：
- get 方法没有加锁，原因是节点的value是volatile的，已经保证了可见性，只要value有更新，那么我们一定能读到最新数据。
e.find(h, key)这里：如果对应索引位头结点是ForwardingNode节点，那么会直接去扩通后的数组找对应的key，可以参见上面ForwardingNode.find()方法
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
get方法和containsKey方法都是遍历对应索引位上所有节点，来判断是否存在key相同的节点以及获得该节点的value。但由于遍历过程中其他线程可能对链表结构做了调整，因此get和containsKey返回的可能是过时的数据，这一点是ConcurrentHashMap在弱一致性上的体现。
get()时如果判断到当前索引位正在扩容，那么直接在扩容后的数组中去找对应的keypackage com.xiaolyuh;
import java.util.Map;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
/**
* @author yuhao.wang3
* @since 2019/7/26 17:58
*/
public class HashMapTest {
public static void main(String[] args) {
AtomicInteger integer = new AtomicInteger();
ExecutorService cachedThreadPool = Executors.newFixedThreadPool(50);
Map<User, Integer> map = new ConcurrentHashMap<>();
for (int i = 0; i < 10000; i++) {
cachedThreadPool.execute(() -> {
User user = new User(1);
map.put(user, 1);
});
}
}
static class User {
int age;
public User(int age) {
this.age = age;
}
@Override
public int hashCode() {
return age;
}
@Override
public String toString() {
return "" + age;
}
}
}
为监控而生的多级缓存框架 layering-cache这是我开源的一个多级缓存框架的实现，如果有兴趣可以看一下
本文发表于2019年07月29日 17:00
(c)注：本文转载自https://my.oschina.net/u/3748347/blog/3080609，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如有侵权行为，请联系我们，我们会及时删除.
阅读 1692 讨论 0 喜欢 0
Spring Cloud Edgware新特性之二：如何配置Zuul的Hystrix线程池
分布式环境中使用基于共享存储的LVM块设备时的元数据同步方案对比
避坑！MotionGo就是一款诈骗软件！千万不要用ChatPPT，浪费时间！
宝塔面板使用WWW用户执行计划任务命令 解决laravel日志权限问题 宝塔设置计划任务执行用户
手机微信一键制作透明底文字表情 教你如何让微信表情包背景为透明 自制微信表情包动图 文字表情在线制作
ssh目录权限配置指南 .ssh文件夹及rsa_id.pub等文件正确权限规则
Mac连接亚马逊AWS EC2 远程连接登录不上去 有pem私钥文件依然要输密码 默认密码 教程
PHP工程师必知必会 - Linux系统常用命令 - Linux中的网络管理命令（下）
| 抢先体验 |
|---|
扫码体验 |
| 闪念胶囊 |
|---|
|
你要过得好哇，这样我才能恨你啊，你要是过得不好，我都不知道该恨你还是拥抱你啊。 17:21 2021年04月19日 查看详情 |
|
直抵黄龙府，与诸君痛饮尔。 18:17 2021年03月28日 查看详情 |
|
那时陪伴我的人啊，你们如今在何方。 16:28 2021年03月19日 查看详情 |
|
不出意外的话，我们再也不会见了，祝你前程似锦。 18:05 2021年03月17日 查看详情 |
|
这世界真好，吃野东西也要留出这条命来看看 21:21 2021年03月14日 查看详情 |
| Contact |
|---|
Y2lvbkBjaGluYWNpb24uY24= |