hash - 散列函数是增量的意味着什么？

Question

例如，我听说 MurmurHash2 不是“增量的”，但 MurmurHash3 是增量的。这是什么意思？为什么它有用？

Answer 1

增量散列函数适用于如果先前散列的消息 M 稍微更新为新消息 M* 的情况，那么计算更新消息 M* 的散列值应该相当快。这是通过从旧散列值 m 计算新散列 m* 来完成的，而传统散列函数必须从头开始重新计算新散列 m*，这需要更长的时间。

http://www.cs.berkeley.edu/~daw/papers/inchash-cs06.pdf

它们之所以有用，是因为它们更容易计算，因此在计算能力和时间方面成本更低。

然而，它们并不适合所有情况。伯克利的那篇论文有一些很好的例子，说明它们何时可以在引言部分有用。

Answer 2

我不是这方面的专家，但我认为 MurmurHash3 在 tommarshall 所描述的意义上并不是增量的。

当人们将其描述为增量时，他们可能意味着您可以在 O(1) 内存中计算流的哈希值，即您可以拥有一个 API 让您执行以下操作（在伪代码中）：

x = Hasher()
x.add("hello ")
x.add("world!")
x.get_hash()

这将产生字符串“hello world”的散列，而不会在任何时间点将整个字符串保存在内存中。

特别是，imurmurhash-js javascript 包似乎在这个含义中使用了“增量”这个词。

MetroHash文档中似乎使用了相同的含义。