Ich habe gehört, dass zum Beispiel MurmurHash2 nicht "inkrementell" ist, sondern MurmurHash3 inkrementell ist. Was bedeutet das? Und warum ist es nützlich?Was bedeutet es für eine Hash-Funktion, inkrementell zu sein?
Incremental-Hash-Funktionen für Situationen geeignet, bei denen, wenn eine zuvor gehashte Nachricht, M leicht in eine neue Nachricht aktualisiert wird, M *, dann ist es sollten ziemlich schnell sein, den Hash-Wert der aktualisierten Nachricht zu berechnen, M *. Dies geschieht durch die Berechnung des neuen Hashs m * aus dem alten Hash-Wert, m, im Gegensatz zu herkömmlichen Hash-Funktionen, die den neuen Hash m * von Grund auf neu berechnen müssen, was eine längere Zeit in Anspruch nimmt.
http://www.cs.berkeley.edu/~daw/papers/inchash-cs06.pdf
Sie nützlich sind aufgrund der Tatsache, dass sie leichter zu berechnen und daher weniger teuer in Bezug auf Leistung und Rechenzeit.
Sie sind jedoch nicht für jede Situation geeignet. Dieses Dokument aus Berkeley hat einige schöne Beispiele, wann sie im Einführungsteil nützlich sein können.
Ich bin kein Experte auf diesem, aber ich denke, MurmurHash3 ist nicht inkrementell in dem Sinne, wie Tommarshall beschreibt.
Wenn die Leute beschreiben es als inkrementelle sie wahrscheinlich bedeuten, dass Sie Hash eines Stroms in O berechnen kann (1) Speicher, dh Sie eine API haben können, dass Sie lassen Sie wie folgt (in Pseudo-Code):
x = Hasher()
x.add("hello ")
x.add("world!")
x.get_hash()
und das würde einen Hash der Zeichenfolge "Hallo Welt" erzeugen, ohne die ganze Zeichenfolge zu irgendeinem Zeitpunkt im Speicher zu halten.
Insbesondere das imurmurhash-js JavaScript-Paket scheint das Wort 'inkremental' in dieser Bedeutung zu verwenden.
Gleiche Bedeutung scheint in MetroHash Docs verwendet werden.
Vielleicht sollte es "Stream Hashing" genannt werden. – CMCDragonkai
Danke! Virus Beispiel ist großartig (aus Papier). –
Ich bin durch diese Antwort verwirrt. Die Frage fragt genau, in welchem Sinne MurmurHash3 inkrementell ist, aber ich denke nicht, dass es in dem in der Antwort beschriebenen Sinne inkrementell ist. Vielleicht sehe ich nur nicht wie. – Rotsor