hash - ハッシュ関数がインクリメンタルであるとはどういう意味ですか?

Question

たとえば、MurmurHash2 は「インクリメンタル」ではなく、MurmurHash3 はインクリメンタルであると聞いたことがあります。これは何を意味するのでしょうか？そして、なぜそれが役立つのですか？

Answer 1

以前にハッシュされたメッセージ M が新しいメッセージ M* にわずかに更新された場合、更新されたメッセージ M* のハッシュ値をかなり迅速に計算する状況に適した増分ハッシュ関数。これは、古いハッシュ値 m から新しいハッシュ m* を計算することによって行われます。従来のハッシュ関数は、新しいハッシュ m* をゼロから再計算する必要があり、時間がかかります。

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

これらは、計算が簡単で、計算能力と時間の点で安価であるため、便利です。

ただし、すべての状況に適しているわけではありません。Berkeley の論文には、導入セクションで役立つ場合の良い例がいくつかあります。