* that otherwise encounter collisions for hashCodes that do not
* differ in lower or upper bits.
*/
private static int hash(int h) {
// 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);
}
又复杂了，没错！ 目的只有一个使结果在目标空间均匀。相关文章请参考这里
除了hash算法的改进，还有就是在并发HashMap中使用了锁，而且这把锁是分离的锁。目的就是绕过访问必须加锁的技术障碍，当然又要保护数据的安全。这样比HashTable中方法级别的synchronized更加细粒度的Segment诞生了。该类自身就是继承自ReentrantLock可重入锁对象，目的是方便加锁操作。
Java代码
/**
* Segments are specialized versions of hash tables. This
* subclasses from ReentrantLock opportunistically, just to
* simplify some locking and avoid separate construction.
*/
static final class Segment
并发HashMap中默认使用16个Segment对HashMap的数据进行分段，读取方法如下：
Java代码
public V get(Object key) {
int hash = hash(key.hashCode());
return segmentFor(hash).get(key, hash);
}
读取方法使用了二次hash操作，第一次时命中一个Segment，第二次调用Segment的get方法：
Java代码
/* Specialized implementations of map methods */
V get(Object key, int hash) {
if (count != 0) { // read-volatile 1.这里是确保可见性
HashEntry
while (e != null) {
if (e.hash == hash && key.equals(e.key)) {
V v = e.value;
if (v != null)// 2.这里的数据为空说明有并发的修改。
return v;
return readValueUnderLock(e); // recheck
}
e = e.next;
}
}
return null;
}
只有当数据被并发修改的时候才加锁读，否则都是直接返回数据。这样提高了并发性能。get方法还用到了JDK 1.5对volatile字段的语义增强(JSR 166)，确保happens-before原则。相关文章这里。
Segment中的table存放的是HashEntry数组，那么它的结构又是怎样的呢？
Java代码
static final class HashEntry
final K key;
final int hash;
volatile V value;
final HashEntry
HashEntry(K key, int hash, HashEntry
this.key = key;
this.hash = hash;
this.next = next;
this.value = value;
}
@SuppressWarnings("unchecked")
static final
return new HashEntry[i];
}
}
我们从代码可以看出除了value字段是可以修改的，其它都是final 字段，这样造成的结果是删除一个元素的时候我们无法修改HashEntry的next引用。这样我们删除操作时只能其它部分逐个复制了。相关代码如下：
Java代码
/**
* Remove; match on key only if value null, else match both.
*/
V remove(Object key, int hash, Object value) {
lock();//1.删除操作是加锁的，当然这个锁得粒度仅仅在Segment范围之内。
try {
int c = count - 1;
HashEntry
int index = hash & (tab.length - 1);
HashEntry
HashEntry
while (e != null && (e.hash != hash || !key.equals(e.key)))
e = e.next;
V oldValue = null;
if (e != null) {
V v = e.value;
if (value == null || value.equals(v)) {