功能散列/雪崩效應

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

雪崩效應確保輸入中的微小變化（例如：雲對雲）會在輸出中產生很大的變化，也就是說，接近的輸入值會產生遙遠且不可預知的輸出值。