hashmap的hash算法( 转)

王朝学院·作者佚名  2016-05-28
窄屏简体版  字體: 小  |  中  |  大  |  超大  

hashmap的hash算法( 转) 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=87=7^86=6^7^85=5^8^7^64=4^7^6^5^83=3^8^6^5^8^4^72=2^7^5^4^7^3^8^61=1^6^4^3^8^6^2^7^5结果中的1、2、3三位出现重复位^运算3=3^8^6^5^8^4^7 -> 3^6^5^4^72=2^7^5^4^7^3^8^6 -> 2^5^4^3^8^61=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。

 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
© 2005- 王朝網路 版權所有 導航