8

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

注意:经过快速调查,似乎MurmurHash3可能是最佳选择。我愿意接受任何评论,否则'

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

我有一个对象列表,每个对象都包含一个保存到数据库的大约 3k 段落的列表。每隔 X 小时,这些段落就会重新生成,我需要查找是否有任何段落发生了变化,如果是,则只推送那些新段落。

我发现找到差异的最快方法(知道大部分时间内容是相同的)是创建一个MerkleTree,将其保存到数据库,然后遍历 MerkleTree 以找到差异,而不是比较段落本身.

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

Java中最好的算法是什么?


在我的例子中,主要对象由 Sections 组成,Sections 由 Languages 组成,Languages 由 Paragraph 组成。比较策略是:

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

2)在所有Section上循环,只保留具有不同哈希的Section

3)循环这些部分的所有语言,只保留具有不同哈希的语言

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

4

1 回答 1

7

Programmers Stack Exchange 上的这个惊人答案告诉你所有你需要知道的。

简短的版本是,使用FNV-1a,又名 Fowler-Noll-Vo 哈希函数,它具有出色的性能、高随机性和低冲突。

我可能对这个问题的任何进一步解释只是从 Programmers.SE 答案的复制和粘贴,顺便说一句,这是整个网站上投票第二高的答案。

其他一些想法:

  • 最终,您有一个非常利基的用例。大多数人不会定期处理 10 亿个条目数据集。因此,您可能必须进行自己的基准测试。
  • 也就是说,具有高随机性表明该算法很可能适用于英语散列。
  • 您还没有真正谈论过其他问题;你能把整个数据集保存在内存中吗?您的足迹要求是什么?

另请参阅:文本数据的最快哈希算法

于 2015-08-04T18:58:12.170 回答