9
|
David Citron · 技术社区 · 16 年前 |
![]() |
1
12
我不确定您是否遗漏了文档中的“^表示求幂”(而不是xor)。
每次通过循环时,哈希的前一个值乘以31
再一次
在添加到的下一个元素之前
我们可以通过归纳法证明这些东西是相等的,但我认为一个例子可能更多 清楚: 假设我们正在处理一个4字符的字符串。让我们展开循环:
现在,通过将哈希的每个值替换为以下语句,将这些值组合成一个语句:
31*0为0,因此简化:
现在将两个内项乘以第二个31:
现在将三个内部术语乘以前31个:
并转换成指数(不再是Java):
|
![]() |
2
24
展开循环。然后你得到:
现在您可以进行一些数学操作,插入0作为初始哈希值:
再简化一点:
这基本上就是给出的原始算法。 |
![]() |
3
10
归纳法证明:
我想我拿到了,要求提供证据。 |
![]() |
4
9
看看前几个迭代,您会发现模式开始出现: hash0 = 0 + s0 = s0 hash1 = 31(hash0) + s1 = 31(s0) + s1 hash2 = 31(hash1) + s2 = 31(31(s0) + s1) + s2 = 312(s0) + 31(s1) + s2 ... |
![]() |
5
0
把字符串的散列码数出来是不是一点用都没有? 所有字符中 ?想象一下文件名或类名的完整路径放入哈希集中。或者使用字符串文档而不是列表的哈希集的人,因为“ HashSet always beats Lists “。 我会做如下的事情:
最后,hashcode只是一个提示。 |
![]() |
danial · 如何在多个字符串的每个位置找到最频繁的字符 2 年前 |
![]() |
Manny · 如何比较Perl中的字符串? 2 年前 |
![]() |
Diret · 获取范围内每个数字的子倍数的算法 2 年前 |
![]() |
Saif · 排序时python如何决定何时调用比较器? 2 年前 |