哈希表查找

哈希表涉及的是一种映射关系，可以根据某个值查找到关键字的地址，这样的做法省去了比较的时间，优化了算法。

哈希表的定义

哈希表是把值（关键字）存到跟它具有“唯一”映射的格子（某个地址）里，需要用的时候则可直接取到该值（关键字）的值。而这个“唯一”的格子的地址是根据关键字的值确定的，确定这个格子需要用到哈希函数。

例如：

1. 哈希函数为（K为关键字的值，m为哈希表长度，h(K)为储存该值的地址；其中h(K)的范围在0~m-1之间）

h(K) = K%m

要将集合 S={16,76,63,57,40}存入哈希表中，取m=11，则有：

2. 将集合存完之后，如要查找该集合是否存在 K=16 的值就无需逐一比较了，直接根据已知的哈希函数计算出地址，在判断改地址是否存在该值就行了：

h(16)=16%11=5，取出哈希表中地址为5的值比较即可。

那么问题来了，如果集合S中同时存在值K=16和值K=27，我们该如何将两个地址一样的值存入哈希表呢？

我们将这种情况试做冲突，在建立哈希表时，应该把解决冲突的方法想好，那么建立哈希表的步骤就变成了：

1. 构造“好”的哈希函数
2. 制定解决冲突的放方法

常用的哈希函数

1. 除留余数法(m为表长，p为小于m的最大素数）

H(key)=key%p (p<=m)

2. 直接地址法(a,b为常数）

H(key)=a*key%+b

3. 数字分析法(关键字位数比地址码位数多的情况）

将关键字排成一列，选取几列位数当做地址码，前提是地址码不会重复

处理冲突的方法

1. 开放定址法（H(key)为原哈希函数，m为表长，d_i为探测时的地址增量）

基本思路就是根据该key的值探测哈希表中其他的空格子存储冲突的值，设空格子的地址序列为Hi

Hi = (H(key)+di)%m (i = 1,2,3…,k(k<=m-))

形成探测序列的方法很多，如下：

- 线性探测法：d_i = 1,2,3…,m=1

- 二次探测法：d_i = 1²,-1²,2²,-2²,…,q²,-q²,(q<=m/2)

- 双哈希函数探测法：d_i = iRH(key) (i = 1,2,3,…,m-1) ,此时Hi = (H(key)+iRH(key))%m

2. 连地址法

基本思路就是在重复的位置建立链表或数组存储