转载请注明出处:http://anxpp.com/,谢谢!

    我们知道,使用散列的容器,其高性能的主要影响因素之一就是hash值。

    在HashMap中,为了更好的性能,我们希望作为Key的对象提供一个合理的hash函数以便能将其合理的分配到桶中。

    而在实际的HashMap中,对从对象获取的hash值又做了调整。

    我们先看源码:

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

    我们可以将其详细步骤等价改为如下:

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

    代码过程的直接翻译就是:如果Key值为null,返回0;如果Key值不为空,返回原hash值和原hash值无符号右移16位的值按位异或的结果。

    我们知道,按位异或就是把两个数按二进制,相同就取0,不同就取1。

    比如:0101 ^ 1110 的结果为 1011。(记得以前上数字电路课的时候学过)异或的速度是非常快的。

    把一个数右移16位即丢弃低16为,就是任何小于216的数,右移16后结果都为0(2的16次方再右移刚好就是1)。

    任何一个数,与0按位异或的结果都是这个数本身(很好验证)。

    所以这个hash()函数对于非null的hash值,仅在其大于等于216的时候才会重新调整其值。

    但是调整后又什么好处呢?

    我们先看下put的时候,这个hash值是怎么处理(部分源码)的:

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
    ......
    }

    在寻找桶位的时候,这个hash值为与上table的zise-1,初始为16,我们就拿16来举例.

    以为算法是hashValue & size - 1 ,此时size-1=15的二进制为 1 1 1 1 ,也就是任意类似16进制0x?0(二进制最后四位为0000)的hash值,都会被存储到位置为0的桶位上,一个桶中的元素太多,就一定会降低其性能,但是我们来看看这样的hash值经过上面的函数处理过后的结果:

public class TestHashCodeMethod {
    public static void main(String args[]) throws Exception{
        final int max = Integer.MAX_VALUE >>> 4;
        Random random = new Random(System.currentTimeMillis());
        for(int i=0;i<20;i++){
            int hash = random.nextInt(max) << 4;
            int betterHash = hash ^ (hash >>> 16);
            System.out.print(toBinaryString(hash));
            System.out.println("-->" + toBinaryString(betterHash));
        }
    }
    //将整数转换为二进制字符串,高位补0
    final static char[] digits = {'0','1'};
    static String toBinaryString(int i) {
        char[] buf = new char[32];
        int pos = 32;
        int mask = 1;
        do {
            buf[--pos] = digits[i & mask];
            i >>>= 1;
        } while (pos > 0);
        return new String(buf, pos, 32);
    }
}

    查看结果该hash函数转换后的值:

00011000000100011111000101100000-->00011000000100011110100101110001
00110111100110001011010000100000-->00110111100110001000001110111000
01101110000011101111100011010000-->01101110000011101001011011011110
00000000000111110010101100010000-->00000000000111110010101100001111
00110101101001101000010010010000-->00110101101001101011000100110110
00101111111111001011000101010000-->00101111111111001001111010101100
01100101111101101110100110110000-->01100101111101101000110001000110
00000011101101101110000110100000-->00000011101101101110001000010110
00100011001101010011110010110000-->00100011001101010001111110000101
01101101111010000001111011110000-->01101101111010000111001100011000
01111001111100110101000101010000-->01111001111100110010100010100011
00111110101001111101100110100000-->00111110101001111110011100000111
01011001000001101010011001110000-->01011001000001101111111101110110
01101000101100101110101100100000-->01101000101100101000001110010010
01100110111011001111110001000000-->01100110111011001001101010101100
00100001100011000010110001100000-->00100001100011000000110111101100
01100010001010000110101111110000-->01100010001010000000100111011000
00000011001111101111111110110000-->00000011001111101111110010001110
00111110100100101011111110110000-->00111110100100101000000100100010
01000100000101011111111110000000-->01000100000101011011101110010101

    是不是发现情况都发生了好转,原来一大批会被放到“0”桶位的hash值,现在几乎都被更佳合理的分配到了其他桶位。

    我们知道hashMap中的桶位都是以oldCap<<1(即原容量*2)来增长的,所以最终这个hash值要存放的时候,都是跟一连串二进制的“1"作与运算的,而容量定义为int类型,java中int类型为4字节,即32位,但是Integer.MAX为0x7fffffff,也就是231 - 1 那么大(因为最高位被用作符号位),而取16算是一种折衷的办法。而另一个原因,也许是跟对象本身的hash值(当然也为int)有关。

    那么这个方法就介绍这么多了,近期准备将HashMap整个源码解读一下,并分享出来,并在最终整体介绍一下Java的容器体系。

    之前已发过两篇容器的源码解读,这里给出链接:

    Java之LinkedList源码解读(JDK 1.8)

    Java之ArrayList源码解读(JDK 1.8)