散列表的查找
散列表的查找
基本思想
记录的存储位置与关键字之间存在的对应关系.
使用哈希函数查找对应的数据
就是直接将学生的学号当做下标来存储.
这样就非常好查找
如何让查找
根据散列函数H(key)=k
查找key=n,则访问H(n)=n的地址,若内容为n则成功.
若查询不到,返回一个特殊值,空指针或空记录.
优点:查找效率非常高;
缺点:空间效率低!
若干术语
散列方法:使用一个函数计算元素的存储位置,按这个位置存放.
查找时,由同一个函数对给定值k计算地址,将k与地址单元中元素关键码进行对比,确定查找是否成功;
散列函数:散列方法中使用的转换函数;
冲突:不同关键码映射到同一个散列地址.
同义词:具有相同函数值的多个关键字.
散列函数的构造方法
在散列查找方法中,冲突不可避免,只能尽可能减少.
使用散列表要解决的两个问题
- 构造好散列函数
- 制定一个好的解决冲突的方案
构造散列函数考虑的因素
-
执行速度
-
关键字的长度
-
散列表的大小
-
关键字的分布情况
-
查找频率
散列表的构造的两个要求
- 希望散列的地址空间尽可能的小
- 尽量均匀的存放元素,避免冲突.
直接定址法
优点:以关键码key的某个线性函数值为散列地址,不会产生冲突.
缺点:要占用连续地址空间,空间效率低.
除留余数法
关键:如何选取合适的p?
技巧:设表长为m,取p<=m且为质数.
