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

[netty]

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

31 是奇素数。

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

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

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

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

[mejee]

推广就推广，还弄这么个标题

[wysnylc]

为什么不是 42 呢？选啥你都有破理由

[netty]

@mejee 另一个词叫：分享。标题本来就是这个啊，觉得有点价值的才分享。

[netty]

@wysnylc 怎么能这么说呢，文章有数据说明，不是乱来的

[mightofcode]

为什么“偶数的哈希效果非常差”呢

[aguesuka]

netty 这么好的 id，结果全是推广

[netty]

@mightofcode 哈希的效率，简单的理解取决于冲突：存储的冲突率，以及解决冲突的效率。偶数的哈希冲突率较高，解决冲突耗时，查找数据也耗时，O(1)最好，冲突越高越往 O(n)方向靠

[salamanderMH]

我在 SF 上看过一篇文章的分析 https://segmentfault.com/a/1190000010799123

[hantsy]

@netty 用什么简单的数学教程吗？现在很多年没有看算法之类，现在发现很多公式，Big O 看不懂。

[mightofcode]

@netty 为什么“偶数的哈希冲突率较高”呢，不太明白

[publicccc]

感觉一个奇怪的问题，
推广博客大家都比较包容，
但是推广公众号非常容易引起反感。

[chinvo]

虽然这个论坛不反对分享、转载，但是你这样“推广”真的很惹人厌

[netty]

@mightofcode
首先要注意的是，这个哈希算法针对的是 "字符串" 哈希码的计算。
其次，偶数的冲突率高针对的是这段算法，对于其他算法不一定适用：
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
目前据我了解到的，都是通过测试数据来证明。要解释为什么，就要去研究上面这段代码。
如果有同学更了解的，也可以解释一下^_^

[netty]

@chinvo 不好意思，向大家道歉，回去自我检讨。之前因为发表不了也没有发，现在可以发了，想到有几篇自己还不错的文章就发了一下。

[BruceHong]

这是实验数据结果观察来的，不仅是 Java，PHP 的数组底层 HashTable 实现也是这个数

[zxcslove]

@publicccc 应该是因为博客没有羁绊，公众号有

[secondwtq]

"推广“公众号文章我觉得没什么，这个贴子只看内容除了链接域名不一样之外和其他分享博客文章的没啥区别，也没放个二维码求关注。

主要是这个标题看上去像个问题，点进来发现是个文章。

[deepreader]

数据量大的项目，结果数据天天就 hash collisions。
已经换成 farmhash 了。

[goodboy95]

来，以纯小写字母（或者纯大写字母），长度较长（假设超过 50 ）字符串的 hash 为例，楼主能说出上面这些测试的理论依据吗？
第一个是“小数值的哈希冲突率较高”（此处的小数值暂时限制为 1-25 ）
第二个是“偶数的哈希冲突率较高”
这应该很简单吧，真正去研究的话会发现这些不过是大一难度，别一上来就用测试啊，有理论基础之后的测试才更容易让人接受。

[goodboy95]

不然的话，就告诉我们这么个结论，面试的时候帮不上忙啊（逃
好吧，我承认我有点功利了（被各种一面没下文搞的心态不稳了 hhh ）