概览
最近在看redis源码，发现redis采用了几种不同的算法来计算Hash Code;因此打算借此整理下JDK中的实现，加深理解;
Redis
Thomas Wang's 32 bit Mix Function
关于该算法的具体内容，可以参考这篇文章,算法源码如下：
public int hash32shift(int key)
{
key = ~key + (key << 15); // key = (key << 15) - key - 1;
key = key ^ (key >>> 12);
key = key + (key << 2);
key = key ^ (key >>> 4);
key = key * 2057; // key = (key + (key << 3)) + (key << 11);
key = key ^ (key >>> 16);
return key;
}
可以看到它是计算int类型的hash code,返回结果也是int类型;另外它还提供了64bit的算法，有兴趣的可以自行查阅:
根据Thomas Wang所描述，由于上述代码可以利用CPU的native指令，在HP 9000 workstations机器上只需要11个时钟周期，速度很快；
比较费解这边的常量值是怎么确定的，无奈算法基础比较差，如果有了解的同学，欢迎答疑；
Austin Appleby's MurmurHash2
MurmurHash是一种非加密型哈希函数，由Austin Appleby在2008年发明，并且有多个变种;该算法的作者2011去了google,开发出来了新的算法CityHash；
unsigned int dictGenHashFunction(const void *key, int len) {
/* 'm' and 'r' are mixing constants generated offline.
They're not really 'magic', they just happen to work well. */
uint32_t seed = dict_hash_function_seed;
const uint32_t m = 0x5bd1e995;
const int r = 24;
/* Initialize the hash to a 'random' value */
uint32_t h = seed ^ len;
/* Mix 4 bytes at a time into the hash */
const unsigned char *data = (const unsigned char *)key;
while(len >= 4) {
uint32_t k = *(uint32_t*)data;
k *= m;
k ^= k >> r;
k *= m;
h *= m;
h ^= k;
data += 4;
len -= 4;
}
/* Handle the last few bytes of the input array */
switch(len) {
case 3: h ^= data[2] << 16;
case 2: h ^= data[1] << 8;
case 1: h ^= data[0]; h *= m;
};
/* Do a few final mixes of the hash to ensure the last few
* bytes are well-incorporated. */
h ^= h >> 13;
h *= m;
h ^= h >> 15;
return (unsigned int)h;
}
Murmur可以计算字符串的hash code,基本思想就是把key分成n组，每组4个字符，把这4个字符看成是一个uint_32，进行n次运算，得到一个h，然会在对h进行处理，得到一个相对离散的hash code;
DJB Hash
unsigned int DJBHash(char *str)
{
unsigned int hash = 5381;
while (*str){
hash = ((hash << 5) + hash) + (*str++); /* times 33 */
}
hash &= ~(1 << 31); /* strip the highest bit */
return hash;
}
Redis对其进行了部分调整，不区分大小写：
unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
unsigned int hash = (unsigned int)dict_hash_function_seed;
while (len--)
hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
return hash;
}
JDK
Austin Appleby's MurmurHash3
从JDK7开始，JDK引入了一种新的计算Hash code的算法，可以在如下的集合对象中使用:
- HashMap
- Hashtable
- HashSet
- LinkedHashMap
- LinkedHashSet
- WeakHashMap
- ConcurrentHashMap
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
可以看到只有key为字符类型，而且hashSeed不为0时才采用新的哈希算法；
sun.misc.Hashing.stringHash32实际上调用的是String.hash32方法:
int hash32() {
int h = hash32;
//h==0表示未计算过hash code
//可以看到hash code只会计算一次
if (0 == h) {
//HASHING_SEED是根据时间戳等计算出来的随机数
h = sun.misc.Hashing.murmur3_32(HASHING_SEED, value, 0, value.length);
//确保结果非0，避免重新计算
h = (0 != h) ? h : 1;
hash32 = h;
}
return h;
}
可以看到最终调用的是MurmurHash3算法，那么什么情况下hashSeed不为0呢？
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
可以看到是否采用新算法和Holder.ALTERNATIVE_HASHING_THRESHOLD有关；实际上JDK定义了一个新的属性jdk.map.althashing.threshold（默认值－1），只有当系统容量大于该属性值时，才会采用新的算法；因此可以将通过-Djdk.map.althashing.threshold＝0设置该属性为0，启用新的哈希函数；
String.hashCode
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
Object.hashCode
之前曾经在Java对象结构 中介绍了Java的MarkWord,其中记录了对象的hashCode;如果对象计算过hashCode，则会存储到对象头中；如果是第一次计算则是调用
static inline intptr_t get_next_hash(Thread * Self, oop obj) {
intptr_t value = 0 ;
if (hashCode == 0) {
// This form uses an unguarded global Park-Miller RNG,
// so it's possible for two threads to race and generate the same RNG.
// On MP system we'll have lots of RW access to a global, so the
// mechanism induces lots of coherency traffic.
value = os::random() ;
} else
if (hashCode == 1) {
// This variation has the property of being stable (idempotent)
// between STW operations. This can be useful in some of the 1-0
// synchronization schemes.
intptr_t addrBits = intptr_t(obj) >> 3 ;
value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;
} else
if (hashCode == 2) {
value = 1 ; // for sensitivity testing
} else
if (hashCode == 3) {
value = ++GVars.hcSequence ;
} else
if (hashCode == 4) {
value = intptr_t(obj) ;
} else {
// Marsaglia's xor-shift scheme with thread-specific state
// This is probably the best overall implementation -- we'll
// likely make this the default in future releases.
unsigned t = Self->_hashStateX ;
t ^= (t << 11) ;
Self->_hashStateX = Self->_hashStateY ;
Self->_hashStateY = Self->_hashStateZ ;
Self->_hashStateZ = Self->_hashStateW ;
unsigned v = Self->_hashStateW ;
v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;
Self->_hashStateW = v ;
value = v ;
}
value &= markOopDesc::hash_mask;
if (value == 0) value = 0xBAD ;
assert (value != markOopDesc::no_hash, "invariant") ;
TEVENT (hashCode: GENERATE) ;
return value;
}
可以看到，这边提供了多种不同的实现，具体采用哪种，取决于hashCode的值，在Linux机器上,hashCode默认为0:
hashCode.png
因此是通过os::random计算hashCode,可以参考Java对象结构 ；
其它
Character、Integer、Long、Double的hashCode方法返回包装的基本类型;
网友评论