15

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

2 Answers 2

10

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.

2
  • Thanks! Virus example is great (from paper). Commented Sep 7, 2012 at 21:46
  • 1
    I am confused by this answer. The question asks specifically in what sense MurmurHash3 is incremental, but I don't think it's incremental in the sense described in the answer. Perhaps I'm just not seeing how.
    – Rotsor
    Commented Mar 31, 2016 at 22:36
4

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.

1
  • 3
    Perhaps it should be called "stream hashing". Commented Jan 25, 2017 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.