動機
雜湊表把龐大的鍵集合映射到較小的桶集合。當鍵的數目多於桶的數目時,任何映射都無法避免所有碰撞。然而,若鍵的集合是在抽取雜湊函數之前已經固定,一個精心挑選的隨機族便能令每一對特定鍵的碰撞機會變得很小。
我們利用質數域上的仿射映射來構造這樣的族。當桶的數目不能整除該質數時,由域元素化為桶編號的過程會令各桶的大小略有不均。證明會精確地計算這種不均衡。證明亦會說明,為何當對手看到所選取的雜湊函數之後,針對固定鍵的保證便不能原封不動地沿用。
定義
定義 5.2.1
(隨機仿射映射後接桶歸約)
固定質數 及整數 。鍵集合為 ,並與 等同。獨立地從 中均勻選取 ,並從 中均勻選取 。定義
其中第一個餘數以其在 內的整數表示。輸出為 內的一個桶。
由相異鍵組成的集合 是獨立於隨機種子 而固定的。在分析期望鏈長時,不成功查詢所用的查詢鍵同樣是獨立於該種子而固定的。所有概率陳述均是就所指明的種子隨機選取而言。
對於桶 j,設 為 中模 m 同餘於 j 的整數個數。當 時,部分桶可能是空的。由商與餘數可知,每個桶(不論是否為空)的大小不是 就是 。
定理/命題
定理 5.2.2
(通用碰撞界)
對於任意兩個相異的固定鍵 ,
此結論對每個 皆成立,包括 的情況。兩個鍵的桶輸出不一定互相獨立,亦不一定在全部 m 個桶上各自均勻分布。
定理 5.2.3
(期望碰撞數與鏈結法)
對於由 個相異鍵組成的固定集合 ,設 為發生碰撞的無序鍵對數目。則
對於固定的 ,其所在桶的期望佔用量至多為 。對於固定的查詢 ,其所在桶的期望佔用量至多為 。
證明思路
兩個相異的域像呈均勻分布
證明
(兩個相異鍵給出相異域像的均勻有序對)
對於固定的相異 ,考慮預先指定的相異域元素 。方程
在 中有唯一解 及 。兩個差皆不為零,故所得的 是被容許的。反之,由於乘以非零的 a 是單射,每個被容許的種子都給出相異的像。
共有 個等可能的種子,而相異有序對 的數目亦相同。因此 在這些對上呈均勻分布。特別地,每個個別的域像都是均勻的,但這一對並不獨立:兩個像永遠不會相等。質數域中的除法有效,是因為 ;對於任意的合數模,此構造不具備這個證明。
不均等的桶大小仍然給出所述的界
證明
(計算共同的桶)
以第一個域像為 u 作條件。第二個像在其餘 個元素中均勻分布。若 u 位於大小為 c 的桶內,則恰有 c−1 個選擇會與它碰撞,故條件碰撞概率為 。
每個桶的大小至多為 ,而且
因此對每個 u,條件概率至多為 。對 u 取平均即證得碰撞界。當 時,每個有元素的桶只含一個域元素,故碰撞概率實際上為零。當 時,界為一,而且每一對鍵都會碰撞。
證明透視
條件化所用的是相異的域像,而非獨立的桶
第一個域像固定後,第二個像在其餘 p−1 個域元素中變動。計算第一個像所在桶內的其他成員,即使各桶大小不同,亦可得出該界。桶輸出的獨立性既沒有被假設,亦不需要。
以指示變量計算鍵對
證明
(期望鍵對數目與桶佔用量)
對於 S 中每一對無序的相異鍵,使用一個僅在碰撞時等於一的指示變量。它們的總和即為 X。期望的線性性(不要求這些指示變量互相獨立)給出上面所示的期望。事件 由非負整數 X 的馬爾可夫(Markov)不等式涵蓋,而概率從不大於一。
對於固定的鍵 ,其所在桶的佔用量等於一加上 x 與其他每個鍵之間的碰撞指示變量。對於 S 以外的固定查詢,佔用量則是它與所有已儲存鍵之碰撞指示變量的總和。同一個鍵對界加上線性性,即給出這兩個佔用量估計。此論證包括 S 以外的查詢在 時的情況;當 S 為空集時,沒有可供選取的 S 內鍵。
概念視角組合
把碰撞概率看成有序對的計數
種子與相異域元素的有序對 一一對應。因此對任意兩個相異鍵,碰撞概率恰好等於這些有序對中落在同一桶的比例:
當 、 時,桶的大小為 ,得到 。界 來自把這個與種子無關的計數同最大可能的桶大小比較。
例題
例題 5.2.4
(一個具體的仿射表)
設 、、 及 。鍵 分別映射到桶 。恰有一對發生碰撞的無序鍵對,即鍵 1 與鍵 3。對於這個固定的四鍵集合,定理把所有種子上的期望鍵對數目界定為 ;此界是就種子取的平均值,並非宣稱這個特定種子有兩次碰撞。
例題 5.2.5
(桶多於域元素)
取 及 ,第二次取餘數時,每個域代表元都保持不變。每個被容許的仿射映射都是 的置換,故相異鍵永不碰撞。桶 5、6 及 7 為空。一般的上界 有效,但並不尖銳。
例題 5.2.6
(一個固定的不成功查詢)
設 ,某固定集合含有 個鍵,並使用 個桶。對於集合以外的任何固定查詢鍵,其所在桶內已儲存鍵的期望數目至多為二。因此,對不成功查詢進行簡單鏈掃描的期望鍵比較次數至多為二。部分種子仍可能產生較長的鏈;該期望並非對每個種子都成立的最壞情況界。
由碰撞界到隨機重試
為固定集合抽取種子後,把其鍵插入各桶,並檢查是否有任何桶含多於一個鍵。若沒有,則該映射在 S 上為單射。除了計算雜湊值及抽取種子的成本之外,此檢查可通過初始化 m 個計數器並掃描 n 個鍵,以 次桶操作完成。
對於 ,若 ,則碰撞概率至多為二分之一。每次失敗後,獨立地重新抽取一個新種子。首 t 次嘗試全部失敗的機會至多為 ,而期望嘗試次數至多為二:尾和公式給出 作為上界。對於 ,每個種子在 S 上本來就是單射。
這是一個成功條件可供檢查的構造,並非嘗試次數的確定性最壞情況界。它亦沒有說明使用 個桶的無碰撞表必然是最節省空間的選擇。若種子是以有限的公平位元預算抽取並可能中止,則該抽樣程序的影響需另行分析。
桶歸約之後依然存在相依性
取 及 ,桶零含有代表元 ,而桶一和桶二各含兩個代表元。對於相異的固定 x、y,兩個域像同時落在桶零的概率為
每個個別輸出為零的概率均為 ,其乘積為 ,而非 。因此在這個例子中,兩個桶輸出並不獨立,而且在三個桶上也不是均勻分布。儘管如此,它們的碰撞概率仍滿足已證明的上界。對任意固定鍵對的碰撞控制比「桶輸出獨立且均勻」的斷言為弱。
反之,若 a 是從整個 (包括零)中均勻選取,則相異鍵的兩個域像會是獨立的均勻域元素:同樣的兩個方程對每個有序對(包括相等的對)都恰有一個解。歸約之後,它們的桶輸出會互相獨立,但一般並非均勻。對於 ,所得的碰撞概率為 。因此,在這個歸約下,把零乘數包括在內會改變碰撞保證。
查詢成本與固定輸入條件
使用分離鏈結法時,對固定的 作成功搜尋,所比較的鍵數不會多於其所在桶的佔用量。對 S 以外的固定查詢作不成功搜尋,所比較的鍵數至多為該桶的佔用量。因此,除計算雜湊值本身之外,期望比較次數的界可由該定理得出。成功的掃描可能提早停止;對於這個上界,不需要對鏈內的次序作任何假設。
當集合或查詢是在看到種子之後才選取,這些期望並不會自動適用。舉一個具體的對比,設 及 。從七個鍵到三個桶的每個映射,都有某個桶至少含三個鍵。先看到所選雜湊函數的觀察者,可以在這樣的桶中挑選任意三個鍵。這三對鍵於是全部碰撞,故對於這種依賴種子的選取,X 恆為三。對 的固定集合定理,期望鍵對數目的上界則為一。兩者並無矛盾:該定理中的集合必須獨立於種子。
反例模式
期望碰撞數並不是個別種子的最壞情況
一個誘人的說法:固定的三鍵集合的期望碰撞鍵對數至多為一,所以我們挑選的任何三個鍵至多產生一對碰撞。當鍵是在種子之後才選取時,這並不成立。取 、、、,即在 上 。鍵 全部落入桶零,;而定理只對在種子之前已固定的集合給出 。馬爾可夫界同樣只控制固定集合出現至少一次碰撞的概率,它可以等於平凡界一,亦沒有說明每個種子都不產生碰撞。
計算範圍
此構造假設已提供質數 p,而且鍵以域元素表示;它並沒有證明尋找合適質數是不需成本的。它亦假設 與 按規定作均勻抽樣。當所表示的數值符合機器字模型時,簡單的機器字運算模型可把域運算及取餘數運算視為基本運算。若 p 與 m 以任意二進制編碼,則模乘法、除法及種子產生各有位元成本,必須另行計算。
只有相異的鍵才符合集合模型。同一個鍵的重複出現必定雜湊到同一處,應按多重度或另一約定下儲存的記錄來計算。碰撞保證所涉及的是相異的輸入鍵,而非同一個鍵的兩種表示偶然相等。
常見錯誤
常見錯誤
(把鍵對碰撞界讀成獨立均勻的輸出)
對 、 及兩個相異的固定鍵,兩個輸出同為桶零的概率是 ,但每個輸出為桶零的概率是 ,而 。兩個輸出既不獨立,在三個桶上亦不均勻,當 不能整除 時尤其如此。受到控制的只是碰撞概率,其上界為 。
常見錯誤
(讓乘數可以取零)
若容許 取遍 全部元素,兩個域像便成為獨立的均勻元素,碰撞概率為 。對 、,此值為 ,界 不再成立。排除 是證明的一部分。
常見錯誤
(把期望鏈長當作實際鏈長)
界 是對事先固定的查詢鍵就種子取的平均。取 、、 及集合以外的查詢鍵 ,查詢所在桶內已儲存鍵數的期望至多為 ;但種子 、 把兩個已儲存的鍵都放進查詢鍵所在的桶,掃描便要與兩個鍵比較。
總結
非零的仿射乘數把兩個相異的固定鍵映射到相異域元素的均勻有序對。計算它們可能共同的餘數桶,即可證明碰撞概率至多為 ,即使各桶大小不均亦然。線性性給出期望鍵對數目及鏈佔用量;一次檢查加上獨立重試,便得到期望嘗試次數受控的固定集合無碰撞構造。每個這類概率陳述都取決於種子及鍵的選取模型。
練習
快速檢查
(對於 ,列出鍵 0、1、2 及 3 所在的桶,並計算發生碰撞的鍵對數目。)
解答 · 答案
輸出為 。鍵 0 與鍵 2 構成一對碰撞,鍵 1 與鍵 3 構成另一對碰撞,故共有兩對。
快速檢查
(若 及 ,該定理對至少發生一次碰撞的概率給出甚麼上界?)
解答 · 答案
該界為 。
快速檢查
(為何不需假設碰撞事件互相獨立,也可以把期望碰撞鍵對數目界定為各鍵對概率之和?)
解答 · 答案
鍵對碰撞數是有限個碰撞指示變量之和。不論各指示變量之間是否相依,期望的線性性都成立。
快速檢查
(對於 ,每個桶內各有多少個域代表元?)
解答 · 答案
代表元為 、 及 ,故大小分別為 3、2 及 2。