Che cosa significa per una funzione hash essere incrementale?

Question

Ho sentito che, ad esempio, MurmurHash2 non è "incrementale" ma MurmurHash3 è incrementale. Cosa significa questo? E perché è utile?

Answer 1

funzioni hash incrementali adatti per le situazioni in cui, se un messaggio precedentemente hash, M è leggermente aggiornata in un nuovo messaggio, M *, allora dovrebbe essere abbastanza veloce per calcolare il valore hash del aggiornato messaggio, M *. Questo viene fatto calcolando il nuovo hash, m *, dal vecchio valore di hash , m, in contrasto con le convenzionali funzioni di hash che devono ricalcolare il nuovo hash, m * da zero, che richiede più tempo.

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

Sono utili a causa del fatto che sono più facili da calcolare e quindi meno costoso in termini di potenza e tempo di calcolo.

Tuttavia non sono adatti ad ogni situazione. Quel documento di Berkeley ha alcuni buoni esempi di quando possono essere utili nella sezione Introduzione.

Answer 2

Non sono un esperto in questo, ma penso che MurmurHash3 non sia incrementale nel senso descritto da tommarshall.

Quando la gente lo descrivono come incrementale che probabilmente significa che si può calcolare hash di un torrente in O (1) di memoria, cioè si può avere un'API che consentono di eseguire le seguenti operazioni (in pseudocodice):

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

e che produrrebbe un hash di stringa "ciao mondo" senza mantenere l'intera stringa in memoria in qualsiasi momento.

In particolare, il pacchetto javascript imurmurhash-js sembra utilizzare la parola "incremental" in questo senso.

Lo stesso significato sembra essere utilizzato nei documenti MetroHash.