使用除留余数法的一个经验是若散列表表长为m,通常p为小于或等于表长(最好接近m)的最小质数或不包含小于20质因子的合数
2.除留余数法:H(key) = key % p(p为不大于散列表表長但最接近或等于表长的质数p)
3.数字分析法:选取r进制数数码分布较为均匀的若干位作为散列地址
4.平方取中法:取关键字的平方值的中间幾位作为散列地址
5.折叠法:将关键字分割成位数相同的几部分,然后取这几部份的叠加和作为散列地址
1.开放定址法(闭已知采用开放地址法解决哈希表冲突)
注:在开放定址的情形下不能随便物理删除表中已有元素,若删除元素将会截断其他具有相同散列地址的元素的查找地址若想删除一个元素,给它做一个删除标记进行逻辑删除。
2.拉链法(开已知采用开放地址法解决哈希表冲突)
把所有的同义词存储在一个線性链表中线性链表由其散列地址唯一标识。拉链法适用于经常进行插入和删除的情况
1.计算位置:构造散列函数确定关键词存储位置
2.解决冲突:应用某种策略解决多个关键词位置相同的问题。
如下程序实现统计打电话次数最多的人
輸入:通话记录的条数N接下来输入N条记录,每条记录含有两个电话号码
冲突解决办法:分离链接法。
散列函数:除留余数法
//查找打電话最多的人
//冲突处理的方法:分离链接法
//哈希函数:出留余数法
//返回大于size的最小素数
//从大于N的第一个奇数开始
//计算要查找的key的哈希值
//从該哈希值所对应的链表的第一个节点开始
//当未到该链表尾,并且key未找到时
//向散列表中插入数据
if (!P) //关键词未找到则插入该新数据
//析构函数,釋放动态分配的内存空间