基于除留余数法的哈希表构建及冲突处理问题求助

a) 确定合适的m值 #

除留余数法的哈希函数为 h(key) = key % m，最优m值优先选质数（或不含小于20质因子的合数），能最大程度降低哈希冲突概率。题目给定哈希表大小为13，13本身是质数，因此合适的m值就是13。

b) 链表法处理冲突的可视化结果 #

先计算每个键的哈希值（h(key) = key %13）：

• 13→0；17→4；39→0；27→1；1→1；20→7；4→4；40→1；25→12；9→9；2→2；37→11

同一哈希槽的冲突元素以链表串联，结果如下：

• 0 →13 →39
• 1 →27 →1 →40
• 2 →2
• 4 →17 →4
• 7 →20
• 9 →9
• 11 →37
• 12 →25
• 3、5、6、8、10：空槽

c) 线性探测（s(j)=j）的插入分步过程 #

线性探测的哈希函数为 h_j(key) = (h(key) + j) %13，j从0开始递增，直到找到空槽。以下是逐个键的插入步骤：

1. 插入13：h(13)=13%13=0，槽0为空，直接插入 → 槽0：13
2. 插入17：h(17)=17%13=4，槽4为空，直接插入 → 槽4：17
3. 插入39：h(39)=39%13=0，槽0已被占用；j=1，h_1=(0+1)%13=1，槽1为空，插入 → 槽1：39
4. 插入27：h(27)=27%13=1，槽1已被占用；j=1，h_1=(1+1)%13=2，槽2为空，插入 → 槽2：27
5. 插入1：h(1)=1%13=1，槽1已被占用；j=1→h1=2（被27占用）；j=2→h_2=(1+2)%13=3，槽3为空，插入 → 槽3：1
6. 插入20：h(20)=20%13=7，槽7为空，直接插入 → 槽7：20
7. 插入4：h(4)=4%13=4，槽4已被占用；j=1→h_1=(4+1)%13=5，槽5为空，插入 → 槽5：4
8. 插入40：h(40)=40%13=1，槽1已被占用；j=1→h1=2（被27占用）；j=2→h2=3（被1占用）；j=3→h3=4（被17占用）；j=4→h4=5（被4占用）；j=5→h_5=(1+5)%13=6，槽6为空，插入 → 槽6：40
9. 插入25：h(25)=25%13=12，槽12为空，直接插入 → 槽12：25
10. 插入9：h(9)=9%13=9，槽9为空，直接插入 → 槽9：9
11. 插入2：h(2)=2%13=2，槽2已被占用；j=1→h1=3（被1占用）；j=2→h2=4（被17占用）；j=3→h3=5（被4占用）；j=4→h4=6（被40占用）；j=5→h5=7（被20占用）；j=6→h_6=(2+6)%13=8，槽8为空，插入 → 槽8：2
12. 插入37：h(37)=37%13=11，槽11为空，直接插入 → 槽11：37

最终线性探测后的哈希表各槽内容：
0:13, 1:39, 2:27, 3:1, 4:17, 5:4, 6:40, 7:20, 8:2, 9:9, 10:空, 11:37, 12:25

内容的提问来源于stack exchange，提问作者ekert298