¿Qué significa que una función hash sea incremental?

Question

He oído que, por ejemplo, MurmurHash2 no es "incremental", pero MurmurHash3 es incremental. ¿Qué significa esto? ¿Y por qué es útil?

Answer 1

funciones hash incrementales adecuadas para situaciones en las que si un mensaje previamente hash, H está ligeramente modificada en un nuevo mensaje, M *, entonces debe ser bastante rápida para calcular el valor hash del mensaje actualizado , METRO*. Esto se hace calculando el nuevo hash, m *, del antiguo valor hash , m, en contraste con las funciones hash convencionales que tienen que volver a calcular el nuevo hash, m * desde cero, lo que lleva más tiempo.

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

son útiles debido al hecho de que son más fáciles de calcular y por lo tanto menos costoso en términos de potencia y tiempo de cálculo.

Sin embargo, no son adecuados para cada situación. Ese documento de Berkeley tiene algunos buenos ejemplos de cuándo pueden ser útiles en la sección Introducción.

Answer 2

No soy un experto en esto, pero creo que MurmurHash3 no es incremental en el sentido que describe tommarshall.

Cuando las personas lo describen como incrementales que probablemente significa que se puede calcular de hash de una corriente en O (1) de memoria, es decir, puede tener una API que le permiten hacer lo siguiente (en pseudocódigo):

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

y que produciría un hash de cadena "hello world" sin mantener todo el hilo en la memoria en cualquier momento.

En particular, el paquete imurmurhash-js javascript parece utilizar la palabra 'incremental' en ese sentido.

El mismo significado parece ser utilizado en MetroHash documentos.