Key不能为null
数据结构
ConcurrentHashMap的底层数据结构是由Segment数组组成，而Segment的元素存储的是HashEntry的数组，HashEntry和HashMap的Entry的结构十分相似，都是包含hash，K,V,next四个属性
static final class HashEntry<K,V> {
final int hash;
final K key;
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;
}
ConcurrentHashMap底层结构.png
Segment数组长度代表并发度，Segment数组元素存储的是HashEntry数组。
put元素逻辑分析
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
// j 用来定位元素应该放进那一个segment
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
通过(hash >>> segmentShift) & segmentMask计算元素应该防止那一个segment。
s = ensureSegment(j);这行代码其实是确保定位到的segment[j]已经初始化。
private Segment<K,V> ensureSegment(int k) {
final Segment<K,V>[] ss = this.segments;
long u = (k << SSHIFT) + SBASE; // raw offset
Segment<K,V> seg;
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
Segment<K,V> proto = ss[0]; // use segment 0 as prototype
int cap = proto.table.length;
float lf = proto.loadFactor;
int threshold = (int)(cap * lf);
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) { // recheck
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) {
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}
}
}
return seg;
}
每个segment的初始化其实是以ss[0]为prototype原型的，ss[0]是在new ConCurrentHashMap的时候已经初始化了，这样做的目的是防止每个segment的初始化的时候都重新计算里面的table.length,loadFactor,threshold这些信息。
put的时候扩容
Segment数组不会扩容，segment初始化之后就不再变化了。只是对Segment数组里的table进行
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
//加锁
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
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;
}
Segment继承了ReentrantLock锁，在put的时候，是某个segment[i]进行加锁，从而保证线程的安全。上面的rehash扩容代码也是在加锁的代码里，所以不存在线程并发扩容的问题。
