这是一个创建于 1795 天前的主题，其中的信息可能已经有所发展或是发生改变。
Java String 类的哈希乘数选择 31，主要有以下几点考虑：
31 是奇素数。
哈希分布较为均匀。偶数的冲突率基本都很高，只有少数例外。较小的乘数，冲突率也比较高，如 1 至 20。
哈希计算速度快。可用移位和减法来代替乘法。现代的 VM 可以自动完成这种优化，如 31 * i = (i << 5) - i。
31 和 33 的计算速度和哈希分布基本一致，整体表现好，选择它们就很自然了。
 |
1
mejee 2020-01-30 18:50:57 +08:00 via iPhone  3
推广就推广，还弄这么个标题
|
 |
2
wysnylc 2020-01-30 18:53:49 +08:00 via Android
为什么不是 42 呢？选啥你都有破理由
|
 |
5
mightofcode 2020-01-30 19:04:26 +08:00
为什么“偶数的哈希效果非常差”呢
|
 |
6
aguesuka 2020-01-30 19:08:01 +08:00
netty 这么好的 id，结果全是推广
|
 |
7
netty OP @mightofcode 哈希的效率，简单的理解取决于冲突：存储的冲突率，以及解决冲突的效率。偶数的哈希冲突率较高，解决冲突耗时，查找数据也耗时，O(1)最好，冲突越高越往 O(n)方向靠
|
 |
8
salamanderMH 2020-01-30 19:40:56 +08:00
我在 SF 上看过一篇文章的分析 https://segmentfault.com/a/1190000010799123
|
|
10
mightofcode 2020-01-30 19:48:39 +08:00
@netty 为什么“偶数的哈希冲突率较高”呢，不太明白
|
 |
11
publicccc 2020-01-30 19:50:54 +08:00
感觉一个奇怪的问题，
推广博客大家都比较包容， 但是推广公众号非常容易引起反感。 |
 |
12
chinvo 2020-01-30 19:52:20 +08:00 via iPhone
虽然这个论坛不反对分享、转载，但是你这样“推广”真的很惹人厌
|
|
13
netty OP @mightofcode
首先要注意的是，这个哈希算法针对的是 "字符串" 哈希码的计算。 其次，偶数的冲突率高针对的是这段算法，对于其他算法不一定适用： for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } 目前据我了解到的，都是通过测试数据来证明。要解释为什么，就要去研究上面这段代码。 如果有同学更了解的，也可以解释一下^_^ |
|
14
netty OP @chinvo 不好意思，向大家道歉，回去自我检讨。之前因为发表不了也没有发，现在可以发了，想到有几篇自己还不错的文章就发了一下。
|
 |
15
BruceHong 2020-01-30 21:18:38 +08:00 1
这是实验数据结果观察来的，不仅是 Java，PHP 的数组底层 HashTable 实现也是这个数
|
 |
17
secondwtq 2020-01-31 21:25:42 +08:00
"推广“公众号文章我觉得没什么，这个贴子只看内容除了链接域名不一样之外和其他分享博客文章的没啥区别，也没放个二维码求关注。
主要是这个标题看上去像个问题，点进来发现是个文章。 |
 |
18
deepreader 2020-02-01 08:26:55 +08:00
数据量大的项目，结果数据天天就 hash collisions。
已经换成 farmhash 了。 |
 |
19
goodboy95 2020-04-01 20:52:36 +08:00
来，以纯小写字母（或者纯大写字母），长度较长（假设超过 50 ）字符串的 hash 为例，楼主能说出上面这些测试的理论依据吗？
第一个是“小数值的哈希冲突率较高”（此处的小数值暂时限制为 1-25 ） 第二个是“偶数的哈希冲突率较高” 这应该很简单吧，真正去研究的话会发现这些不过是大一难度，别一上来就用测试啊，有理论基础之后的测试才更容易让人接受。 |
|
20
goodboy95 2020-04-01 21:01:14 +08:00
不然的话，就告诉我们这么个结论，面试的时候帮不上忙啊（逃
好吧，我承认我有点功利了（被各种一面没下文搞的心态不稳了 hhh ） |
Select Language