1. 問題
問題同《簡單散列函數(shù)算法》，這個例子并不是特別恰當(dāng)，當(dāng)在于簡單，數(shù)字小，方便驗(yàn)證，方便理解，特別是計算概率的部分。
設(shè)有10個非負(fù)整數(shù)，用不多于20個的儲存單元來存放，如何存放這10個數(shù)，使得搜索其中的某一個數(shù)時，在儲存單元中查找的次數(shù)最少？
問題類似于，有10個帶號碼的球，放到編號為{0, 1, 2, …, 19}共20個盒子中，每個盒子最多放一個，問如何放，使能夠用最少的次數(shù)打開盒子，知道任一個球所在的盒子編號？
2. 分析
《散列函數(shù)之單散列算法解決沖突問題》中，我們提到用單散列算法來解決沖突，比簡單散列算法沖突的比率有所降低，但18%的沖突率，對于實(shí)際應(yīng)用來說還是略偏高，《初等數(shù)論及其應(yīng)用》中，說明是從另一個角度來說明該沖突率高的原因。
設(shè) h0(k) ≡ k (mod m), k = 球號， m = 盒子數(shù)量
hj(k) ≡ h0(k) + j，0<= j < m, hj(k) 表示發(fā)生 j 次沖突后，球所放入的盒子編號
