jac*_*bko 461 java string algorithm hash
每Java文档中,哈希代码的String对象被计算为:
Run Code Online (Sandbox Code Playgroud)s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]使用
int算术,其中s[i]是 字符串的第i个字符,是字符串n的长度,并^指示取幂.
为什么31用作乘数？
我知道乘数应该是一个相对较大的素数.那么为什么不是29岁,37岁,甚至97岁？
mat*_*t b 386
根据Joshua Bloch的Effective Java(一本不能推荐的书,以及我在stackoverflow上不断提及而购买的书):
选择值31是因为它是奇数素数.如果它是偶数并且乘法溢出,则信息将丢失,因为乘以2相当于移位.使用素数的优势不太明显,但它是传统的.31的一个很好的特性是乘法可以用移位和减法代替,以获得更好的性能:
31 * i == (i << 5) - i.现代VM自动执行此类优化.
(来自第3章,第9项:覆盖等于时始终覆盖哈希码,第48页)
Joh*_*Zaj 79
正如古德里奇和塔玛西亚指出的那样,如果你接受超过50,000个英语单词(形成为两个Unix变体中提供的单词列表的联合),使用常数31,33,37,39和41将产生少于7个冲突在每种情况下.知道这一点,许多Java实现选择其中一个常量应该不足为奇.
巧合的是,当我看到这个问题时,我正在阅读"多项式哈希码"部分.
编辑:这里是我上面提到的~10mb PDF书的链接.请参见Java中的数据结构和算法的第10.2节哈希表(第413页)
Tom*_*ine 55
在(大多数)旧处理器上,乘以31可能相对便宜.例如,在ARM上,它只有一条指令:
RSB r1, r0, r0, ASL #5 ; r1 := - r0 + (r0<<5)
大多数其他处理器需要单独的移位和减法指令.但是,如果你的乘数很慢,这仍然是一个胜利.现代处理器往往具有快速乘法器,因此它没有太大的区别,只要32在正确的一侧.
它不是一个很好的哈希算法,但它足够好并且比1.0代码更好(并且比1.0规范好得多!).
eri*_*son 30
通过相乘,位向左移位.这使用了更多可用的哈希码空间,减少了冲突.
通过不使用2的幂,也填充低阶最右边的位,以与进入散列的下一个数据混合.
表达式n * 31相当于(n << 5) - n.
Dav*_*aro 25
您可以在http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622的 "评论"下阅读Bloch的原始推理.他研究了哈希表中得到的"平均链大小"的不同哈希函数的性能.P(31)这是他在K&R的书中找到的那个时期的常见功能之一(但即使是Kernighan和Ritchie也记不住它的来源).最后他基本上不得不选择一个,所以他采取了,P(31)因为它似乎表现得很好.即使P(33)不是真的更糟糕,乘以33同样快速计算(只是换一个5和一个加法),他选择了31因为33不是素数:
在其余四个中,我可能选择P(31),因为它是在RISC机器上计算最便宜的(因为31是2的两个幂的差异).P(33)计算起来同样便宜,但它的表现稍微差一些,而且33是复合的,这让我有点紧张.
因此,推理并不像这里的许多答案所暗示的那样理性.但是在我们做出决定之后,我们都很善于提出合理的理由(甚至布洛赫也可能会这样做).
hrr*_*hrr 22
实际上,37会很好用!z:= 37*x可以计算为y := x + 8 * x; z := x + 4 * y.这两个步骤都对应于一个LEA x86指令,因此速度非常快.
实际上,通过设置可以以相同的速度与更大的素数73相乘y := x + 8 * x; z := x + 8 * y.
使用73或37(而不是31)可能会更好,因为它会导致更密集的代码:两个LEA指令只需要6个字节,而7个字节用于移动+移位+减法乘以31个.一个可能的警告是这里使用的3参数LEA指令在英特尔的Sandy网桥架构上变得更慢,延迟增加了3个周期.
此外,73是Sheldon Cooper最喜欢的号码.
来自JDK-4045622,Joshua Bloch描述了String.hashCode()选择特定(新)实施的原因
下表总结了上述各种哈希函数对三个数据集的性能:
1)所有在Merriam-Webster的第二个国际完整字典中有条目的单词和短语(311,141个字符串,平均长度为10个字符).
2)/ bin/,/ usr/bin /,/ usr/lib/,/ usr/ucb / 和/ usr/openwin/bin/*(66,304字符串,平均长度为21个字符)中的所有字符串.
3)由昨晚运行了几个小时的网络爬虫收集的URL列表(28,372个字符串,平均49个字符).
表中显示的性能指标是散列表中所有元素的"平均链大小"(即,查找元素时密钥数量的预期值).
Run Code Online (Sandbox Code Playgroud)Webster's Code Strings URLs --------- ------------ ---- Current Java Fn. 1.2509 1.2738 13.2560 P(37) [Java] 1.2508 1.2481 1.2454 P(65599) [Aho et al] 1.2490 1.2510 1.2450 P(31) [K+R] 1.2500 1.2488 1.2425 P(33) [Torek] 1.2500 1.2500 1.2453 Vo's Fn 1.2487 1.2471 1.2462 WAIS Fn 1.2497 1.2519 1.2452 Weinberger's Fn(MatPak) 6.5169 7.2142 30.6864 Weinberger's Fn(24) 1.3222 1.2791 1.9732 Weinberger's Fn(28) 1.2530 1.2506 1.2439看看这个表,很明显除了当前的Java函数和Weinberger函数的两个破坏版本之外的所有函数都提供了极好的,几乎无法区分的性能.我强烈推测这种性能本质上是"理论上的理想",如果您使用真正的随机数生成器代替散列函数,这就是您所获得的.
我排除了WAIS函数,因为它的规范包含随机数的页面,并且它的性能并不比任何更简单的函数更好.其余六个功能中的任何一个看起来都是很好的选择,但我们必须选择一个.我想我会排除Vo的变体和Weinberger的功能,因为它们增加了复杂性,尽管很小.在其余四个中,我可能选择P(31),因为它是在RISC机器上计算最便宜的(因为31是2的两个幂的差异).P(33)计算起来同样便宜,但它的表现稍微差一些,而且33是复合的,这让我有点紧张.
玩笑
Java 字符串 hashCode() 和 31
\n这是因为 31 有一个很好的属性 \xe2\x80\x93 它的乘法可以用按位移位代替，这比标准乘法更快：
\n31 * i == (i << 5) - i\nBloch 并没有深入探讨这一点，但我一直听到/相信的基本原理是这是基本代数。哈希归结为乘法和模运算，这意味着如果可以帮助，您永远不想使用具有公因数的数字。换句话说，相对质数提供了均匀分布的答案。
使用散列组成的数字通常是：
您实际上只能控制其中的几个值，因此需要格外小心。
在最新版本的 JDK 中，仍然使用 31。https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/lang/String.html#hashCode()
哈希字符串的目的是
^哈希码计算文档中的运算符，它有助于唯一）31 是最大值可以放入 8 位（= 1 字节）寄存器，最大质数可以放入 1 字节寄存器，是奇数。
乘以 31 是 <<5 然后减去自身，因此需要便宜的资源。