HashCode算法为什么采用31作为乘数

一、为什么 String 重写 equals() 后还需要重写 hashcode()

hashCode() 的源码:

两个对象比较,由于 Java 默认比较的是类的地址值,每个对象一定是不同的,所以重写 hashCode() 和 equals()。重写 hashCode() 是为了提高效率,因为先根据类里的属性生成 hashCode,如果生成的 hashCode 值不同,则没必要再使用 equals() 比较属性的值,这样就大大减少了 equals 的次数,这对大数据量比较的效率提高是很明显的。一个很好的例子就是在集合中的使用:

Java 中的 List 集合是有序的,因此是可以重复的。set 集合是无序的,因此是不能重复的,那么如何保证不能被放入重复的元素呢,单靠 equals() 比较的话,如果原来集合中已有 10000 个元素了,那么放入 10001 个元素,难道要将前面的所有元素都进行比较,看看是否有重复?这个效率可想而知,因此 hashcode 就应遇而生了,Java 就采用了 hash 表,利用哈希算法(也叫散列算法),就是将对象数据根据该对象的特征使用特定的算法将其定义到一个地址上,那么在后面定义进来的数据只要看对应的 hashCode 地址上是否有值,那么就用 equals 比较,如果没有则直接插入,如此大大减少了 equals 的使用次数,执行效率就大大提高了。

为什么必须要重写 hashCode(),简言之就是为了保证同一个对象,在 equals 相同的情况下 hashCode 值也相同。如果重写了 equals() 而未重写 hashCode(),可能就会出现两个没有关系的对象 equals 相同(因为 equals 都是根据对象的特征进行重写的),但 hashCode 不同的情况。

String 是遵守类 hashCode 的协定,equals() 相同,如何保持 hashCode 相同。初始 String 对象成员变量 int hash 默认是 0,调用 hashCode() 之后h = 31 * h + val[i],其实就是 String 内部根据 char[] 来进行一个运算。那么只要内容 equals(),其内容运算生产的 hashCode() 也是相等的。这里也阐明了 equals() 与 hashCode() 在一般应用中的正向关系。

二、HashCode算法为什么采用 31 作为乘数

1️⃣更少的乘积结果冲突
31 是质子数中一个“不大不小”的存在,如果使用的是一个如 2 的较小质数,那么得出的乘积会在一个很小的范围,很容易造成哈希值的冲突。而如果选择一个 100 以上的质数,得出的哈希值会超出 int 的最大范围,这两种都不合适。而如果对超过 50,000 个英文单词(由两个不同版本的 Unix 字典合并而成)进行 hashCode() 运算,并使用常数 31、33、37、39 和 41 作为乘子,每个常数算出的哈希值冲突数都小于 7 个(国外大神做的测试),那么这几个数就被作为生成 hashCode 值的备选乘数了。

2️⃣31 可以被 JVM 优化

位运算是 JVM 里最有效的计算方式:

  1. 【左移 <<】左边的最高位丢弃,右边补全0(把 << 左边的数据*2的移动次幂)。
  2. 【右移 >>】把>>左边的数据/2的移动次幂。
  3. 【无符号右移 >>>】无论最高位是 0 还是 1,左边补齐 0。

所以:31 * i = (i << 5) - i【例如:31*2=62 转换为 2*2^5-2=62】

3️⃣理解

  1. 首先 hash 函数必须要选用质/素数,这个是被科学家论证过的 hash 函数减少冲突的一个理论。
  2. 如果设置为偶数的话会存在溢出的情况,导致信息丢失(因为使用偶数相当于使用了移位运算)。
  3. 可以兼顾到虚拟机的性能,虚拟机默认使用2<<5-1来得到很好的性能,且其是一个不大不小的质数,兼顾了性能和冲突率。

为什么 31 的性能和解决冲突是最优的?回顾 String 对象的 hashCode():

/**
     * Returns a hash code for this string. The hash code for a
     * {@code String} object is computed as
     * <blockquote><pre>
     * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
     * </pre></blockquote>
     * using {@code int} arithmetic, where {@code s[i]} is the
     * <i>i</i>th character of the string, {@code n} is the length of
     * the string, and {@code ^} indicates exponentiation.
     * (The hash value of the empty string is zero.)
     *
     * @return  a hash code value for this object.
     */
    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;
    }

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

选择不大不小的质数的原因

正如备注上所描述的那样,这段代码的实际执行方法如下:

s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1] 推算过程为
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]

因此可以代入式的计算一下,假如有一个String test = “abcdef”六个字母。使用一个较小的质数 2 或者一个较大的质数 101 带入进去,前者2^(6-1) = 32,后者101^(6-1) = 10 510 100 501。 一个太小一个太大。太小的话 hash 冲突的概率就会相对大一些,太大的话就会太过于分散,对于 hash 结构的集合来说就会占用过的存储空间。因此选择不大不小的质数是非常有必要的。

如何证明 31 这个数值就比其他数值优呢?

整型的数值区间是 [-2147483648, 2147483647],区间大小为 2^32。所以这里可以将区间等分成 64 个子区间,每个子区间大小为 2^26。

  1. 乘子 2 算出的哈希值几乎全部落在第 32 分区,也就是 [0, 67108864) 数值区间内,落在其他区间内的哈希值数量几乎可以忽略不计。这也就不难解释为什么数字 2 作为乘子时,算出哈希值的冲突率如此之高的原因了。

  2. 乘子 101,冲突率很低,这也说明哈希值溢出并不一定会导致冲突率上升。但是还是因为乘积太大导致整数溢出的问题。所以 Java 在设计的时候是为了兼顾性能和 hash 函数的分散性。

由此,使用 31 这数值,可以说是最佳实践。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,293评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,604评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,958评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,729评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,719评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,630评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,000评论 3 397
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,665评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,909评论 1 299
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,646评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,726评论 1 330
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,400评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,986评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,959评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,197评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,996评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,481评论 2 342