【Java深入研究】11、深入研究hashmap中的hash算法

2019-08-09 00:00:00 java 算法 研究

一、简介

大家都知道,HashMap中定位到桶的位置 是根据Key的hash值与数组的长度取模来计算的。

JDK8中的hash 算法:

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

取模算法:

hash(key)&(length-1)

二、深入分析

1、取模算法为什么用的是位与运算?

由于位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。

2的倍数取模,只要将数与2的倍数-1做按位与运算即可。

对原理感兴趣的可以参考【Java基础】14、位与(&)操作与快速取模

2、为什么不直接使用key.hashcode()进行取模运算?

我们知道hash的目的是为了尽量分布均匀。

取模做位与运算的时候,实际上刚刚开始数组的长度一般比较小,只利用了低16位,高16位是用不到的。这种情况下,产生hash冲突的概率会大大增加。

这样设计保证了对象的hashCode的高16位的变化能反应到低16位中,相比较而言减少了hash冲突的情况 。

选用亦或的方式是因为&和|都会使得结果偏向0或者1 ,并不是均匀的概念。

3、String的hashCode()深入分析

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

推导出的公式如下:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

举个例子推导计算一下:

假设 n=3
i=0 -> h = 31 * 0 + val[0]
i=1 -> h = 31 * (31 * 0 + val[0]) + val[1]
i=2 -> h = 31 * (31 * (31 * 0 + val[0]) + val[1]) + val[2]
       h = 31*31*31*0 + 31*31*val[0] + 31*val[1] + val[2]
       h = 31^(n-1)*val[0] + 31^(n-2)*val[1] + val[2]

3.1、为什么使用31作为计算的因子呢?

  • 选择质数作为乘子,会大大降低hash冲突的概率。质数的值越大,hash冲突率越低
  • 31参与乘法运算,可以被 JVM 优化,31 * i = (i << 5) - i
  • 使用 101 计算 hash code 容易导致整型溢出,导致计算精度丢失

 

 

 

 

,

3、String的hashCode()深入分析

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

推导出的公式如下:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

举个例子推导计算一下:

假设 n=3
i=0 -> h = 31 * 0 + val[0]
i=1 -> h = 31 * (31 * 0 + val[0]) + val[1]
i=2 -> h = 31 * (31 * (31 * 0 + val[0]) + val[1]) + val[2]
       h = 31*31*31*0 + 31*31*val[0] + 31*val[1] + val[2]
       h = 31^(n-1)*val[0] + 31^(n-2)*val[1] + val[2]

3.1、为什么使用31作为计算的因子呢?

  • 选择质数作为乘子,会大大降低hash冲突的概率。质数的值越大,hash冲突率越低
  • 31参与乘法运算,可以被 JVM 优化,31 * i = (i << 5) - i
  • 使用 101 计算 hash code 容易导致整型溢出,导致计算精度丢失

 

 

相关文章