这种查找结构与线性表和树形结构都不同,前两者的共同特点是关键字与记录位置之间没有确定关系,需要从一个起点不断进行比较查找位置。
可以知道散列表(哈希表)是一种完全不同机制的查找结构,不采用基于比较选择的查找机制,而是直接在关键字与位置之间建立映射。
所以在讨论它时也和上面的几种查找结构的思路不同。
1.散列函数的构造方法
构造散列函数需要参考的几个原则。
几种常用的散列函数
1.直接定址法
根据关键字的线性函数值来取地址 如H(key) = a ×key +b
优点:计算简单,不会有冲突(因为查找表中不会有重复的关键字)
缺点:若关键字分布不连续,则存储空间浪费较多
2.除留余数法
最常用
H(key) = key % p
地址等于关键字key除p取余的结果
关于如何选择合适的除数p:
p一定要小于散列表的表长m(这里的表长注意是查找表的长度,而不是关键字的个数,所以除数p不能大于m,大于的话得到的余数就可能大于表长,这时就溢出了)
p应该是一个质数,并且要在一定范围内尽可能大,p在小于m的情况下取值越大则冲突的可能性越小,反之p越小则冲突可能性越大。p取质数也是为了尽量减少冲突
p如果过大的话也会有缺点,在关键字个数一定的情况下,可以得知余数p取得太大的话会造成很大的空间浪费(空隙太多)
3.数字分析法
4.平方取中法
数字分析法这里讲的太拉了