java - Java 中最快的字符串哈希算法

Question

为简单起见，我的问题是:如何尽快散列一个字符串(大约 200 个字符)。安全性并不重要，但碰撞是个大问题。

注意:经过快速调查，似乎是MurmurHash3可能是最好的选择。我对任何意见持开放态度，尽管如此'

首先，我知道还有很多其他类似的问题，但我还没有找到一个令人信服的答案。

我有一个对象列表，每个对象都包含一个大约 3k 段落的列表，这些段落被保存到数据库中。每 X 小时，这些段落就会重新生成，我需要查找是否有任何段落已更改，如果有，则仅推送那些新段落。

我发现找到差异的最快方法(知道大多数时候内容是相同的)是创建一个 MerkleTree ，将其保存到数据库，并迭代 MerkleTree 以查找差异，而不是比较段落本身。

这意味着，在我的例子中，我将每秒创建一万个哈希来与数据库中的内容进行比较。因此，我需要一种非常有效的方法来创建这些哈希值。我不关心安全性，我只需要确保碰撞次数保持非常非常低。

Java 中可用的最佳算法是什么？

---

在我的例子中，主要对象由节组成，节由语言组成，语言由段落组成。比较策略是:

1) 如果对象哈希相同，则停止，否则转到2)

2) 循环所有Section，只保留具有不同哈希值的Section

3) 循环这些部分的所有语言，只保留具有不同散列的语言

4) 循环所有这些语言的所有段落，如果哈希不同，则推送新内容。

Answer 1

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 亿个条目数据集。因此，您可能需要自己进行基准测试。
• 也就是说，具有高随机性表明该算法可能适用于英语哈希。
• 你还没有真正谈论过其他问题；你能把整个数据集保存在内存中吗？您的足迹要求是什么？

另见:Fastest Hash Algorithm for Text Data