散列查找

散列表：

散列表的构建：

小优化

散列表的查找：

查找成功：

查找长度为3

查找失败：

在数组中存放的是指针，指针为空则不用进行比较，故查找长度为0

平均查找长度：

常见的散列函数：

除留余数法：

直接定址法：

数字分析法：

平方取中法：

处理冲突：

拉链法:

见上

开放定址法：

注意：m是散列表表长，不要和散列函数中的除留余数法的p混淆

线性探测法：

存入操作：

存1：


存68，20：

存84：


存27：


存55：


存11：

存10：


存79：


存25：

查找操作：

查找成功

查找失败

删除操作：

查找效率分析（ASL）：

查找成功：

查找失败：

平方探测法：

（原因看数论）

存入操作：

↓

查找操作：

按照探测序列依次对比

伪随机序列法：

↓

再散列法：

总结：