Java HashMap的hash和indexFor函数_JAVA_编程开发_程序员俱乐部

??????? 此文章，我们将一起了解一下hash和indexFor方法在hashmap内部起什么作用。hash和indexFor方法属于HashMap类，为什么JDK开发者在key对象已经有他自己的hashcode方法的情况下还需要另一个hash函数？

??????? 首先看一下hash和indexFor方法的代码：

????????

class="java">/**
     * 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);
    }

????? 正如java doc对hash方法的描述：将hash函数作为已给定的hashCode的一个补充，可以提高hash函数的质量。hash质量的好坏是非常重要的，因为HashMap用2的次幂作为表的hash长度，这就容易产生冲突，因为hashCodes在低位不是不同的（hashCodes that do not differ in lower bits）。注意：Null 的key的hash值总是0，即他在table的索引为0。

?????? 让我们通过例子来帮助我们理解一下上面的话。加入说key object的hashCode()只返回三个值：31、63和95.31、63和95都是int型，所以是32位的。

??????? 31=00000000000000000000000000011111
? ? ? ? 63=00000000000000000000000000111111
??????? 95=00000000000000000000000001011111

????? 现在加入HashMap的table长为默认值16(2^4,HashMap的长度总是2的次幂)

????? 假如我们不用hash函数，indexFor将返回如下值：

????? 31=00000000000000000000000000011111 => 1111=15
????? 63=00000000000000000000000000111111? => 1111=15
????? 95=00000000000000000000000001011111 => 1111=15

为什么会这样？因为当我们调用indexFor函数的时候，它将执行31&15，,63&15和95&15的与操作，比如说95&15得出一下结果：

??????? 00000000000000000000000001011111 &00000000000000000000000000001111

??????? 也就是说(2^n-1)总会是一个1的序列，因此不管怎样，最后会执行0&1的于然后得出0.

??????? 上面的例子，也就解释了凡是在末尾全是1111的都返回相同的index，因此，尽管我们有不同的hashcode，Entry对象却讲都被存在table中index为15的位置。

??????? 倘若我们使用了hash函数，对于上面每一个hashcode，经过hash作用作用后如下：

??????? 31=00000000000000000000000000011111 => 00000000000000000000000000011110
??????? 63=00000000000000000000000000111111? => 00000000000000000000000000111100
???? ?? 95=00000000000000000000000001011111 => 00000000000000000000000001011010

??????? 现在在通过新的hash之后再使用indexFor将会返回：

??????? 00000000000000000000000000011110 =>1110=14
??????? 00000000000000000000000000111100 =>1100=12
??????? 00000000000000000000000001011010 =>1010=10

??????? 在使用了hash函数之后，上面的hashcodes就返回了不同的index，因此，hash函数对hashmap里的元素进行了再分配，也就减少了冲突同时提高了性能。

???????? hash操作最主要的目的就是在最显著位的hashcode的差异可见，以致于hashmap的元素能够均匀的分布在整个桶里。

???????? 有两点需要注意：

????????? 如果两个key有相同的hashcode，那他们将被分配到table数组的相同index上

?????????? 如果两个key不具有相同的hashcode，那么他们或许可能，或许也不可能被分配到table数组相同的index上。

???????? 英文参考文档：http://javapostsforlearning.blogspot.in/2014/02/hash-and-indexfor-method-in-hashmap.html

?