我遇到了計算機科學課程中的一個示例。鏈接散列並使用大小爲'm`的表格
假設我們使用鏈接哈希並使用大小爲m
的表。帶密鑰k
的哈希函數映射記錄到k mod m
時隙。如果我們知道記錄密鑰是{i^2 | 1 <= i <= 100}
的子集,那麼在最壞情況下搜索的代價是哪個值的m
?
一)11
B)7
C)9
d)12
我的TA說(1)爲真,但我薄這是假的。事實上我不知道我們如何得到這個!任何想法?
我遇到了計算機科學課程中的一個示例。鏈接散列並使用大小爲'm`的表格
假設我們使用鏈接哈希並使用大小爲m
的表。帶密鑰k
的哈希函數映射記錄到k mod m
時隙。如果我們知道記錄密鑰是{i^2 | 1 <= i <= 100}
的子集,那麼在最壞情況下搜索的代價是哪個值的m
?
一)11
B)7
C)9
d)12
我的TA說(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
m=1
(所有元素都在一個會發生什麼列表)或m=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中。在最壞的情況下,更均勻的傳播會降低搜索成本。
哇,@amit,你是如此聰明,好主意。但我怎麼能用理論的方式來證明呢? – 2015-02-24 13:35:13
@AliMovagher我同意鏈接問題的最佳答案並不嚴謹。這裏的考慮歸結爲數論。 Mod是一個奇素數m = p,對於所有二次餘數,除0之外,漸近分佈爲2/m,對於0,1/m的漸近分佈,而在非殘餘桶中則不存在。模數m = p^2是不好的,因爲p的所有倍數落在0桶中,小數部分爲1/sqrt(m)。同上的權力和倍數。 Squarefree複合材料是可以的,但由於這個評論框太小而無法形容,所以比素數差一些。 – 2015-02-24 15:39:47
@DavidEisenstat,我喜歡理論學習:)請問您提交答案嗎?事實上,我想學習更正式:) – 2015-02-24 15:42:17