hashmap的hash算法( 转)

浏览数：24 / 时间：2015年06月08日

HashMap 中hash table 定位算法：

int hash = hash(key.hashCode());  
int i = indexFor(hash, table.length);

其中indexFor和hash源码如下：

/** 
 * Applies a supplemental hash function to a given hashCode, which 
 * defends against poor quality hash functions.  This is critical 
 * because HashMap uses power-of-two length hash tables, that 
 * otherwise encounter collisions for hashCodes that do not differ 
 * in lower bits. Note: Null keys always map to hash 0, thus index 0. 
 */  
static int hash(int h) {  
    // 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);  
}  
  
/** 
 * Returns index for hash code h. 
 */  
static int indexFor(int h, int length) {  
    return h & (length-1);  
}

现在分析一下hash算法：

h ^= (h >>> 20) ^ (h >>> 12);  
return h ^ (h >>> 7) ^ (h >>> 4);

假设key.hashCode()的值为：0x7FFFFFFF，table.length为默认值16。

上面算法执行如下：

得到i=15

其中h^(h>>>7)^(h>>>4) 结果中的位运行标识是把h>>>7 换成 h>>>8来看。

即最后h^(h>>>8)^(h>>>4) 运算后hashCode值每位数值如下：

8=8

7=7^8

6=6^7^8

5=5^8^7^6

4=4^7^6^5^8

3=3^8^6^5^8^4^7

2=2^7^5^4^7^3^8^6

1=1^6^4^3^8^6^2^7^5

结果中的1、2、3三位出现重复位^运算

3=3^8^6^5^8^4^7 -> 3^6^5^4^7

2=2^7^5^4^7^3^8^6 -> 2^5^4^3^8^6

1=1^6^4^3^8^6^2^7^5 -> 1^4^3^8^2^7^5

算法中是采用(h>>>7)而不是(h>>>8)的算法，应该是考虑1、2、3三位出现重复位^运算的情况。使得最低位上原hashCode的8位都参与了^运算，所以在table.length为默认值16的情况下面，hashCode任意位的变化基本都能反应到最终hash table 定位算法中，这种情况下只有原hashCode第3位高1位变化不会反应到结果中，即：0x7FFFF7FF的i=15。

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

hashmap的hash算法( 转)