第1章　散列

散列在概率數(shù)據(jù)結(jié)構(gòu)中扮演著核心角色，因?yàn)檫@些數(shù)據(jù)結(jié)構(gòu)使用散列對(duì)數(shù)據(jù)進(jìn)行隨機(jī)化和緊湊表示。散列函數(shù)通過生成體量更小（在大多數(shù)情況下為固定大小）的標(biāo)識(shí)符來壓縮任意大小的輸入數(shù)據(jù)塊。生成的標(biāo)識(shí)符又被稱為散列值，或簡(jiǎn)稱為散列。

散列函數(shù)的選擇對(duì)于避免偏差至關(guān)重要。盡管對(duì)于散列函數(shù)的選擇主要基于輸入和特定用例，但為了方便選擇，散列函數(shù)應(yīng)該滿足某些通用屬性。

散列函數(shù)會(huì)壓縮輸入。因此，兩個(gè)不同的數(shù)據(jù)塊具有相同散列值的情況是不可避免的。這種現(xiàn)象又稱為散列碰撞。

1979年，J.Lawrence Carter和Mark Wegman提出全域散列函數(shù)，即使輸入數(shù)據(jù)是從全域中隨機(jī)選擇的，其數(shù)學(xué)特性仍可以保證散列值的期望碰撞次數(shù)很少。

全域散列函數(shù)族H將全域中的元素映射到范圍{0,…,m-1}中，并通過從函數(shù)族中隨機(jī)挑選散列函數(shù)的方式保證發(fā)生散列碰撞的概率是有界的：

因此，從滿足性質(zhì)(1-1)的函數(shù)族中隨機(jī)選擇一個(gè)散列函數(shù)完全等價(jià)于均勻隨機(jī)地選擇一個(gè)元素。

一個(gè)被用于整數(shù)散列的重要的全域散列函數(shù)族被定義為：

其中k和q是隨機(jī)生成的模p的整數(shù)，且k≠0。p是一個(gè)素?cái)?shù)且p≥m。通常情況下，p可從已知的梅森素?cái)?shù)中進(jìn)行選擇。例如，若m=109，則我們選擇p=M31=231-1≈2·109。

許多應(yīng)用也使用函數(shù)族(1-2)的簡(jiǎn)化版本：

盡管函數(shù)族(1-3)僅僅具備近似全域性質(zhì)，但其期望的散列碰撞概率仍然小于2/m。

然而，上述所有的散列函數(shù)族僅適用于整數(shù)散列。這對(duì)許多需要對(duì)變長(zhǎng)的向量進(jìn)行散列，且需要既能滿足特定屬性又快速可靠的散列函數(shù)的實(shí)際應(yīng)用來說是不夠的。

在實(shí)際應(yīng)用中有許多種類的散列函數(shù)，其選擇主要取決于它們的設(shè)計(jì)和特定應(yīng)用場(chǎng)景。在本章中，我們對(duì)常用的散列函數(shù)和各種概率數(shù)據(jù)結(jié)構(gòu)中普遍存在的簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)進(jìn)行概述。