動機
隨機化數據結構常常假設不同的鍵以很小的概率發生碰撞。除非能夠構造出合適的雜湊族並弄清其抽樣成本,否則基於這一假設的分析是不完整的。在二元向量上的一個簡單仿射構造,只需一個有限的隨機種子,就能給出均勻分佈且兩兩獨立的雜湊值。
兩兩獨立弱於所有雜湊值的完全獨立,但對許多期望碰撞數的計算已經足夠。我們證明該雜湊族的性質,將其應用於雜湊表和碰撞聯集界,並說明固定輸入這一假設在何處起作用。
定義
設鍵的全集為 ,桶的集合為 ,其中整數 。運算在二元體 上進行。取一個均勻隨機的二元 矩陣 ,以及與之獨立的均勻隨機向量 。定義
種子由 個相互獨立的公平位元組成。一個桶就是一個 位元向量,因此共有 個可能的桶。
若對任意不同的鍵 以及任意輸出 都有
則稱該雜湊族具有兩兩獨立的均勻輸出。
這蘊含每個輸出都是均勻的,且碰撞概率為 。它並不聲稱三個或更多輸出之間聯合獨立。
定理
定理 10.1.1
(仿射二元雜湊族)
對於不同的二元鍵,雜湊族 具有兩兩獨立的均勻輸出。它使用 個公平種子位元,並且透過直接做矩陣乘法,可以用 次基本位元運算完成求值。
定理 10.1.2
(固定鍵集中的期望碰撞數)
對於與隨機雜湊函數獨立選取的、由 個不同鍵組成的任意固定集合,與指定鍵碰撞的其他鍵的期望個數為 。集合中存在任意一對鍵發生碰撞的概率至多為 。
證明:矩陣的一行
證明
(仿射雜湊族的兩兩獨立性)
固定不同的 ,並令 。由於 ,存在某個座標 等於 1。對於 的一個均勻隨機行向量 ,點積 是一個公平位元:固定 的其餘所有座標後,翻轉 就會翻轉該點積。因此
是一個均勻的 位元向量,這是因為矩陣的各行相互獨立。
偏移量 是均勻的,並且與 獨立。在任意給定 的條件下, 是均勻的。於是,對任意指定的 ,先要求 ,其概率為 ;再要求 ,其條件概率為 。聯合概率為 。
對 個相等的輸出對 的聯合概率求和,得到碰撞概率 。偏移量還使每個單獨的輸出都是均勻的,對零鍵也是如此。
證明透視
偏移量提供均勻的取值
各假設用在哪裏: 恰好只用一次,用來找出使 的座標 ;沒有它, 為零,兩個鍵必定碰撞。關鍵一步是把輸出對拆成兩部分:差 ,由隨機矩陣使之均勻;位置 ,由獨立的偏移使之均勻。 的各行相互獨立,使 的 個位元相互獨立; 與 獨立,使兩個因子 可以相乘。論證只涉及一對 ,所以只證明了兩兩獨立,並不涉及三個鍵;反例中的四鍵關係說明更強的結論並不成立。
證明:固定集合的碰撞界
證明
(期望碰撞數與聯集界)
對於由 個不同鍵組成的固定集合 中的一個固定鍵 ,令 表示 與 是否碰撞的指示變量。發生碰撞的其他鍵的個數為 。每個指示變量的期望都是 ,因此由線性性得期望為 。這些指示變量不必相互獨立。
對於任意一對不同鍵(無序對),碰撞概率為 。共有 對。由聯集界,至少有一對發生碰撞的概率至多為 。若該量超過 1,不等式依然成立,但不能給出有用的概率估計。
集合和查詢都是獨立於雜湊種子而固定的。如果對手在看到所選雜湊函數之後,再選取專門設計成發生碰撞的鍵,那麼在沒有進一步分析的情況下,就不能套用同樣的固定集合概率陳述。
例題詳解
例題 10.1.3
(一個輸出位元)
對於 ,設隨機行為 ,偏移量為 。對於鍵 和 ,輸出分別為 和 。它們恰在 時碰撞,概率為 。
例題 10.1.4
(期望鏈長)
對於由 個鍵組成的固定集合,用任何具有相同碰撞界的雜湊族將其雜湊到 個桶中,一個指定的已儲存鍵與之碰撞的其他鍵的期望個數至多為 。這裏的二元構造本身的寬度是 2 的冪,所以這個數值例子說明的是碰撞定理,而不是聲稱它使用了滿足 的 。
例題 10.1.5
(聯集界可能是鬆的)
對於 和 ,至少發生一次碰撞的聯集界為 。它不一定等於真實的碰撞概率,因為不同鍵對的碰撞事件可能重疊。
例題 10.1.6
(零鍵仍然有隨機輸出)
沒有偏移量時,對每個矩陣都有 。有了獨立的偏移量, 在各個桶上是均勻的。偏移量對於單個鍵輸出的均勻性是必不可少的。
常見錯誤
反例模式
兩兩獨立不等於完全獨立
對於四個兩位元鍵 以及任意仿射二元雜湊函數,它們的輸出之和為零:矩陣項和偏移量各出現偶數次。因此這四個輸出滿足一個確定性關係,它們並非聯合均勻的,儘管其中任意兩個不同的輸出是兩兩獨立的。
常見錯誤
(期望很小不代表每個種子都好)
期望碰撞數並不保證每個種子下鏈都很短。有些被抽到的函數可能產生大量碰撞;例如 會把每個鍵都映射到 。高概率界需要額外的論證,並且可能弱於完全隨機性所能給出的斷言。
常見錯誤
(計算時間不等於種子大小)
表達式 計的是直接求值時的基本位元運算次數。機器字實現對某些維度可能求值更快,而儲存種子仍需 個位元。該定理並不保證存在與鍵長無關的常數大小種子。
概念視角代數
兩兩獨立就是線性映射的滿射性
種子 在 上均勻分佈,而 是映到 的 線性映射。當 時它是滿射,因為 與 可以各自獨立地指定;均勻的輸入經過滿射的線性映射,輸出仍然均勻。對四個鍵 ,像落在輸出之和為零的子空間內,所以那個映射不是滿射。
應用:鏈地址法
將每個鍵存入其雜湊桶對應的鏈表中。對於一個固定的已儲存查詢鍵 ,直接掃描所檢查的條目數至多為 1 加上同一桶中其他已儲存鍵的個數。因此,除去計算雜湊和比較鍵的開銷外,其期望至多為 。
對於不在已儲存集合中的固定查詢 ,其所在桶中已儲存鍵的期望個數為 ,所以一次不成功的掃描在期望意義下檢查這麼多個鍵。這些陳述都假設已儲存集合和查詢是在隨機選取種子之前固定的。它們統計的是鏈表條目數;比較兩個 位元鍵以及計算雜湊各有其自身的成本。
若 與 相當,則被檢查的鏈表條目的期望個數為常數。這是對固定輸入在雜湊種子上的平均,而不是對每個桶長度的最壞情形界。碰撞聯集界在另一個方向上更強:它控制是否有任何一對鍵發生碰撞,但要使其很小,可能需要大得多的 。
適應性選擇可以強制產生碰撞
設 ,且對手看到了抽樣得到的矩陣 。線性映射 存在非零的核向量 ,因為從 維二元向量空間到 維二元向量空間的映射不可能是單射。對手可以選取 和 。於是
必然成立。這並不與定理矛盾:鍵 是在看到 之後選取的,所以這一對鍵並非獨立於種子而固定。對於固定的非零 ,在全新的隨機矩陣上 的概率仍然是 。
這個例子也說明,公開的雜湊種子加上適應性對手,需要超出初等固定鍵分析的模型。視應用而定,可能需要秘密隨機性、定期重建、更強的假設或不同的數據結構。僅憑兩兩獨立性,得不到任何這樣的適應性保證。
從期望到尾界
令 為與某個固定已儲存查詢碰撞的其他已儲存鍵的個數。由於 ,馬爾可夫(Markov)不等式對任意整數 給出
這由 以及期望碰撞數公式得到。該界可能是鬆的,但不需要假設碰撞指示變量相互獨立即可成立。特別地,鏈長期望為常數並不意味著出現很長的鏈的概率為零。
對於整個固定集合,由同樣的指示變量論證,發生碰撞的無序對的期望個數為 。若該期望小於 1,則至少存在一個沒有任何碰撞的種子:否則每個種子都至少有一對碰撞,期望就至少為 1。這證明的是存在性,而不是找到這樣一個種子的高效確定性方法。窮舉檢驗全部 個種子的成本可能高得無法承受。
有限種子如何使用
矩陣含有 個位元,偏移量再含 個位元。獨立且均勻地抽取所有這些位元,就確定了該雜湊族中的一個函數。隨後,同一個抽到的函數被用於該雜湊表或該草圖行中的所有鍵。對每次查找都重新抽取新的函數,通常會改變桶的分配,也就無法維持所描述的數據結構。
要計算一個輸出位元,把矩陣的相應行與輸入向量在 上相乘,再加上相應的偏移量位元。每行直接求值至多使用 次位元乘法和加法,因此全部 個輸出位元共需 次基本位元運算。這一計數假設矩陣和鍵都是顯式給出的。軟件實現可以把位元打包進機器字,但其實際的字運算界取決於機器模型和字長。
獨立的草圖行可以透過為每一行獨立抽取種子得到。同一行內的輸出具有上面證明的兩兩性質;不同行的輸出因種子獨立而相互獨立。這一區別在 Count–Min 的分析中很有用:線性性處理同一行內的碰撞,而行與行之間的獨立性則放大了至少有一行雜訊較小的概率。
四個鍵的相關性可以逐座標驗證。把 上的輸出寫成 、、 和 ,其中 是 的兩列。它們在 上的和為零。若四個輸出是完全獨立的均勻 位元向量,則這一等式只以概率 成立,而不是必然成立。因此,兩兩獨立性不能推廣到這個四鍵集合。
碰撞聯集界有時被稱為生日式估計:儘管每一次單獨碰撞的概率只有 ,但鍵對的數目是二次的。例如,要使所示的界至多為 ,需要 。相比之下,要使與某個固定鍵碰撞的期望次數低於某個常數,只需 與 成正比。這是兩種不同的保證,不應互相替換。如果鍵對的界超過 1,把它換成 1 給出的是一個有效但平凡的概率上界;這並不意味著概率本身超過 1。只有當該界的數值小於這一平凡極限、從而提供資訊時,它才有用。
總結
隨機二元矩陣加偏移量,用一個顯式的有限種子產生均勻且兩兩獨立的雜湊輸出。對固定鍵集,兩兩碰撞概率給出期望鏈長和聯集界,而不要求所有鍵之間完全獨立。
練習
快速檢查
(當 時,共有多少個桶?兩個固定的不同鍵的碰撞概率是多少?)
桶的個數是 。
解答 · 答案
共有 個桶,碰撞概率為 。
快速檢查
(為甚麼在二元向量上,當 時 非零?)
在 上, 意味著甚麼?
解答 · 答案
在 上,若 則 。因此不同的鍵至少在一個座標上不同,它們的和在該座標上為 1。
快速檢查
(對於 個已儲存鍵和 個桶,與某個固定已儲存鍵碰撞的其他鍵的期望個數是多少?)
把其他鍵的碰撞指示變量相加。
解答 · 答案
在所述的兩兩均勻雜湊族下,它是 。
快速檢查
(為甚麼期望碰撞數的證明不需要碰撞指示變量相互獨立?)
期望對任何有限和都成立的是哪個性質?
解答 · 答案
期望對有限和總是可以分配,與是否相依無關。對每個其他鍵,只需其各自的碰撞概率即可。