Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What does it mean for a hash function to be incremental?

Tags:

hashtable

hash

I have heard that, for example, MurmurHash2 is not "incremental" but MurmurHash3 is incremental. What does this mean? And why is it useful?

like image 724
Palace Chan Avatar asked Sep 07 '12 20:09

Palace Chan


People also ask

What is incremental hash?

In a nutshell, the idea of incremental hashing is that if we have already computed the hash value of some document, and this document is modified in one part, then instead of re-computing the hash value of the whole document from scratch, we just need to update the hash value, performing computations only on the ...

How do you know if a hash function is good?

There are four main characteristics of a good hash function: 1) The hash value is fully determined by the data being hashed. 2) The hash function uses all the input data. 3) The hash function "uniformly" distributes the data across the entire set of possible hash values.

What are the 3 main properties of hash function?

One of the hardest concepts my students had grasping was secure cryptographic hash functions, partially because of the number theory, but also in differentiating between the three properties of a secure hash function: collision resistance, preimage resistance, and second preimage resistance.


2 Answers

Incremental hash functions suited for situations where if a previously hashed message, M is slightly updated into a new message, M*, then it should be fairly quick to compute the hash value of the updated message, M*. This is done by computing the new hash, m*, from the old hash value, m, in contrast to conventional hash functions that have to recompute the new hash, m* from scratch, which takes a longer time.

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

They're useful due to the fact that they're easier to compute and therefore less expensive in terms of computing power and time.

However they're not suited to every situation. That paper from Berkeley has some nice examples of when they can be useful in the Introduction section.

like image 138
tommarshall Avatar answered Oct 15 '22 18:10

tommarshall


I'm not an expert on this, but I think MurmurHash3 is not incremental in the sense tommarshall describes.

When people describe it as incremental they probably mean that you can compute hash of a stream in O(1) memory, i.e. you can have an API that let you do the following (in pseudocode):

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

and that would produce a hash of string "hello world" without keeping the whole string in memory at any point in time.

In particular, the imurmurhash-js javascript package seems to use the word 'incremental' in that meaning.

Same meaning seems to be used in MetroHash docs.

like image 32
Rotsor Avatar answered Oct 15 '22 17:10

Rotsor