111年身心障礙人員三等資料結構
|
二、以下7個數字 [21, 1, 16, 11, 25, 9, 35]，要儲存到 Hash Table 中，Hash Table的儲存空間是一個索引從0開始的一維陣列 (Array)。假設 Hash 函數為 H(Key) = (Key*3) mod 7，裝填因子 (Load Factor) 為0.7。 (一)若處理 Hash Table 衝突的方法為開放定址法 (Open Addressing Hashing)中的線性探測法 (Linear Probing)：增量函數 F(i) = i (i 為衝突的次數)。請依序列出每存入一個數字後的 Hash Table 的內容。接著計算在相同機率的情況下，查找成功及查找失敗的平均查找長度 (Average Search Length; ASL)。（15分） (二)若處理 Hash Table 衝突的方法為開放定址法 (Open Addressing Hashing)中的平方探測法 (Quadratic Probing)：增量函數 F(i) = i2 (i 為衝突的次數)。請依序列出每存入一個數字後的 Hash Table 的內容。接著計算在相同機率的情況下，查找成功及查找失敗的平均查找長度 (Average Search Length; ASL)。（15分） |
答：
[21, 1, 16, 11, 25, 9, 35]
裝填因子 = 資料個數/總容量 = 0.7，表示有7筆資料，總容量10個。
(一)
1.Hash Table的內容：
H(Key) = (Key*3) mod 7
hi(Key) = (H(Key)+i) mod 7，i 是碰撞次數。
H(21) = (21*3) mod 7 = 63 mod 7 = 0
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
21 |
|
|
|
|
|
|
|
|
|
H(1) = (1*3) mod 7 = 3 mod 7 = 3
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
21 |
|
|
1 |
|
|
|
|
|
|
H(16) = (16*3) mod 7 = 48 mod 7 = 6
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
21 |
|
|
1 |
|
|
16 |
|
|
|
H(11) = (11*3) mod 7 = 33 mod 7 = 5
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
21 |
|
|
1 |
|
11 |
16 |
|
|
|
H(25) = (25*3) mod 7 = 75 mod 7 = 5，發生碰撞。
h1(25) = (5+1) mod 7 = 6 mod 7 = 6，發生碰撞。
h2(25) = (5+2) mod 7 = 7 mod 7 = 0，發生碰撞。
h3(25) = (5+3) mod 7 = 8 mod 7 = 1。
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
21 |
25 |
|
1 |
|
11 |
16 |
|
|
|
H(9) = (9*3) mod 7 = 27 mod 7 = 6，發生碰撞。
h1(9) = (6+1) mod 7 = 7 mod 7 = 0，發生碰撞。
h2(9) = (6+2) mod 7 = 8 mod 7 = 1，發生碰撞。
h3(9) = (6+3) mod 7 = 9 mod 7 = 2。
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
21 |
25 |
9 |
1 |
|
11 |
16 |
|
|
|
H(35) = (35*3) mod 7 = 105 mod 7 = 0，發生碰撞。
h1(35) = (0+1) mod 7 = 0 mod 7 = 1，發生碰撞。
h2(35) = (0+2) mod 7 = 2 mod 7 = 2，發生碰撞。
h3(35) = (0+3) mod 7 = 3 mod 7 = 3，發生碰撞。
h4(35) = (0+4) mod 7 = 4 mod 7 = 4。
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
21 |
25 |
9 |
1 |
35 |
11 |
16 |
|
|
|
2.查找成功及查找失敗的平均查找長度：
|
hash地址 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
Key |
21 |
25 |
9 |
1 |
35 |
11 |
16 |
|
|
|
|
比較次數 |
1 |
4 |
4 |
1 |
5 |
1 |
1 |
|
|
|
|
尋找空格次數 |
8 |
8 |
8 |
8 |
8 |
8 |
8 |
|
|
|
(1)查找成功的平均查找長度：
比較次數的加總 / 資料個數 = (1+4+4+1+5+1+1) / 7 = 17/7次。
(2)查找失敗的平均查找長度：
a.因為是 mod 7，所以尋找的 hash 地址是0~6。尋找到空格的次數就是失敗的次數。
b.尋找空格次數的加總 / 槽個數 = (8+7+6+5+4+3+2) / 7 = 35/7 = 5次。
※參考資料：
1.https://www.796t.com/content/1549944207.html
2.https://blog.csdn.net/butbabuc/article/details/108115295
3.https://www.bilibili.com/video/BV11R4y1p7DQ/?spm_id_from=333.788.recommend_more_video.-1
(二)
1.Hash Table的內容：
H(Key) = (Key*3) mod 7
hi(Key) = (H(Key)+i2) mod 7，i 是碰撞次數。
H(21) = (21*3) mod 7 = 63 mod 7 = 0
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
21 |
|
|
|
|
|
|
|
|
|
H(1) = (1*3) mod 7 = 3 mod 7 = 3
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
21 |
|
|
1 |
|
|
|
|
|
|
H(16) = (16*3) mod 7 = 48 mod 7 = 6
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
21 |
|
|
1 |
|
|
16 |
|
|
|
H(11) = (11*3) mod 7 = 33 mod 7 = 5
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
21 |
|
|
1 |
|
11 |
16 |
|
|
|
H(25) = (25*3) mod 7 = 75 mod 7 = 5，發生碰撞。
h1(25) = (5+12) mod 7 = 6 mod 7 = 6，發生碰撞。
h2(25) = (5+22) mod 7 = 9 mod 7 = 2。
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
21 |
|
25 |
1 |
|
11 |
16 |
|
|
|
H(9) = (9*3) mod 7 = 27 mod 7 = 6，發生碰撞。
h1(9) = (6+12) mod 7 = 7 mod 7 = 0，發生碰撞。
h2(9) = (6+22) mod 7 = 10 mod 7 = 3，發生碰撞。
h3(9) = (6+32) mod 7 = 15 mod 7 = 1。
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
21 |
9 |
25 |
1 |
|
11 |
16 |
|
|
|
H(35) = (35*3) mod 7 = 105 mod 7 = 0，發生碰撞。
h1(35) = (0+12) mod 7 = 1 mod 7 = 1，發生碰撞。
h2(35) = (0+22) mod 7 = 4 mod 7 = 4。
2.查找成功及查找失敗的平均查找長度：
|
hash地址 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
Key |
21 |
9 |
25 |
1 |
35 |
11 |
16 |
|
|
|
|
比較次數 |
1 |
4 |
3 |
1 |
3 |
1 |
1 |
|
|
|
|
尋找空格次數 |
8 |
8 |
8 |
8 |
8 |
8 |
8 |
|
|
|
(1)查找成功的平均查找長度：
比較次數的加總 / 資料個數 = (1+4+3+1+3+1+1) / 7 = 14/7 = 2次。
(2)查找失敗的平均查找長度：
a.因為是 mod 7，所以尋找的 hash 地址是0~6。尋找到空格的次數就是失敗的次數。
b.尋找空格次數的加總 / 槽個數 = (8+7+6+5+4+3+2) / 7 = 35/7 = 5次。
留言列表
國考資訊處理解答 (7)
