为什么 Java String 哈希乘数为 31?

netty 25天前 22

Java String 类的哈希乘数选择 31,主要有以下几点考虑:

31 是奇素数。

哈希分布较为均匀。偶数的冲突率基本都很高,只有少数例外。较小的乘数,冲突率也比较高,如 1 至 20。

哈希计算速度快。可用移位和减法来代替乘法。现代的 VM 可以自动完成这种优化,如 31 * i = (i << 5) - i。

31 和 33 的计算速度和哈希分布基本一致,整体表现好,选择它们就很自然了。

https://mp.weixin.qq.com/s/sCWQGU_OWiQkDUuSPXvw-w

最新回复 (18)
  • mejee 21天前
    引用 2
    推广就推广,还弄这么个标题
  • wysnylc 21天前
    引用 3
    为什么不是 42 呢?选啥你都有破理由
  • 楼主 netty 21天前
    引用 4
    @mejee 另一个词叫:分享。标题本来就是这个啊,觉得有点价值的才分享。
  • 楼主 netty 21天前
    引用 5
    @wysnylc 怎么能这么说呢,文章有数据说明,不是乱来的
  • mightofcode 21天前
    引用 6
    为什么“偶数的哈希效果非常差”呢
  • aguesuka 21天前
    引用 7
    netty 这么好的 id,结果全是推广
  • 楼主 netty 21天前
    引用 8
    @mightofcode 哈希的效率,简单的理解取决于冲突:存储的冲突率,以及解决冲突的效率。偶数的哈希冲突率较高,解决冲突耗时,查找数据也耗时,O(1)最好,冲突越高越往 O(n)方向靠
  • salamanderMH 21天前
    引用 9
    我在 SF 上看过一篇文章的分析 https://segmentfault.com/a/1190000010799123
  • hantsy 21天前
    引用 10
    @netty 用什么简单的数学教程吗?现在很多年没有看算法之类,现在发现很多公式,Big O 看不懂。
  • mightofcode 21天前
    引用 11
    @netty 为什么“偶数的哈希冲突率较高”呢,不太明白
  • publicccc 21天前
    引用 12
    感觉一个奇怪的问题,
    推广博客大家都比较包容,
    但是推广公众号非常容易引起反感。
  • chinvo 21天前
    引用 13
    虽然这个论坛不反对分享、转载,但是你这样“推广”真的很惹人厌
  • 楼主 netty 21天前
    引用 14
    @mightofcode
    首先要注意的是,这个哈希算法针对的是 "字符串" 哈希码的计算。
    其次,偶数的冲突率高针对的是这段算法,对于其他算法不一定适用:
    for (int i = 0; i < value.length; i++) {
    h = 31 * h + val[i];
    }
    目前据我了解到的,都是通过测试数据来证明。要解释为什么,就要去研究上面这段代码。
    如果有同学更了解的,也可以解释一下^_^
  • 楼主 netty 21天前
    引用 15
    @chinvo 不好意思,向大家道歉,回去自我检讨。之前因为发表不了也没有发,现在可以发了,想到有几篇自己还不错的文章就发了一下。
  • BruceHong 21天前
    引用 16
    这是实验数据结果观察来的,不仅是 Java,PHP 的数组底层 HashTable 实现也是这个数
  • zxcslove 21天前
    引用 17
    @publicccc 应该是因为博客没有羁绊,公众号有
  • secondwtq 21天前
    引用 18
    "推广“公众号文章我觉得没什么,这个贴子只看内容除了链接域名不一样之外和其他分享博客文章的没啥区别,也没放个二维码求关注。

    主要是这个标题看上去像个问题,点进来发现是个文章。
  • deepreader 21天前
    引用 19
    数据量大的项目,结果数据天天就 hash collisions。
    已经换成 farmhash 了。
  • 游客
    20
返回