1.7版本
基本策略是在segments的基础上再细分table，每一个都是一个并发可读的hashtable。
为了节省空间，
table的默认大小=16
static final int DEFAULT_INITIAL_CAPACITY = 16;
默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认并发等级
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
最大容量=2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
每个Segment的最小table数=2，防止使用后立即被resizing
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
segment的最大数量216,，最多224?
static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
？？？？？？？？？？？？？
static final int RETRIES_BEFORE_LOCK = 2;
构造函数
initialCapacity,初始化map的容量，既map能装多少键值对。
loadFactor，负载因子，给Segment计算其包含的table在什么时候被rehash(扩容，重新分布)
concurrencyLevel
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
//Segments最大数，这里默认是2^16.concurrencyLevel不能大于此值
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// Find power-of-two sizes best matching arguments
//这里的意思是ssize是Segments最终的大小，它只能是2的幂。
//起初是2^0=1,通过和传入的concurrencyLevel比较，取一个不大于concurrencyLevel的2的幂作为Segments最后的容量。
//sshift相当于ssize转换成2进制之后，1后面0的个数。比如ssize==2^4,二进制就是10000，sshift就是4。
int sshift = 0;
int ssize = 1;
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
//int一共32位，segmentShift即时ssize左边数？
this.segmentShift = 32 - sshift;
//segmentMask是segments的容量-1，既最后一个位置的index。
this.segmentMask = ssize - 1;
//整个initialCapacity代表ConcurrentHashMap的初始化时的容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//除以ssize，既segments的大小，既得到每个segment中的table的容量c
int c = initialCapacity / ssize;
//因为可能有余数，所以table容量c * segments容量ssize必须大于initialCapacity。
if (c * ssize < initialCapacity)
++c;
//调整segments的table的容量必须是2的幂，并且不小于计算出来的c
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
cap <<= 1;
// create segments and segments[0]
//这里就是创建了，注意的事loadFactor负载因子是用来计算table的rehash的阈值的，
//比如table的cap=8，loadFactor=0.75,那么阈值threshold就是6，
//也就是table里面装了6个hashEntry后就会触发rehash。
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;
}
private static class Holder {
/**
* Enable alternative hashing of String keys?
*
* <p>Unlike the other hash map implementations we do not implement a
* threshold for regulating whether alternative hashing is used for
* String keys. Alternative hashing is either enabled for all instances
* or disabled for all instances.
*/
static final boolean ALTERNATIVE_HASHING;
static {
// Use the "threshold" system property even though our threshold
// behaviour is "ON" or "OFF".
String altThreshold = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction(
"jdk.map.althashing.threshold"));
int threshold;
try {
threshold = (null != altThreshold)
? Integer.parseInt(altThreshold)
: Integer.MAX_VALUE;
// disable alternative hashing if -1
if (threshold == -1) {
threshold = Integer.MAX_VALUE;
}
if (threshold < 0) {
throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
}
ALTERNATIVE_HASHING = threshold <= MAXIMUM_CAPACITY;
}
}
第二部分成员变量
Holder.ALTERNATIVE_HASHING
final int segmentMask;
final int segmentShift;
final Segment<K,V>[] segments
Segment
//最大重试次数，如果cpu核大于1，取64，否则取1.
static final int MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
//被volatile修饰的HashEntry的table。
transient volatile HashEntry<K,V>[] table;
//table中有多少格子被初始化放入了HashEntry的数量。
transient int count;
//“修改次数统计”，对Segment中的table的任何修改都会往上加一
transient int modCount;
//table何时进行rehash的门槛值，这个值是通过负载因子loadFactor和整个table的大小capacity相乘而得。
//比如默认的loadfactor是0.75f，如果table的大小是16，那么threshold既为12.
//意即当table数组中有超过12个位置都被初始化放入了HashEntry的时候，就会在put操作的时候触发rehash
transient int threshold;
//负载因子，作用如上解释。
final float loadFactor;
put方法被ConcurrentHashMap的put和putInAbsent方法使用，key和value很好理解，hash是我们传入的key的哈希值，onlyAbsent表示是否只能在key尚未存在于table中的时候放入。
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
//在多次尝试中去获得锁，node不一定是最新的啊？？？？
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
//通过key的hash值定位应该放在哪个table格子中。
int index = (tab.length - 1) & hash;
//得到这个位置的第一个HashEntry
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {//将首节点赋值给变量e，开始循环
//第一种情况，首节点不为null,判断当前e==key，或者传入的key和e的hash，equals2方法均相等，此时在onlyIfAbsent为false的情况下修改e节点的值，增加修改次数统计modCount+1，跳出循环。如果e和key不匹配，则E向链表后一节点移动，继续下一次循环。
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;
}
//第二种情况，e为null，已找遍了这个格子。说明key对应的节点从来没被创建过。
else {
//如果刚才已经在scanAndLockForPut方法中为key创建了对应的Node，将他放到头结点的前面成为新的头结点。如果刚才在scanAndLockForPut没创建成，创建HashEntry。
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
//segment中包含的HashEntry加一
int c = count + 1;
//如果segment包含的HashEntry数既count已经大于threshold，并且table的长度还没有超过最大table容量2^30，则rehash????。如果不需要rehash，直接将key对应的Node放入table的格子中，这时就真正将key-value放了ConcurrentHashMap了。segment的修改次数+1。
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
//将初始化好的第一个HashEntry放入table中
setEntryAt(tab, index, node);
++modCount;//Segment的修改次数+1
count = c;
oldValue = null;//原来没有初始化，oldValue自然是null
break;
}
}
} finally {
//最后释放Segment的锁
unlock();
}
//返回这个key对应的oldValue
return oldValue;
}
scanAndLockForPut方法
这个方法在干嘛呢？
就是不停的通过tryLock去尝试获得Segment的锁。如果第一次就顺利获得了锁，就直接返回，结果也是null。
否则进入while循环，
先去尝试找key是否已经在链表中，如果在，返回的结果node就是null，如果没创建这个key的HashEntry，则返回的node就是新创建的HashEntry。
之后不停的去尝试获取锁，每隔2次尝试锁后，再次检查该table格子的头结点是否变化了，如果变化了。重复第一步遍历链表的动作。
所以这个方法做了2件事。
第一：在低于64次的重试中一定要拿到Segment的锁。
第二：如果key没有对应的已经创建过的HashEntry，创建并返回这个HashEntry，否则返回null.
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
//entryForHash是一通过key的hash值计算key应该在table的哪一个格子中。
//返回这个格子中的HashEntry的头结点，所以结果的变量名叫first.
HashEntry<K,V> first = entryForHash(this, hash);
HashEntry<K,V> e = first;
HashEntry<K,V> node = null;
//重试次数默认设置为-1
int retries = -1; // negative while locating node
//再次尝试去锁住Segment，如果成功了返回null？？？？？？如果失败了没锁成功，开始循环，一直到得到锁为止。
while (!tryLock()) {
HashEntry<K,V> f; // to recheck first below
if (retries < 0) {//第一次锁失败了，到达这儿，这时retries为-1，进入代码块。
if (e == null) {
//第一步：
//如果first节点为null，既table中的这个格子从来没被命中过，也就是没有初始化，让入第一个HashEntry.
//尝试去创建table这个格子中的第一个HashEntry，将重试次数设置为0.继续第二轮尝试。
if (node == null) // speculatively create node
node = new HashEntry<K,V>(hash, key, value, null);
retries = 0;
}
//如果first节点不为null，并且first节点就是我们传入的key的节点，将重试次数设置为0，继续第二轮尝试。
else if (key.equals(e.key))
retries = 0;
//如果任然没找到，将e指向后面一个HashEntry。
else
e = e.next;
}
else if (++retries > MAX_SCAN_RETRIES) {
//第二步：
//这里的逻辑是：既然到这儿了，那么表示又是一次重试了，所以++retries，重试次数+1。
//如果重试的次数还没超过64次。继续走到下面的分支。
//如果重试的次数大于了最大扫描重试次数64次，直接使用lock方法，阻塞等待其他线程释放这个Segment的锁，然后跳出循环。既尝试了64次后，我一定要得到这个锁才走。
lock();
break;
}
//第三步：
//如果重试的次数是偶数的时候，再次去那table这个格子里面的值，如果发现头结点已经不是我们刚才拿出来的那个节点了（因为我们锁失败了嘛，说明其他线程在占用此segment，这个线程有可能删除了我们刚才找到的头节点），那就更新数据后重来第一步。
else if ((retries & 1) == 0 &&
(f = entryForHash(this, hash)) != first) {
e = first = f; // re-traverse if entry changed
retries = -1;
}
}
return node;
}
Segment的remove方法是ConcurrentHashMap的2个remove方法的实际执行者。
final V remove(Object key, int hash, Object value) {
//和put方法一样首先尝试去获得锁，失败则调用scanAndLock方法。采用tryLock不停的去尝试获得锁，类似scanAndLockForPut，但是更简单??????
if (!tryLock())
scanAndLock(key, hash);
V oldValue = null;
try {
HashEntry<K,V>[] tab = table;
//通过hash值得到table中相应的格子index
int index = (tab.length - 1) & hash;
//得到table此index上的第一个HashEntry
HashEntry<K,V> e = entryAt(tab, index);
HashEntry<K,V> pred = null;
while (e != null) {//如果e不为null，进入循环，如果是null事就了了，表示找遍了都没有，说明没有对应的key呗。
K k;
//先拿到当前节点的下一节点的引用
HashEntry<K,V> next = e.next;
//如果e就是我们要找的节点，并且传入的value是null，或者value等于这个节点的value值，则删除这个节点
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
V v = e.value;
if (value == null || value == v || value.equals(v)) {
if (pred == null)
//pred==null说明这个被删除的节点是头结点，要把下一个节点放入table
setEntryAt(tab, index, next);
else
//否则只需直接将前一个节点的next改变即可.
pred.setNext(next);
++modCount;//修改次数+1
--count;//Segment中包含的HashEntry总数减一
oldValue = v;//返回被删除的key对应的旧value
}
//删除成功，跳出循环
break;
}
//e没匹配上,e往后移动一格
pred = e;
e = next;
}
} finally {
unlock();
}
return oldValue;
}
scanAndLock
Segment的2个replace方法就更简单了，不再赘述。
Segment的clear方法就是死等锁，然后遍历Segment的table，将每个格子置为null，修改对应的modCount和count，最后释放锁。
final void clear() {
lock();
try {
HashEntry<K,V>[] tab = table;
for (int i = 0; i < tab.length ; i++)
setEntryAt(tab, i, null);
++modCount;
count = 0;
} finally {
unlock();
}
}
Segment的hash方法
在put方法时，超过了threshold被触发。
网友评论