HashMap

HashMap的hash()方法巧妙之处

先看看JDK1.8中hash算法的实现，感觉真的很巧妙。

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    index = (n - 1) & hash(key) //n表示长度

如果是自己实现hash算法的话，最简单的话就是直接用hasCode对取余

index = key.hasCode() % n

在HashMap的实现中要求n的长度为2的n次幂
对于2的n次幂取余，可以用更加高效的方法

index = key.hasCode() & (n-1)

上面两种方法都存在一种缺陷，就是取余的计算结果对高位是无效的，只是对低位有效，当计算出来的hasCode()只有高位有变化时，取余的结果还是一样的。

例如

int hashCode1 = 01110101
int hasdCode2 = 01010101

int index1 = 01110101 & 1111 -> 0101
int index2 - 01010101 & 1111 -> 0101

//十进制翻译
int hashCode1 = 117
int hashCode2 = 85

int index1 = 117 % 16  -> 5
int index2 = 85 % 16  -> 5

从上面的例子可以看出来，当key计算出来的hashCode()只有高位变化时，最终算出来的index索引就会引起hash冲突，如果冲突太多的话，HashMap的效率就会非常低下了。

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

再来看看这段代码，对key的hashCode值进行再一次计算。在java中，hashCode是32位的。

首先，对hashCode进行16位的无符号右移。

（我们的例子就假设hashCode是8位的）

int hashCode1 = 01110101 >>> 4
--> hashCode1 = 00000111

int hasCode2 = 01010101 >>> 4
-->hasCode2 = 00000101

然后，对自身进行与或运算。

hashCode1 = 01110101 ^ 00000111
--> hashCode1 = 01110010

hashCode2 = 01010101 ^ 00000101
--> hashCode2 = 01010000

最后，取余

hashCode1 = 01110010 & 1111 = 0010
hashCode2 = 01010000 & 1111 = 0000

通过上面的分析，hash的再次计算能够把高位的变化影响到了低位的变化，真的很神奇啊

作者：曾泽浩
链接：https://www.jianshu.com/p/e1d3ba0c733a
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

HashMap

原文：https://www.cnblogs.com/islch/p/12817125.html