哈希表的查找

哈希表的几个概念

1. 哈希函数:把关键字为ki的对象存放在相对应的哈希地址中
2. 哈希表 :长度为m(m≥n)的连续内存单元
   
3. 哈希冲突:对于两个关键字分别为ki和kj(i≠j)的记录,有ki≠kj ,但h(ki)=h(kj).我们把这种现象称为哈希冲突.(哈希冲突是很难避免的!!)

正因为哈希冲突,所以哈希表的实际主要就是解决哈希冲突.但是实际上哈希冲突是难以避免的,主要与三个因素有关:
1.与装填因子有关。装填因子α=存储的记录个数/哈希表的大小 =n/m => α越小，冲突的可能性就越小； α越大（最大可取1）， 冲突的可能性就越大。通常使最终的控制在0.6～0.9的范围内。
2.与所采用的哈希函数有关。好的哈希函数会减少冲突的发生；不
好的哈希函数会增加冲突的发生。
3.与解决冲突方法有关。好的哈希冲突解决方法会减少冲突的发生

哈希函数的构造方法

1. 直接定址法

直接定址法是以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法.h(k)=k+c

2. 除留余数法
   h(k)=k mod p(mod为求余运算,p≤m p最好是质数)
3. 数字分析法
   

接下来做个题目试试看

哈希冲突解决方法

1.开放定址法:即冲突时找一个新的空闲的哈希地址
找空闲单元的方式有以下两种

• 线性探查法
  
• 平方探查法
  
  2.拉链法:把所有的同义词用单链表连接起来的方法