鏈接散列並使用大小爲'm`的表格

Question

我遇到了計算機科學課程中的一個示例。

假設我們使用鏈接哈希並使用大小爲m的表。帶密鑰k的哈希函數映射記錄到k mod m時隙。如果我們知道記錄密鑰是{i^2 | 1 <= i <= 100}的子集，那麼在最壞情況下搜索的代價是哪個值的m？

一）11

B）7

C）9

d）12

我的TA說（1）爲真，但我薄這是假的。事實上我不知道我們如何得到這個！任何想法？

Answer 1

可以憑經驗用一個簡單的代碼檢查：

int[] mVals = {11, 7, 9, 12}; 
    for (int m : mVals) { 
     int[] cells = new int[m]; 
     for (int i = 1; i<= 100; i++) { 
      int x = i*i % m; 
      cells[x]++; 
     } 
     System.out.println("m=" + m + " cells=" + Arrays.toString(cells)); 
    } 

將產生：

m=11 cells=[9, 19, 0, 18, 18, 18, 0, 0, 0, 18, 0] 
m=7 cells=[14, 29, 28, 0, 29, 0, 0] 
m=9 cells=[33, 23, 0, 0, 22, 0, 0, 22, 0] 
m=12 cells=[16, 33, 0, 0, 34, 0, 0, 0, 0, 17, 0, 0] 

因爲你的價值觀是在指定的範圍內，你可以看到，在「最壞的」細胞對於要插入的元素，m = 11表的概率爲19/100，而對於m的所有其他值，最高概率更高。

---

至於爲什麼，有幾個因素在眼前：

的 m
1. 較大的值通常是首選 - 瞭解它，請確保您瞭解當m=1（所有元素都在一個會發生什麼列表）或m=2（兩個列表中的每個列表中的元素的一半）
2. 素數是首選，對散列函數「表現更好」。本主題在線程Why should hash functions use a prime number modulus?中進行了深入討論。這個想法是素數不易受特定元素域的偏見影響，您的一組平方數就是這樣一個例子。

Answer 2

作爲一般的經驗法則，您通常需要一個大的素數在散列模中進行模運算，因爲它會生成更多不同的值，並且這些散列值會導致散列表中各個槽的分佈更均勻。由於11是列表中最大的素數，直觀地說這將是最好的。

爲了您的具體問題，我們有記錄：

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, ..., 10000 

我們必須找到，您的每個選項，從這個系列中的許多不同值的數字如何生成模的變種。

對於11：

if n mod 11 = 0 => n*n mod 11 = 0 
if n mod 11 = 1 => n*n mod 11 = 1 (1) 
if n mod 11 = 2 => n*n mod 11 = 4 (2) 
      = 3    = 9 (3) 
      = 4    = 5 (4) 
      = 5    = 3 (5) 
      = 6    = 3 
      = 7    = 5 
      = 8    = 9 
      = 9    = 4 
      = 10    = 1 

對於7：

if n mod 7 = 0 => n*n mod 7 = 0 (1) 
      = 1    = 1 (2) 
      = 2    = 4 (3) 
      = 3    = 2 (4) 
      = 4    = 2 
      = 5    = 4 
      = 6    = 1 

對於9：

if n mod 9 = 0 => n*n mod 9 = 0 (1) 
      = 1    = 1 (2) 
      = 2    = 4 (3) 
      = 3    = 0 
      = 4    = 7 (4) 
      = 5    = 7 
      = 6    = 0 
      = 7    = 4 
      = 8    = 1 

類似地，對於12。正如你所看到的，11是爲方塊生成更多不同值的人，所以它會將你的值更均勻地散佈在你的哈希表的bin中。在最壞的情況下，更均勻的傳播會降低搜索成本。