之前我说过一些查找的算法，而本文中，也将继续讲述一下关于散列表的查找的一些方法的介绍。
首先了解一下散列技术：
散列技术是记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每 个关键字key对应一个存储位置f(key). 查找时,根据这个对应关系找到给定值 key的映射f(key). 若查找集合中存在这个记录,则必定在f(key)的位置上.
第一种方法：直接定址法
直接地址法其实就是利用一个地址记录存储一个范围内的信息。
f(key) - a*key+b(a,b为常数)
例如：
年龄在0-1岁的有500万，将500万用地址00表示
年龄在1-2岁的有600万，将600万用地址01表示
…………
年龄在20-21岁的有3000万，将3000万用地址20表示
那么，我们要查在1-2岁有多少人数时，直接查他对应的地址01就可以。
这个直接地址法的效率并不高，容易造成地址数过大。
第二种方法：数字分析法
对一些数字多的值，例如手机号码，记录其固定的4位或多位连续的数字，当我们查找时，直接查找记录的几个数字，来找到整个值。
缺点：易重复分布太集中的某几个数字，若分布均匀，可作为散列地址。
第三种方法：平方取中法
这个方法就是将存储的数开平方，取中间的几位数字，记录中间的值为key，然后通过key去查找内容。
例如：1234^2 = 1522756
记录227
缺点，会遇到重复的值，造成散列冲突
第四种方法:折叠法
折叠法就是将关键字从左到右分割成位数相等的几部分(注意最后一部分位数不够可以稍微短 些); 然后将几部分叠加求和,并按散列表表⻓,取后几位作为散列地址.
例如：
9 8 7 6 5 4 3 2 1 0
分割成3位一组，共4组
987 654 321 0
987+654+321+0 = 1962
将1962后3位：962为散列地址。
缺点：有几率造成散列冲突
第五种方法：除留余数法
f(key) = key mod p(p<=n)
除留余数法取关键字被某个不大于散列表表长n的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=n
第六种方法：随机数法
f(key) = random(key);
在一定的范围内随机生成一个值，作为f(key)的散列值
缺点：
计算公式花费时间
关键字长度;
散列表⼤⼩
关键字分布情况
记录查找概率
第六种方法：开放定址法
开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址.只有散列表足够大,空的散列 地址总能找到,并将记录存入.
开放定址法公式:
fi(key)=(f(key)+di) Mod m; ( di = 1,2,3,……,m-1)
开放地址法就是将值与表长度n求余，存储在相应的下标当中，若出现重复的求余值，那么寻找该下标值往后的地址为空的地方存储。
例如：
关键字集合 { 12,67,56,16,25,37,22,29,15,47,48,34 } 表⻓为12, 我们用散列函数f(key) = key mod 12;
关键字集合 { 12,67,56,16,25,37,22,29,15,47,48,34 } 表⻓为12, 我们用散列函数f ( key ) = key mod 12;
- key = 37时, f(37) = 1, 与25发⽣冲突;
- 使⽤开放定址公式: f(37) = (f(37) + 1) mod 12 = 2.
- 发现下标为2 位置上是空.即可存储下来.
开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址.只有散列表足够大,空的散列 地址总能找到,并将记录存入.
解决冲突的开放定址法称为 线性探测法
第七种方法:链地址法
关键字集合 { 12,67,56,16,25,37,22,29,15,47,48,34 }
表⻓为12, 我们用散列函数 f ( key ) = key mod 12;
链地址法跟之前讲的邻接表有点类似，先通过求余存储相应下标的位置，每个下标都对应着一个链表，这个链表记录散列值相同的数值。以此来减少查找的次数
第八种方法：公共溢出法
关键字集合 { 12,67,56,16,25,37,22,29,15,47,48,34 }
表⻓为12, 我们用散列函数 f ( key ) = key mod 12;
这个方法跟链地址法原理相同，唯一的区别就是第一次求得没有重复的散列值存储在一个链表中，第二次求的重复的散列表又存储在另一个链表中，当遇到重复的，就用另一个链表记录重复的值，这个方法浪费的空间太多，一般很少使用。
下面我们就来实现一下开放地址法来实现一下散列表的查找。
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
#define OK 1
#define ERROR 0
//定义散列表长为数组的长度
#define HASHSIZE 12
#define NULLKEY -32768
typedef struct {
//数据元素存储基址
int *data;
//当前数据元素个数
int count;
}HashTable;
int n = 0;//散列表表长，全局变量
//1、初始化散列表
int InitHashTable(HashTable *h){
int i;
//1、设置h.count初始值；并开辟n个空间
n = HASHSIZE;
h->count = n;
h->data = (int *)malloc(sizeof(int)*n);
//2、为h.data[i]动态数组中的数据置空(-32768)
for (i = 0; i<n; i++) {
h->data[i] = NULLKEY;
}
return OK;
}
//2、散列函数
int Hash(int key){
//除留余数法
return key%n;
}
//3、插入关键字进散列表
void InsertHash(HashTable *h,int key){
//1、求散列地址
int address = Hash(key);
//2、如果不为空，则冲突
while (h->data[address]!=NULLKEY) {
//开发地址发的线形探测
address = (address+1)%n;
}
//3、直到有空位后插入关键字
h->data[address] = key;
}
//4、散列表查找关键字
int SearchHash(HashTable h,int key,int *address){
//1、求散列地址
*address = Hash(key);
//2、如果不为空，则冲突
while (h.data[*address]!=key) {
//开放地址法的线形探测
*address = (*address+1)%n;
if(h.data[*address] == NULLKEY || *address == Hash(key))
//说明关键字不存在
return ERROR;
}
return OK;
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("开放地址法!\n");
int arr[HASHSIZE]={12,67,56,16,25,37,22,29,15,47,48,34};
HashTable h;
//初始化
InitHashTable(&h);
//插入数据
for (int i = 0; i<n; i++) {
InsertHash(&h, arr[i]);
}
//查39
int key = 39;
int result,p;
result = SearchHash(h, key, &p);
if(result)
printf("查找%d的地址为:%d\n",key,p);
else
printf("查找%d失败\n",key);
//查48
key = 48;
result = SearchHash(h, key, &p);
if(result)
printf("查找%d的地址为:%d\n",key,p);
else
printf("查找%d失败\n",key);
printf("\n");
//将数组中的key，打印出所在散列存储地址
for (int i = 0; i<n; i++) {
key = arr[i];
SearchHash(h, key, &p);
printf("查找%d的地址为:%d\n",key,p);
}
return 0;
}
输出结果
开放地址法!
查找39失败
查找48的地址为:6
查找12的地址为:0
查找67的地址为:7
查找56的地址为:8
查找16的地址为:4
查找25的地址为:1
查找37的地址为:2
查找22的地址为:10
查找29的地址为:5
查找15的地址为:3
查找47的地址为:11
查找48的地址为:6
查找34的地址为:9
Program ended with exit code: 0
