概述
理想的查找情况是不经过任何比较，直接便能得到待查记录的存储位置，那就必须在记录的存储位置和它的关键码之间建立一个确定的对应关系H，使得每个关键码key和唯一的存储位置H(key)相对应。存储记录时，根据这个对应关系找到关键码的映射地址，并按此地址访问该记录。
查找记录时，根据这个对应关系找到待查关键码的映射地址，并按此地址访问该记录，这种查找技术称为散列技术。
采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表（hash table），将关键码映射为散列表中适当存储位置的函数称为散列函数（hash function），所得的存储位置称为散列地址（hash address）。
在散列技术中，由于记录的定位主要基于散列函数的计算，不需要进行关键码的多次比较，所以一般情况下，散列技术的的查找速度要比基于比较查找技术的查找速度快。但是散列技术一般不适用于多个记录有同样的关键码的情况，也不适用于范围查找。其最适合回答的问题是：如果有的话，哪个记录的关键码等于待查找值。
散列函数的定义域是查找集合中全部记录的关键码，如果散列表有m个地址单元，那么散列函数的值域就是0~m-1。
在理想情况下，对任意给定的查找集合T，如果选定了某个理想的散列函数H，以及相应的散列表T，则对T中的记录ri的关键码ki，H(ki)就是记录ri在散列表L中的存储位置。但是在实际应用中，往往会出现不同的关键码k1!=k2，有H(k1) == H(k2)，即两个不同的记录需要存放在同一个存储位置中，这种现象称为冲突，k1和k2相对于H称做同义词。
因此，在采用散列技术时需要考虑两个问题：
- 散列函数的设计
- 冲突的处理
散列函数的设计
直接定址法
直接定址法的散列函数是关键码的线性函数：
H(key) = a*key+b，a,b为常数
比如关键码集合为{10,30,50,70,80,90}，选取的散列函数为：H(key) = key/10,则散列表为：
直接定址法的特点是不会产生冲突，但实际应用中使用这种方法的情况很少。
直接定址法适用于事先知道关键码的分布，关键码集合不是很大且连续性较好的情况
除留余数法
基本思想是：选择某个适当的正整数p，以关键码除以p的余数作为散列地址：
H(key) = key mod p
这个方法的关键在于选取适当的p，p选的不好容易产生同义词。例如，p含有质因子p = m*n，则所有含m或n因子的关键码的散列地址均为m或n的倍数，这显然增加了冲突的机会。
一般情况下，若散列表表长为m，通常选p为小于或等于表长（最好接近m）的最小素数或不包含小于20质因子的合数。
除留余数法是一种最简单，最常用的构造散列函数的方法，并且其不要求事先知道关键码的分布。
平方取中法
基本思想是：对关键码平方后，按散列表的大小，取中间的若干位作为散列地址，之所以如此，是因为一个数平方后，中间的几位分布较均匀，从而减少冲突的概率。例如关键码1234，假设散列地址是2位，由于(1234)^2 = 1 522 756，选取中间的两位作为散列地址，可以选22，也可以选27。
平方取中法适用于在事先不知道关键码的分布且关键码的位数不是很大的情况
处理冲突的方法
有的时候很难找到理想的散列函数。如果某记录按散列函数计算出的散列地址加入散列表时产生了冲突，就必须另外再找一个地方来存放它，因此要有合适的处理冲突的方法。
开放定址法
用开放定址法处理冲突得到的散列表称为闭散列表
基本思想：如果有关键码得到的散列地址产生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。常用的有线性探测法和二次探测法，
线性探测法
发生冲突时，从冲突的下一个位置起，一次寻找空的散列地址。对于键值key，表长m，冲突时下一个散列地址：
( H(key) + di ) % m,(di = 1 2 3 … m-1)
在处理冲突的过程中出现的非同义词之间对同一个散列地址争夺的现象称为堆积，显然堆积会降低查找效率。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22int HashSerch1(int ht[],int m,int k,int *p){
int i,j,flag = 0; //falg=0表示散列表未满
j = H(k); //计算散列地址
i = j; //记录比较的起始位置
while(ht[i] != 0 && falg == 0){
if(ht[i] == k){
*p = i;
return 1; //比较若干次后查找成功
}
else
i = (i+1)%m; //向后探测一个位置
if(i == j)
flag = 1; //表已满
}
if(flag == 1)
exit(1); //溢出
else{
ht[i] = k;
*p = i;
return 0; //比较若干次，查找不成功，插入
}
}
当从闭散列表中删除一个记录时，需要考虑两点：
- 删除一个记录一定不能影响后面的记录的查找。
- 删除记录的存储单元可以被后来插入的记录使用。
不能简单的把被删除单元清空，应该是在被删除记录的位置上放一个特殊标记，标志一个记录曾经占用这个单元，但是现在已经不占用了。查找时遇到该标记应继续向下搜索，插入时遇到该标记应将新元素插入该位置。
二次探测法
当发生冲突时，二次探测法寻址下一个散列地址的公式为：
(H(key)+di)%m (di = 1^2,-1^2,2^2,-2^2…q^2,-q^2 , q<=sqrt(m))
链地址法
用链地址法构造的散列表称为开散列表。
基本思想：将所有散列地址相同的记录，即所有关键码为同义词的记录存储在一个单链表中——称为同义词子表，在散列表中存储的是所有同义词子表的头指针，设n个记录存储在长度为m的开散列表中，则同义词子表的平均长度为n/m。
例如，对于关键码集合：{47,7,29,11,16,92,22,8,3}，H(key) = key%11，用链地址法处理冲突，构造的开散列表为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19int HashSearch2(Node *ht[],int m,int k,Node *pos){
int j = H(k); //计算散列地址
Node *p = ht[j],*q; //工作指针p初始化为ht[j]的表头
while((p != NULL) &&(p->data != k)){
p = p>next;
}
if(p->data == k){
pos = p;
return 1; //查找成功
}
else{ //查找失败则插入
q = (Node*)malloc(sizeof(Node));
q->data = k;
q->next = ht[j]; //插在ht[j]的表头
ht[j] = q;
pos = q;
return 0;
}
}
用链地址法处理冲突时，删除一个记录只需要在相应的单链表中删除该结点就可以1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19void HashDelete2(Node *ht[],int m,int k){
int j = H(k); //计算散列地址
Node *p = NULL,*pre = NULL; 、、设置两个工作指针
if(ht[j]->data == k){ //处理表头的特殊情况
p = ht[j];
ht[j] = p->next;
free(p);
}
pre = ht[j];
p = pre->next; //工作指针初始化
while((p!=NULL) && (p->data !=k)){
pre = p;
p = p->next;
}
if(p->data == k){ //查找成功，执行删除操作
pre->next = p->next;
free(p);
}
}
性能分析
在散列技术中， 处理冲突的方法不同，得到的散列表不同，散列表的查找性能也不同。在查找过程中关键码的比较次数取决于产生冲突的概率，产生冲突越多，查找效率就越低。影响冲突产生的因素有三点：
- 散列函数是否均匀
- 处理冲突的方法
- 散列表的装填因子
设填入散列表的记录个数为n，散列表长度为m，则装填因子为a = n/m。a标志着散列表装满的程度。
可见，散列表的平均查找长度是装填因子a的函数。不管n有多大，总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围内，因此，散列查找的时间复杂度为O(1)。
参考资料：
《数据结构——从概念到C实现》 第7章
《数据结构——严蔚敏》