昨天学习搜索中两种常见且简单的搜索方式---线性搜索和二分搜索，今天则学习了另一种比较重要且相对较复杂的搜索方式----散列法搜索
要知道的是，散列法搜索不像昨天介绍的两种搜索方式，线性搜索和二分搜索中元素可以排列在任意位置，而散列法搜索则是根据各元素的值来确定存储位置，然后将位置保管在散列表中，从而实现数据的高速搜索。其中散列表是一种数据结构，能对包含关键字的数据集合高效地执行动态插入，搜索，删除操作。虽然链表也能完成同样操作，但搜索和删除的复杂度都高达O(n).
散列表由能容纳m个元素的数组T，以及根据关键字决定数组下标的函数共同组成。就像上面所说的，元素的位置室友元素值决定的，这就比较像一个字典了。散列表大致可通过以下方法实现:
insert(data) T[h(data.key)]=data search(data) return T[h(data.key)];这里我们默认data.key是整数，当然，不是整数的情况下，我们也可以通过一些手段将其转化为整数用来作为下标。
而h(k)是根据k值求数组下标的函数，称为散列函数。散列函数的值域为[0,m-1],其中m是数组T的长度，为满足这个要求，我们一般将散列函数定义为取余运算，保证输出值在0~m-1之间，比如:
h(k)=k mod m
但是这个函数也许大家也能很容易发现她的问题，那就是不同的key对应同一散列值的情况，导致不同的元素存储在数组同一位置。为了解决这种问题，我们有很多方法。开放地址法就是解决这种冲突的常用手段。
这里我们使用的是双散列结构的开放地址法，即使用两个散列函数共同确定元素位置：
H(k)=h(k,i)=(h1(k)+i*h2(k))mod m
散列函数h(k,i)拥有关键字k和i两个参数。其中i是发生冲突后计算下一个散列值的次数。也就是说一开始添加元素时会调用h(k,0),如果发生冲突，就会依次调用h(k,1),h(k,2),h(k,3).......
双散列结构的开放地址法的实现方法如下:
int h1(key) {return key mod M;} int h2(key) {return 1+(key mod (M-1));} int h(key,i) {return (h1(key)+i*h2(key)) mod m} int insert(T,key) { i=0; while(true) j=h(key,i) if(T[j]==Null) //未发生冲突，直接插入并返回下标 T[j]=key return j else //发生冲突，i自增，开始下一次的插入 i++; } int search(T,key) { i=0; while(true) j=h(key,i) if(T[j]==key) //找到元素，返回下标 return j else if(T[j]==Null or i>=m) //查找结束，未找到元素，返回空 else i++ //查找未结束，继续向下一个位置查找 } 这里要理解为啥找到T[j]==null就直接返回空表示未查找到，因为虽然key虽然可能发生冲突存在多个可能的下标的位置上，但是存放的顺序也是固定，也就是说不可能跳过h(key,i)的位置直接先存放在h(key,i+1)的位置，所以在找打j=h(key,i)上元素为空，那么后面的h(key,i+1)，h(key,i+2)位置肯定也不需要查找了，肯定是不存在的。 还有个要注意的问题，由于发生冲突时，每次移动的位置是确定的，都是h2(k),那么就要保证数组的长度m与h2(k)必须是互质的，否则会不断循环的发生冲突，比如说对于有个值key,使得h1(key)=3,h2(key)=4,而数组的长度m=16,那么在发证冲的情况下，寻找的下标依次是3,7,11,(3+3*4) mod16=15,(3+4*4) mod16=3,7,11.....这样就会不断地在3 7 11 15位置上发生冲突，这样的话肯定是不可以的。所以为了保证不出现这种情况，我们可以特意让m为质数，然后取一个小于m的值作为h2(key)，或者最简单的方法就是直接令h2(k)=1，这样使得发生冲突时依次查找后面的位置。 简单介绍了这种方法后，做个小题目吧，就直接用书上的题目了－－－ 题目:请实现一个能执行以下命令的简易"字典"。 1.insert str:向当前字典插入字符串str 2.find str:当前字典中包含str时输出yes,不包含时输出no 输入：第一行输入命令数n.随后n行按顺序驶入n个命令。命令格式如上。 输出：对于find命令输出yes或no.每个输出占一行。 限制: 输入的字符串仅仅由'A','C','G','T'四种字母构成。 1<=字符串长度<=12 n<=1000000 输入示例： 输出示例： 6 yes insert AAA no insert AAC yes find AAA find CCC insert CCC find CCC 散列法搜索的原理已经介绍了，下面直接附上源代码： #include<stdio.h> #include<string.h> #define M 1046527 #define NIL (-1) #define L 14 char H[M][L]; int getChar(char ch) { switch(ch) { case 'A':return 1; case 'B':return 2; case 'C':return 3; case 'D':return 4; default:return -1; } } long long getKey(char str[]) { long long sum=0,p=1; for(int i=0;i<strlen(str);i++) { sum+=p*getChar(str[i]); p*=5; } return sum; } int h1(int key) {return key%M;} int h2(int key) {return 1+(key%(M-1));} int find(char str[]) { long long key,h; key=getKey(str); //将字符串转换为数值 for(int i=0;;i++) { h=(h1(key)+i*h2(key))%M; if(strcmp(H[h],str)==0) return 1; //strcmp(str1,str2),若str1==str2，则返回零；若str1<str2，则返回负数；若str1>str2，则返回正数。 else if(strlen(H[h])==0) return 0; //找到的位置上字符串为空，则找不到该字符串 } return 0; } int insert(char str[]) { long long key,h; key=getKey(str); for(int i=0;;i++) { h=(h1(key)+i*h2(key))%M; if(strcmp(H[h],str)==0) return 1; //在字典中已经有了该"单词"，不进行插入 else if(strlen(H[h])==0) { strcpy(H[h],str); return 0; //不存在该"单词"，则在首次为空的位置进行插入 } } return 0; } int main() { int n,h; char str[L],com[9]; for(int i=0;i<M;i++) H[i][0]='\0'; //初始化散列表，令所有字符串为空 scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%s %s",com,str); if(com[0]=='i') { insert(str); } else{ if(find(str)) printf("yes\n"); else{ printf("no\n"); } } } return 0; } PS:本篇博客因为代码格式的问题修改了好几次，在这里和大家道个歉～