1. 散列表的基本概念

元素的存储位置和其关键字之间建立某种直接关系，这就是散列查找法。

（1）散列函数和散列地址：在记录的存储位置p和其关键字key之间建立一个确定的对应关系H，使p=H(key),称这对应关系H为散列函数，p为散列地址。
（2）散列表：一个有限连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录。通常散列表是一个一维数组，散列地址是数组的下标。
（3）冲突和同义词：对不同的关键字可能得带统一散列地址，即key1 ！= key2，而H（key1） = H（key2），这种现象称为冲突。具有相同函数值得关键字对该散列函数来说称作同义词，key1 和key2互称为同义词。

2. 散列函数的构造方法

选取散列函数的参考：

计算散列地址所需的时间；

关键字长度；

散列表大小；

关键字的分布情况；

查找记录的频率。

(1) 直接定址法

其实就是直接通过取关键的字的某个线性值作为散列地址：f(key)=a*key+b,(a,b为常数)

(2) 数字分析法

假设某公司的员工登记表以员工的手机号作为关键字。手机号一共11位。前3位是接入号，对应不同运营商的子品牌；中间4位表示归属地；最后4位是用户号。不同手机号前7位相同的可能性很大，所以可以选择后4 位作为散列地址，或者对后4位反转（1234 -> 4321）、循环右移（1234 -> 4123）、循环左移等等之后作为散列地址。

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布比较均匀，就可以考虑这个方法。

(3) 平方取中法

假设关键字是1234，平方之后是1522756，再抽取中间3位227，用作散列地址。平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。

(4) 折叠法

将关键字从左到右分割成位数相等的几部分，最后一部分位数不够时可以短些，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

比如关键字是9876543210，散列表表长是3位，将其分为四组，然后叠加求和：987 + 654 + 321 + 0 = 1962，取后3位962作为散列地址。

折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。

(5) 除留取余数法

f(key) = key mod p (p≤m)，m为散列表长。
这种方法不仅可以对关键字直接取模，也可在折叠、平方取中
后再取模。根据经验，若散列表表长为m，通常p为小于或等于表长（最好接近m）的最小质数，可以更好的减小冲突。

(6) 随机数法

f(key) = random(key)，这里random是随机函数。
当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

3. 处理冲突的方法

（1）开放地址法

开放地址就是一旦发生冲突，就去寻找下一个空的散列地址，只有散列表足够大，空的散列地址总能找到，并且记录它。
至于如何寻找下一个空的散列地址，有三种方法

1. 线性探测法

f(key)=(f(key)+d)%m ,其中d取（0，1,2,3,4.....，m-1），m为散列表的长度

如上图所示，散列表的长度为12，而且我们现在已经插入了部分数据了，下面我们继续插入37,。然后，我们使用散列函数计算37的散列地址：
f(37)=f(37)%12=1
但是我们发现1这个位置已经存放了25，那么我们就继续寻找下一个空的散列地址。
f(37)=（f(37)+1）%12=2
发现2这个地址没有内容，所以把37插入到这个位置，得如下图的结果：

线性探测来解决冲突问题，会造成冲突堆积。所谓的冲突堆积就是比如说刚才的37，它本来是属于下标1的元素，现在却占用了下标为2的空间，这会造成待会我们需要存放本来要放在下标为2的元素时，再次发生冲突，这个冲突会一直传播下去，造成查找和插入效率都大大减低。

2. 二次探测法

f（key）=（f(key)+d）%m, ,其中d取（0^2，1^2,-1^2,2^2,-2^2,3^2,-3^2,4^2,-4^2...,q^2,-q^2），q<=m/2,m为散列表的长度

其实，这个是对线性探测的一个优化，增加了平方可以不让关键字聚集在某一块区域。

例如，我们对刚才的那个散列表，插入一个元素：7，通过二次探测的散列函数计算得到的散列地址为：
f(7)=f(7)%12=7
但是，我发现下标为7的位置已经存放了元素：67，所以我需要寻找下一个存储地址：
f(7)=（f(7)+1^2）%12=8
突然发现下标为8的地址也存放了56这个元素，所以我们只能继续往下寻找下一个存储地址：
f(7)=（f(7)+（-1^2））%12=6
发现下标为6的这个地址空间还是空的，所以我就把7插入到这个位置，得到如下结果：

3. 随机探测法

f（key）=（f(key)+d）%m, d为随机数列，而m为表长
在实际程序中应预先用随机数发生器产生一个随机序列，将此序列作为依次探测的步长。这样就能使不同的关键字具有不同的探测次序，从而可以避免或减少堆聚。

(2) 链地址法

所谓的链地址法，其实就是当发生冲突时，我还是把它存放在当前的位置，只是每个位置都是使用链表来存放同义词，这个思路和图的邻接表存储方式很相似。如下图所示：

4. 散列表的查找

开放地址散列表存储表示

#define m 20 //散列表的长度
typedef struct{
    KeyType key;
    InfoType otherinfo;
}HashTable;

给定待查找的关键字key，根据造表时设定的散列函数计算H0=H（key）。

若单元H0为空，则所查找元素不存在。

若单元H0中元素关键字为key，则查找成功。

否则重复下述解决冲突的过程：

按处理冲突的方法，计算下一个散列地址Hi。

若单元Hi为空，则所查找元素不存在。

若单元Hi中元素的关键字为key，则查找成功。

#define NULLKEY 0
int SearchHash(HashTable HT,KeyType key)
{
    H0 = H(key);//根据散列函数H(key)计算散列地址
    if(HT[H0].key == NULLKEY) return -1;
    else if(HT[H0].key == key ) return H0;
    else
    {
        for(i=1;i<m;i++)
        {
              Hi = (H0+i)%m;//按照线性探测法计算下一个散列地址Hi
              if(HT[Hi].key == NULLKEY) return -1;
              else if(HT[Hi].key == key ) return Hi;
        }
        return -1;
    }
}

数据结构（查找-散列表（哈希表）的查找）