哈希表

8、设哈希表长 m=14,哈希函数 H(key)=key%11。表中已有 4 个结点:

addr(15)=4

addr(38)=5

addr(61)=6

addr(84)=7
其余地址为空，如用二次探测再散列处理冲突,关键字为 49的结点的地址是（ ） 。
a)  8
b)  3 
c)  5 
d)  9

结果 为9  ：根据下面所说二次探测： 3^2



1、序

        该篇分别讲了散列表的引出、散列函数的设计、处理冲突的方法。并给出一段简单的示例代码。
2、散列表的引出

        给定一个关键字集合U={0,1......m-1},总共有不大于m个元素。如果m不是很大，我们可以定义一个数组T[0...(m-1)]，把U映射到数组T上，每个位置对应U中的一个关键字，若U中没有关键字为k的元素，则T[k]=NULL。我们称T为直接寻址表，不管是插入、删除、查找，只需o(1)的时间。但是注意前提，当”m不是很大的时候“。显然这个前提限制性很大，m很大时，必然会浪费很多空间，那该怎么办呢？于是就有了散列表：给定n个元素、m个存放位置（也称槽位），通过散列函数把关键字和存储位置关联起来，使每一个关键字与结构中一个唯一的存储位置相对应。于是在查找时，根据散列函数查找关键字的位置，不需要比较就可以取得要查找的记录。散列表也称哈希表。
3、散列函数

      散列函数有很多，好的散列函数特点是：（近似的）满足简单一致散列，即对于关键字集合U中的任何一个关键字，经散列函数映射到地址集合中任何一个地址的概率是相等的，此时可以称为均匀散列函数，也就是说使关键字经过散列函数得到一个“随机的地址”，以便使一组关键字的散列地址均匀分布在整个地址区间，减少冲突。很多时候我们将关键字解释为自然数。下面给出几种常用的散列函数。

       (1) 除法散列法

     散列函数：h(key)=key%p,其中p的取值很重要，这个函数得出的散列地址值不会超过p，同时可以选作p的值常常是与2的整数幂不太接近的质数。当存放位置m较大时，p不宜过小。

     (2)乘法散列法

     散列函数h(key)=[p*(key*A-(int)key*A)].其中0<A<1.(key*A-(int)key*A)是取key*A得小数部分，最后再乘上常数p，最后的值向下取整。一般p选择2的某个幂次，对p的选择并没有什么特别的要求。

     (3)全域散列

     在执行开始时，从一族仔细设计的函数中，随机地选择一个作为散列函数。这里的随机选择针对的是一次对散列表的应用，而不是一次简单的插入或查找操作。散列函数的确定性，是查找操作正确执行的保证。全域散列法确保，当key1 != key2时，两者发生碰撞的概率不大于1/m。设计一个全域散列函数类的方法如下，该方法中，散列表大小m的大小是任意的。

     全域散列函数类类设计方法：选择一个足够大的质数p，使得每一个可能的关键字都落在0到p-1的范围内。设Zp表示集合{0, 1, …, p-1}，Zp*表示集合{1, 2, …, p-1}。对于任何a∈Zp*和任何b∈Zp，定义散列函数ha,b （k）= ((ak+b) mod p) mod m所有这样的散列函数构成的函数族为：Hp,m = {ha,b : a∈Zp*和b∈Zp}由于对a来说有p-1种选择，对于b来说有p种选择，因而，Hp,m中共有p(p-1)个散列函数。在一次散列表应用中，a、b是随机生成的在一定范围的数。举个例子：若p=17,m=6,此次散列应用中随机生成a=3,b=4.则h3,4（8）=5.
