全域雜湊是什麼意思？

1樓：

靈感是隨機地選雜湊函式。如果雜湊函式是隨機選擇的，那麼精心構造的資料就不一定起作用了。但是，

多少個備選函式才夠呢？比如，兩個是不夠的。比如我們有兩個雜湊函式 h1 和 h2 來隨機選擇，各 50% 概率被選到。

那麼構造乙個 h1 的特殊輸入（讓 h1 100% 衝突），這個輸入裡任意兩個元素仍然會有 50% 的情況一定衝突（就是 h1 被選中的概率），沒有達到理想的 1/m。

備選函式夠多就可以嗎？比如，這些函式都會在兩個特殊的點上面衝突，即存在 x != y，使得任取 h 都有 h(x) == h(y)，那麼用這兩個點作為輸入，衝突概率就是 100%。

也就是說，這些函式衝突的地方還不能太重合。

全域雜湊指出可以選擇 |H| 個雜湊函式，且它們最大重合 ≤ |H|/m。其中重合是指，對任意 x != y，雜湊函式集合 H 中 h(x) == h(y) 的雜湊函式個數。

隨機選擇雜湊函式後，對於精心構造的 x, y（我知道 x, y 會在某個或某些函式上衝突），能夠被這個 x, y 命中的雜湊函式個數就會 ≤ |H|/m，即命中概率 ≤ |H|/m / |H| = 1/m。也就是說，對於精心構造的輸入，衝突率重新達到了 1/m。

2樓：

由於數學功底太差，只能給出乙個對於全域雜湊的乙個感性認識。首先雜湊有乙個我們無法迴避的缺點，對於某個鍵集，它的鍵值是一樣的。那麼對於別有用心的資料，該雜湊函式的表現就是很差的，那麼我們如何盡量避免這種情況呢？

就像家源說的那樣，random就好呀，我們都不知道會在函式族裡撞到誰，那麼自然就會達到目的了。那麼對於它的定義，既然碰撞的概率不會超過1/m，那麼我們可以證明對於任意的x，它的碰撞次數的期望是嚴格小於裝載因子α的，實際上E(Cx)=(n-1)/m。而實際上題主有疑問的那句話。。。

恰好這就是全域雜湊的定義。

祝您越來越強。