ハッシュ関数が増分であることは何を意味しますか？

Question

私は、MurmurHash2は "インクリメンタル"ではないが、MurmurHash3はインクリメンタルであると聞いています。これは何を意味するのでしょうか？それはなぜ有用なのですか？以前 ハッシュ化されたメッセージならば、Mは少し新しいメッセージに更新される状況に適し

Answer 1

インクリメンタルハッシュ関数は、M *は、それ は、更新され メッセージのハッシュ値を計算するために、かなり迅速にする必要がありますM *。これは、新しいハッシュm *をゼロから再計算しなければならない従来のハッシュ関数とは対照的に、古い ハッシュ値mから新しいハッシュm *を計算することによって行われ、これはより長い時間を要する。

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

彼らは、それらが力と計算時間の面で計算しやすいので、あまり高価だという事実に便利です。

しかし、すべての状況に適しているわけではありません。 Berkeleyのこの論文には、「はじめに」のセクションで役に立つと思われる例がいくつかあります。

Answer 2

私はこれに関する専門家ではありませんが、私はMurmurHash3がtommarshallの意味でインクリメンタルではないと思います。

人々は、彼らはおそらくあなたがO（1）メモリにストリームのハッシュを計算することができることを意味し、増分としてそれを説明し、あなたが（擬似コードで）次の手順を実行してみましょうAPI持つことができます。すなわち：

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

を

これは、文字列 "hello world"のハッシュを生成しますが、その時点では文字列全体をメモリに保持しません。

特に、imurmurhash-jsのjavascriptパッケージでは、その意味で「インクリメンタル」という単語が使用されているようです。

MetroHash文書でも同じ意味が使われているようです。