4、处理冲突的方法

       当h(key1)==h(key2)时，两个不同的关键字对应得哈希地址相同，于是就产生了冲突，好的哈希函数只能避免冲突，不能完全消除冲突。那么该怎么样处理冲突呢？下面给出几种常用的方法。

     (1)开放寻址法

     在开发寻址法法中，所有的元素都存放在散列表里。插入一个元素时，可以连续地检查散列表的各项，直到找到一个空槽来放置待插入的关键字为止。对开发地址法来说，要求对每一个关键字k，探查序列必须是（0,1...m-1）的一个排列，即能够探测所有的槽。

     H=(H(key)+d) mod m 其中m表示哈希表长度，d为增量序列，H(key)为哈希函数

     线性探测再散列：当上式中d取值依次为1，2,3...m-1时，称为线性探测再散列。这种方法中，初始探查的位置确定了整个探测序列，比如第一个探测位置T[1],那么下一个位置是T[2],然后T[3]....故只有m种不同的探测序列。随着时间推移，连续被占用的槽不断增多，平均查找时间随之增加。这种现象称为集群现象。

    二次探测再散列：d=1^2,(-1)^2,2^2,(-2)^2......这时就是二次探测再散列，初始探查的位置确定了整个探测序列，故只有m种不同的探测序列。但出现集群现象的概率降低了很多。

    伪随机探测再散列：d=伪随机数序列。

    双重散列：使用的函数：h(k,i) = (h1(k) + i h2(k)) mod m, i=0, 1, …, m-1

    为能查找整个散列表，值h2(k)要与表的大小m互质。确保这一条件成立的一种方法是取m为2的幂，并设计一个总能产生奇数的h2。另一种方法是取m为质数，并设计一个总是产生较m小的正整数的h2。例如，可以取m为质数，h1(k)=k mod m , h2(k)=1+(k mod m’)，m’=m-1。

     (2)链地址法

     把散列到同一个槽中的所有元素都放在一个链表中。相对于开放地址法，可能会增加存储空间。

     (3)建立一个公共溢出区

     若发生冲突，把key存入公共溢出区。
5、完全散列

      如果某一种散列技术在进行查找时，其最坏情况内存访问次数为O(1)的话（没有冲突产生），则称其为完全散列(perfect hashing)。通常利用一种两级的散列方案，每一级上都采用全域散列，用一个二次散列表Sj存储所有散列到槽j中的关键字，就像是把链接法中的链表改成一个散列表。为了确保在第二级上不出现碰撞，需要让第二级散列表Sj的大小mj为散列到槽j中的关键字数nj的平方。如果利用从某一全域散列函数类中随机选出的散列函数h，来将n个关键字存储到一个大小为m=n的散列表中，并将每个二次散列表的大小置为mj=nj2 (j=0, 1, …, m-1)，则在一个完全散列方案中，存储所有二次散列表所需的存储总量的期望值小于2n。
6、散列表性能分析

       装填因子a=表中填入的记录数/散列表的长度。a标志着散列表的装满程度。散列表查找成功和不成功的平均查找长度分析很复杂，其中链接法处理冲突插入和删除时间为o(1)，操作也很方便，适合经常有记录删除的哈希表。链接法对哈希函数的依赖很大，如果哈希函数不好，可能会浪费很多空间。而开放地址法的删除记录时可以把删除的位置赋一个特殊值以标识这个记录被删除了。这样就不会影响其他记录插入和查找。
