為什麼所有函式的hashfamily都有{h∈H0|小時：U→V}{H∈H0|H:在→在}{h in H_0 | h:U rightarrow V}滿足通用雜湊？
我在我們關於散列的大學講座中讀到，如果我們可以從 $ U \rightarrow V $ 滿足以下通用散列條件：對於所有 $ \forall x,y\in U $ 以便 $ x≠y $ ， 我們有 $ Pr[h(x)=h(y)]≤\frac{1}{|V|} $
我實際上不明白為什麼所有功能的集合都會滿足我們的條件。我可以明確地看到有一些函式符合這個條件，但我可以想到其他不符合條件的函式。所以我必須對所有函式集的平均機率做出一個陳述，但是如何精確定義這樣的事情呢？
或者我在這裡做錯了什麼，所有函式的集合都不滿足條件，但實際上比條件更好，條件是 h 是從 H 中隨機抽取的？即使是這樣，它似乎也歸結為同樣的問題。
首先註意所有函式的集合 $ U\to V $ 包含每個值 $ u\in U $ 和每一個價值 $ v\in V $ 一個函式 $ f $ 這樣 $ f(u)=v $ . 另請注意，如果您確定一個點 $ u\in U $ 並從 $ U\to V $ , $ f(u) $ 均勻分佈在 $ V $ .
現在，如果您應用它，請修復任意兩點 $ x\neq y,\quad x,y\in U $ . 現在選擇 $ h $ 隨機出 $ U\to V $ . 注意 $ h(x) $ 是均勻分佈的並且 $ h(y) $ 是均勻分佈的。機率為 $ h(x) $ 和 $ h(y) $ 現在應該是平等的 $ 1/|V| $ 這意味著所需的普遍性。
鑑於上述內容可能並不完全清楚，讓我們舉個例子： $$ U={1,2,3}\quad V={1,2,3} $$ 顯然有 27 個函式映射來自 $ U $ 至 $ V $ 顯然有 6 對不相等的值 $ (x,y)\in U\times U $ 我們需要檢查機率是否成立。
$ (x,y)=(1,2): $ 有三種可能的映射方式 $ 1 $ : 到 1,2 或 3，讓我們表示實際值 $ h(x) $ 暫時。還可以映射三個可能的值 $ 2 $ to: 1,2 或 3，讓我們將實際值表示為 $ h(y) $ . 鑑於這兩個選擇是獨立的，這裡有 9 個案例。
- 如果 $ h(x)=1 $ 那麼被測方程僅在以下情況下成立 $ h(y)=1 $ 也是1/3的機會
- 如果 $ h(x)=2 $ 然後與 for 相同的論點 $ h(x)=1 $ 適用於 $ h(y)=2 $
- $ h(x)=3 $ 類似地
現在計算等式成立的情況 $ (x,y)=(1,2) $ 我們得到 $ 3/9\leq 1/3 $ 按要求。
如果我們也檢查其他對，則會出現非常相似的論點，我們將得到 $ 3/9 $ 為他們所有人。因此一個隨機函式來自 $ U $ 至 $ V $ 滿足普遍性。