哈希表：给定一组查找关键字(32,15,7,11,4,28,56,61,79)，哈希表长为m=12，请按照除留余数法设计一个哈希函数，设每个记录的查找概率相等。

柔光的暖阳◎ 2024-04-23 20:05 2阅读 0赞

***慕课数据结构题目：***

给定一组查找关键字(32,15,7,11,4,28,56,61,79)，哈希表长为m=12，请按照除留余数法设计一个哈希函数，设每个记录的查找概率相等。

（1）画出按照**线性探测**再散列处理冲突得到的哈希表（给出求解过程），并计算等概率情况下查找成功和查找失败时的平均查找长度各是多少。

（2）画出按照**链地址法**处理冲突得到的哈希表，并计算等概率情况下查找成功和查找失败时的平均查找长度各是多少。

#### **解答过程：** ####

![在这里插入图片描述][3e017bf2fa5c4f739599cadbf6b62ec9.jpeg]

![在这里插入图片描述][f738e6087d124647a69c2809aa1bbc20.jpeg]

#### 散列查找相关知识点 ####

**思维导图：**  
![在这里插入图片描述][5e2ee12799444e229347ebd939d34412.png]

**除留余数法：**

*  假定散列表（哈希表）表长为 m，取一个不大于 m 但最接近或等于 m 的质数 p，利用以下公式把关键字转换成散列地址。
 *  散列函数为：H(key) = key % p
 *

**处理冲突的方法：**

*  开放地址法：
    
     *  线性探测法：  
        ![在这里插入图片描述][1b053b721b6648b39dfc33a5e75384ba.png]
     *  平方探测法：  
        ![在这里插入图片描述][224d6269ea454c71bde948728bc9b27e.png]
     *  双散列法：  
        ![在这里插入图片描述][b859124a3277452a973ffb3e2c8b861e.png]
 *  拉链法：  
    ![在这里插入图片描述][cd110609d8214abc8b057ca2307edcc2.png]

[3e017bf2fa5c4f739599cadbf6b62ec9.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/8be9b314e532427fa28b6b0c5b4317d2.jpeg
[f738e6087d124647a69c2809aa1bbc20.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5f6ce7fe43434306ba8504d5c9073175.jpeg
[5e2ee12799444e229347ebd939d34412.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/074592026a6d443c8949d6387df17aa9.png
[1b053b721b6648b39dfc33a5e75384ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c0532403c1e74f84be78d561e109161d.png
[224d6269ea454c71bde948728bc9b27e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/26d6e68bc47b45769bf87340c80426ea.png
[b859124a3277452a973ffb3e2c8b861e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/79c9c3144124477f8830275d525724cf.png
[cd110609d8214abc8b057ca2307edcc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/4201533701cb4de38ec99c2513235d5c.png