为简单起见,我的问题是:如何尽快散列一个字符串(大约 200 个字符)。安全性并不重要,但碰撞是个大问题。
注意:经过快速调查,似乎是MurmurHash3可能是最好的选择。我对任何意见持开放态度,尽管如此'
首先,我知道还有很多其他类似的问题,但我还没有找到一个令人信服的答案。
我有一个对象列表,每个对象都包含一个大约 3k 段落的列表,这些段落被保存到数据库中。每 X 小时,这些段落就会重新生成,我需要查找是否有任何段落已更改,如果有,则仅推送那些新段落。
我发现找到差异的最快方法(知道大多数时候内容是相同的)是创建一个 MerkleTree ,将其保存到数据库,并迭代 MerkleTree 以查找差异,而不是比较段落本身。
这意味着,在我的例子中,我将每秒创建一万个哈希来与数据库中的内容进行比较。因此,我需要一种非常有效的方法来创建这些哈希值。我不关心安全性,我只需要确保碰撞次数保持非常非常低。
Java 中可用的最佳算法是什么?
在我的例子中,主要对象由节组成,节由语言组成,语言由段落组成。比较策略是:
1) 如果对象哈希相同,则停止,否则转到2)
2) 循环所有Section,只保留具有不同哈希值的Section
3) 循环这些部分的所有语言,只保留具有不同散列的语言
4) 循环所有这些语言的所有段落,如果哈希不同,则推送新内容。
最佳答案
This amazing answer on Programmers Stack Exchange tells you all you need to know.
简而言之,使用 FNV-1a, aka the Fowler–Noll–Vo hash function ,它具有出色的性能、高随机性和低冲突。
我可能对这个问题做出的任何进一步解释只是从 Programmers.SE 的答案中复制粘贴,顺便说一下,这是整个网站上投票第二高的答案。
一些其他的想法:
- 最终,您将拥有一个非常适合的用例。大多数人不会定期处理 10 亿个条目数据集。因此,您可能需要自己进行基准测试。
- 也就是说,具有高随机性表明该算法可能适用于英语哈希。
- 你还没有真正谈论过其他问题;你能把整个数据集保存在内存中吗?您的足迹要求是什么?
关于java - Java 中最快的字符串哈希算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31816796/