散列表查找（哈希表）

一、散列技术
记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每一个关键字key对应一个存储位置f（key）.查找时，根据这个对应关系找到给定值key的映射f（key）.若查找集合中存在这个记录，则必定在f（key）的位置上。

1、直接定制法

f(key) = a * key + b (a,b为常数);

2、数字分析法

3、平方取中法

4、折叠法
将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够可以稍微短些）；然后将几部分叠加求和，并按散列表表长，取后几位作为散列地址。

5、除留余数法
f ( key ) = key mod p ( p <= m )

6、随机数法
f ( key ) = random ( key ) ;

1. 计算公式花费时间
   2.关键字长度;
2. 散列表⼤⼩
   4.关键字分布情况
3. 记录查找概率

二、处理散列表冲突方法探索
1、开放定址法
开放定址法就是⼀旦发⽣了冲突,就去寻找下⼀个空的散列地址.只有散列表⾜够⼤,空的散列地址总能找到,并将记录存⼊.
开放定址法公式:
fi ( key ) = ( f ( key ) + di ) Mod m ; ( di = 1,2,3,……,m-1)

2、再散列函数法
对于散列表来说, 我们事先准备多个散列函数:
f i( key ) = RH i ( key ) (i = 1,2,…,k)
RH逻辑教育 i 指的是不同的散列函数.

3、链地址法

将所有的关键字为同义词的记录存储在⼀个单链表中,我们称为这种同义词⼦表. 在散列表中只
存储所有同义词⼦表的头指针(头地址).

4、 公共溢出法