7、附录

       参考书籍：《算法导论》  《数据结构》

       哈希表的应用实例：

    [cpp] view plaincopy

        /*
         * 题目：给定一个全部由字符串组成的字典，字符串全部由大写字母构成。其中为每个字符串编写密码，编写的
         *       方式是对于 n 位字符串，给定一个 n 位数，大写字母与数字的对应方式按照电话键盘的方式：
         *         2: A,B,C     5: J,K,L    8: T,U,V
         *         3: D,E,F     6: M,N,O    9: W,X,Y,Z
         *         4: G,H,I     7: P,Q,R,S
         * 题目给出一个1--12位的数，找出在字典中出现且密码是这个数的所有字符串。字典中字符串的个数不超过5000。
         *        
         * 思路：1.回溯法找出所有可能的字符串
         *       2.在字典中查找此字符串是否存在。（字典存储采用哈希表存储） 
         *
         */ 
         
        #include<stdio.h> 
        #include<stdlib.h> 
        #include<string.h> 
         
        #define HASHTABLE_LENGTH 5001  //哈希表长度 
        #define STRING_LENGTH   13     //单词最大长度 
         
        //字符串 
        typedef struct 
        { 
            char str[STRING_LENGTH]; 
            int length; 
        }HString; 
         
        HString string={'\0',0};             //暂存可能的字符串 
        HString hashTable[HASHTABLE_LENGTH]; //哈希表 
         
        //hash函数,构造哈希表 
        void createHashTable(char *str) 
        { 
            int i,key,step=1; 
            i=key=0; 
            while(str[i]){ 
                key+=str[i++]-'A'; 
            } 
            key%=HASHTABLE_LENGTH; 
            while(1){ 
                if(hashTable[key].length==0){ 
                    hashTable[key].length=strlen(str); 
                    strcpy(hashTable[key].str,str); 
                    break; 
                } 
                key=(key+step+HASHTABLE_LENGTH)%HASHTABLE_LENGTH; 
                //处理冲突，线性探测再散列 
                if(step>0) 
                    step=-step; 
                else{ 
                    step=-step; 
                    step++; 
                } 
            } 
        } 
         
        //从文件中读字典 
        void readString() 
        { 
            int i; 
            char str[STRING_LENGTH]; 
            char ch; 
            FILE *fp; 
            if((fp=fopen("document/dictionary.txt","r"))==NULL){    
               printf("can not open file!\n");    
               exit(0);    
            }   
             
            i=0; 
            while((ch=getc(fp))!=EOF){    
                if(ch=='\n'){//读完一个字符串 
                    str[i]='\0'; 
                    createHashTable(str); 
                    i=0; 
                    continue; 
                } 
                str[i++]=ch; 
            } 
         
            if(fclose(fp)){    
                printf("can not close file!\n");    
                exit(0);    
            }    
        } 
         
        //在哈希表中查找是否存在该字符串,存在返回1，不存在返回0 
        int search(char *str) 
        { 
            int i,key,step=1; 
            i=key=0; 
            while(str[i]){ 
                key+=str[i++]-'A'; 
            } 
            key%=HASHTABLE_LENGTH; 
            while(1){ 
                if(hashTable[key].length==0) 
                    return 0; 
                if(strcmp(hashTable[key].str,str)==0){ 
                    return 1; 
                } 
                key=(key+step+HASHTABLE_LENGTH)%HASHTABLE_LENGTH; 
                //处理冲突，线性探测再散列 
                if(step>0) 
                    step=-step; 
                else{ 
                    step=-step; 
                    step++; 
                } 
            } 
            return 0; 
        } 
         
        //求所有可能的字符串 
        void getString(char* num) 
        { 
            int i,digit,max; 
            if(*num==0){//递归出口，字符串已到末尾 
                string.str[string.length]='\0'; 
                if(search(string.str))//这个字符串存在于字典中，输出 
                    puts(string.str); 
                return; 
            } 
         
            digit=*num-'0';//取第一位字符，转成数字 
            if(digit>=2&&digit<=6){ 
                i=(digit-2)*3+'A'; 
                max=(digit-2)*3+'A'+3; 
            } 
            else if(digit==7){ 
                i='P'; 
                max='P'+4; 
            } 
            else if(digit==8){ 
                i='T'; 
                max='T'+3; 
            } 
            else if(digit==9){ 
                i='W'; 
                max='W'+4; 
            } 
         
            for(i;i<max;i++){ 
                string.str[string.length++]=i; 
                getString(num+1); //递归 
                string.length--; 
            } 
        } 
         
        void main() 
        { 
            char num[STRING_LENGTH];   //由于输入的数字超出了unsigned long的范围，所以用字符串来存储 
            readString();              //把字典从文件中读入内存 
            printf("please inputer an number(1--12位,不能有0或1)\n"); 
            scanf("%s",num); 
            getString(num); 
        }