Функция Hashing/Avalanche Effect

Question

Я немного читал о хэшировании функций для уменьшения размерности. Я понимаю, что важно использовать хеш-функцию, которая имеет равномерное распределение выходных данных (вероятность того, что ввод будет сопоставлен с определенным значением, совпадает с любым другим значением в диапазоне), а также эффект лавины/каскада (небольшой изменение ввода приводит к большому изменению выхода). Эти свойства гарантируют, что столкновения между функциями не будут зависеть от их частоты. Тем не менее, я все еще не понимаю, как эффект лавины (в частности) влияет на это. Может ли кто-нибудь объяснить, почему/как это имеет значение здесь? Что представляет собой «большое изменение» в продукции?

Ссылки: http://blog.someben.com/2013/01/hashing-lang/ http://metaoptimize.com/qa/questions/6943/what-is-the-hashing-trick#6945

Answer 1

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

«Большая перемена» предполагает, что ваша функция хэширования h должна показать, что h (a) - h (b) стохастически не зависит от (a-b).

Этого достаточно? Последуйте, если вам нужно больше объяснений.

Answer 2

Эффект лавины гарантирует, что незначительное изменение входного сигнала (например, слова: облако против облаков) приведет к большому изменению выходного сигнала, то есть близкие входные значения будут давать отдаленные и непредсказуемые выходные значения.