Что означает, что хеш-функция должна быть инкрементальной?

Ответ 1

Инкрементные хэш-функции, подходящие для ситуаций, когда если ранее hashed message, M слегка обновляется в новое сообщение, M *, затем оно должен быть достаточно быстрым для вычисления хэш-значения обновленного сообщение, M *. Это делается путем вычисления нового хэша, m *, из старого хэш-значение, м, в отличие от обычных хеш-функций, которые должны пересчитайте новый хэш, m * с нуля, что занимает больше времени.

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

Они полезны из-за того, что их легче вычислить и, следовательно, дешевле с точки зрения вычислительной мощности и времени.

Однако они не подходят для каждой ситуации. В этой статье из Беркли есть несколько хороших примеров того, когда они могут быть полезны в разделе "Введение".

Ответ 2

Я не эксперт в этом, но я думаю, что MurmurHash3 не является инкрементным в том смысле, который описывает tommarshall.

Когда люди описывают это как инкрементное, они, вероятно, означают, что вы можете вычислить хэш потока в O (1) памяти, то есть вы можете иметь API, который позволяет делать следующее (в псевдокоде):

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

и это создаст хэш строки "hello world", не сохраняя всю строку в памяти в любой момент времени.

В частности, пакет javacript imurmurhash-js, по-видимому, использует слово "incremental" в этом значении.

То же самое значение, по-видимому, используется в MetroHash docs.