数据结构第十一周笔记—— 散列查找系列3 (慕课浙大版本--XiaoYu)

11.3 冲突处理方法

11.3.1 开放定址法

处理冲突的方法

常用冲突的思路：

1. 换个位置：开放地址法
   
2. 同一位置的冲突对象组织在一起：链地址法
   

开放地址法(Open Addressing)

1. 一旦产生了冲突(该地址已有其他元素)，就按某种规则去寻找另一空地址
   
2. 网络异常，图片无法展示

   |
   
   
3. di决定了不同的解决冲突方案：线性探测、平方探测、双散列(三种典型的开放地址法)

1. 线性探测：di = i(di的i是下标)，第一次探测i就是1，第二次探测再上次探测基础上加1，往后持续
   
2. 平方探测：跟上方类似，只不过i变成了正负i²(在原来位置基础上偏移量升级层次，加一平方减一平方，加二平方减二平方...)
   
3. 双散列：两个散列函数，第一个散列函数作为他的最早即时找的这个位置，第二个散列函数用来计算偏移量
   

11.3.2 线性探测

线性探测法(Linear Probing)：以增量序列1，2，.....，(TableSize-1)循环试探下一个存储地址

会形成聚集现象

如果按照与刚才例子输入相反的顺序插入各个元素，这些元素在散列表中的位置还是一样的？不一样

散列表查找性能分析

1. 成功平均查找长度(ASLs) => 就是我要找的对象最后被我找到了
   
2. 不成功平均查找长度(ASLu) =>找对象找不着
   

什么是成功的 => 在散列表里找到的是成功的，不在散列表的元素就是不成功的

ASL u = 值(值取决于哈希余数)

余数为0要比较3次，为1要比较2次，余数为2要比较1次，余数为3的时候要比较2次，余数为4、5、6都是比较一次就够了，余数为7则要比较9次才能知道，余数为8则是8次

余数-哈希函数

1. 余数的思想所谓余数，就是程序中取模运算中的“模”。余数具有一个非常重要的特性：可以将无限的数据归一到有限的范围（余数总是小于除数）
   

你知道，整数是没有边界的，它可能是正无穷，也可能是负无穷。但是余数却可以通过某一种关系，让整数处于一个确定的边界内。我想这也是人类发明星期或者礼拜的初衷吧，任你时光变迁，我都是以 7 天为一个周期，“周”而复始地过着确定的生活。因为从星期的角度看，不管你是哪一天，都会落到星期一到星期日的某一天里。

2. 同余定理在上边的例子中，第一天与第八天都是周一，第二天与第九天都是周二，即
   

1%7=8%7=1

2%7=9%7=2

这就引出了余数的另一个重要概念：同余定理

口语化表述：

两个整数 a 和 b，如果它们除以正整数 m 得到的余数相等，我们就可以说 a 和 b 对于模 m 同余

其实，奇数与偶数的确定就是同余定理的应用。将一个数字模2，得0为偶数，得1为奇数复杂算法拆解后的原理并不一定复杂，同余定理也可以作为有用的应用，就是哈希函数

3. 哈希函数（散列函数）
   

将任意长度的输入，通过哈希算法，压缩为某一固定长度的输出，所得存储位置为散列地址

散列过程

（1）存储记录时，通过散列函数记录散列地址，按地址存储记录

（2）查找记录时，通过同样的散列函数计算记录的散列地址，按散列地址访问记录

散列技术通过散列函数建立了从记录的关键码集合到散列表的地址集合的一个映射，显然，会出现两个不同记录存放在同一位置的情况，这种现象称为冲突，此时相同位置的记录称为同义词

散列函数中最常采用的方案是除留余数法，其基本思想：

选择适当的正整数P，以关键码除以P的余数作为散列地址

通常P为小于或等于表长（最好接近）的最小质数或不包含小于 20 质因子的合数

11.3.3 线性探测—字符串的例子

前面5个都是没有冲突的，第六个冲突1次(查找次数变为2)，第七个冲突4次，最后一个冲突2次

网络异常，图片无法展示

|

与例子相似,如果已知散列表的前8个位置有元素(但元素内容与例子不一样）而且后面18个位置也全是空位,那么平均不成功查找次数还是一样的吗？一样的

11.3.4 平方探测法(Quadratic Probing)

也可以叫做：二次探测

2. 平方探测法(Quadratic Probing)

1. 是否有空间，平方探测(二次探测)就能找得到？
   
2. 网络异常，图片无法展示

   |
   
   

还有一种平方探测的方式是: 。也就是增量序列为 。

如果采用前面讲的 增量序列找不到空位置，意味着采用 的增量序列也一定找不到空位置。

线性探测的缺陷：容易聚集，二次探测虽然也有但不严重

有定理显示：如果散列表长度TableSize是某个4k+3(k是正整数)形式的素数时，平方探测法就可以探测到整个散列表空间

11.3.5 平方探测法的实现

typedefstructHashTbl*HashTable;

structHashTbl{

   intTableSize;//当前表的实际大小

   Cell*TheCells;//代表自己是一个数组，实际上是一个指针

}H;

HanshTableInitializeTable(intTableSize)

{

   HashTableH;

   inti;

   if( TableSize<MinTableSize ){//判别散列表的大小，太小就没必要做散列，直接放在数组就行了

       Error("散列表太小");

       returnNULL;

   }

   //分配散列表

   H= (HashTable)malloc(sizeof(structHashTbl));//申请空间赋给H

   if( H==NULL )

       FatalError("空间溢出!!!");//判断有没有申请成功

   H->TableSize=NextPrime(TableSize);//申请成功的话希望表的size是素数，NextPrime就是这个目的，产生一个比表大一点的素数

   //分配散列表Cells

   H->TheCells=(Cell*)malloc(sizeof(Cell)*H->TableSize);//为真正的TableSize分配一个空间，就相当于指向一个数组了

   if(H->TheCells==NULL)

       FatalError("空间溢出!!!");

   for(i=0;i<H->TableSize;i++)

       H->TheCells[i].Info=Empty;

   returnH;

}

友情小提示：typedef struct 的typedef是用来取别名的，比如上方 HashTbl 的别名就是H

实际删除的元素不能真的从表中拿掉，不然查找的时候会有问题的。如果我们要删除可以先做个记号。这样在后续的查找与插入的好处有：首先在查找的时候碰到被删掉的元素就说这个位置他做了个记号被删掉了，我们就知道这还不是空位还可以继续找，如果真拿掉变成空位的话就会产生误判。然后插入的时候发现这个元素是被删掉了，他不是空位而是原来有元素占着，现在被删掉了，这个时候插入元素就可以来替代原来删掉的元素。这样我们插入删除的操作都可以做并且不影响我们的查找过程

//表的初始化

PositionFind(ElementTypeKey,HashTableH)//平方探测

{

   PositionCurrentPos,NewPos;

   intCNum;//记录冲突次数

   CNum=0;

   NewPos=CurrentPos=Hash(Key,H->TableSize);//要算哈希函数，所以先调用一个哈希函数。CurrentPos是我们值真正要放的位置

   while(H->TheCells[NewPos].Info!=Empty&&H->TheCells[NewPos].Element!=Key){//Info位置不空且Element值不等于我要找的Key，那就需要继续找，而循环的条件就是我们要找的位置，被别人占了但是不空

       //字符串类型的关键词需要strcmp函数

       if(++CNum%2){//判断冲突的奇偶次

           NewPos=CurrentPos+(CNum+1)/2*(CNum+1)/2;//探测方法：在原来的位置上(CurrentPos，也就是最早的哈希函数值)加减i²获得新的地址。因为一会加一会减，所以需要在上方用上if来判别是奇数是偶来决定该加还是该减

           while(NewPos>=H->TableSize)//上方NewPos加上后面的大小可能超出大于TableSize了，所以需要通过不断循环减去TableSize，一直到NewPos不大于他(不大于他就落在0-TableSize之间了)

               NewPos-=H->TableSize;

       }else{//如果是偶数就走这条路啦，减去一个i平方

           NewPos=CurrentPos-CNum/2*CNum/2;

           while(NewPos<0)//跟上面那个while类似，为了不负到突破地板，需要将值拉回来

               NewPos+=H->TableSize;

       }

   }

   returnNewPos;

}

将Cnum映射为i的平方。CNum 加 1除以2就是这个i的值。所以举个例子

例子：1加1除以2为1，3加1除以2为2，5加1除以2为3

如果是减少的话，4除2为2，6除2为3

voidInsert(ElementTypeKey,HashTableH)

{

   //插入操作

   PositionPos;

   Pos=Find(Key,H);//通过Find return出来一个position值

   if(H->TheCells[Pos].Info!=Legitimate){//需要判断Pos的状态，如果Pos不属于被占用的状态，那我们这个元素就可以放进去(什么情况不是属于被别人占用：空位或者被删除了)

       //确认在此插入

       H->TheCells[Pos].Info=Legitimate;//将Info设为被我占用的状态，然后下一步将Key放进去

       H->TheCells[Pos].Element=Key;//字符串类型的关键词需要strcpy函数

   }

}

ps：在开放地址散列表中，删除操作要很小心。通常只能"懒惰删除"，即需要增加一个“删除标记(Deleted)”，而并不是真正删除它。以便查找时不会"断链"。其空间可以在下次插入时重用

双散列探测法(Double Hashing)

网络异常，图片无法展示

|

再散列(Rehashing)

1. 当散列表元素太多(即装填因子α太大)时，查找效率会下降(因为冲突在不断增加);  

1. 怎么解决这个问题？扩大散列表。散列表扩大时，原有元素需要重新计算放置到新表中
   
2. 实用最大装填因子一般取0.5 <= α <= 0.85(通常控制在0.5以内)
   

2. 当装填因子过大时，解决的方法是加倍扩大散列表，这个过程叫做"再散列(Rehashing)"
   

11.3.6 分离链接法(Separate Chaining)

将相应位置上有冲突的所有关键词存储在同一单链表中

^表示空指针

链表实现

typedefstructListNode*Position,*List;

structListNode{

   ElementTypeElement;

   PositionNext;//把Next分量分给P，P是下方代码块的一个指针，指向单项链表的第一个元素

};

typedefstructHashTbl*HashTable;

structHashTbl{

   intTableSize;

   ListTheLists;

};

PositionFind(ElementTypeKey,HashTableH)//哈希表来表示

{

   PositionP;

   intPos;

   

   Pos=Hash(Key,H->TableSize);//初始散列位置，第一步算哈希函数值，得到散列函数散列地址，散列地址就代表他在这个数组里的位置

   P=H->TheLists[Pos].Next;//获得链表头，这个P就是上方代码块说的那个指针P，指向单项链表的第一个元素

   while(P!=NULL&&strcmp(P->Element,Key))//典型的遍历单项链表的循环，只要P不等于NULL，P所指向的这个元素跟我要找的这个元素不相等就一个个往后找，P的Next赋给P。意思就是只要P不空(后面还有元素)，那么循环就一直做，同时循环的另一个条件是当前的这个元素值不等于我要找的元素值，如果列表不空再找下一个，再下一个就P的Next赋给P

       //等循环退出来要么P空了，就return NULL(没找到)。要么就strcmp返回值等于0，等于0就相等了，那这个时候所在的这个节点就是我们找到了，也就是return P

       P=P->Next;

   returnP;

}

创建开放地址法的散列表

#define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */

typedefintElementType;    /* 关键词类型用整型 */

typedefintIndex;          /* 散列地址类型 */

typedefIndexPosition;     /* 数据所在位置与散列地址是同一类型 */

/* 散列单元状态类型，分别对应：有合法元素、空单元、有已删除元素 */

typedefenum { Legitimate, Empty, Deleted } EntryType;

typedefstructHashEntryCell; /* 散列表单元类型 */

structHashEntry{

   ElementTypeData; /* 存放元素 */

   EntryTypeInfo;   /* 单元状态 */

};

typedefstructTblNode*HashTable; /* 散列表类型 */

structTblNode {   /* 散列表结点定义 */

   intTableSize; /* 表的最大长度 */

   Cell*Cells;   /* 存放散列单元数据的数组 */

};

intNextPrime( intN )

{ /* 返回大于N且不超过MAXTABLESIZE的最小素数 */

   inti, p= (N%2)?N+2 : N+1; /*从大于N的下一个奇数开始 */

   while( p<=MAXTABLESIZE ) {

       for( i=(int)sqrt(p); i>2; i-- )

           if ( !(p%i) ) break; /* p不是素数 */

       if ( i==2 ) break; /* for正常结束，说明p是素数 */

       else  p+=2; /* 否则试探下一个奇数 */

   }

   returnp;

}

HashTableCreateTable( intTableSize )

{

   HashTableH;

   inti;

   H= (HashTable)malloc(sizeof(structTblNode));

   /* 保证散列表最大长度是素数 */

   H->TableSize=NextPrime(TableSize);

   /* 声明单元数组 */

   H->Cells= (Cell*)malloc(H->TableSize*sizeof(Cell));

   /* 初始化单元状态为“空单元” */

   for( i=0; i<H->TableSize; i++ )

       H->Cells[i].Info=Empty;

   returnH;

}

平方探测法的查找与插入

PositionFind( HashTableH, ElementTypeKey )

{

   PositionCurrentPos, NewPos;

   intCNum=0; /* 记录冲突次数 */

   NewPos=CurrentPos=Hash( Key, H->TableSize ); /* 初始散列位置 */

   /* 当该位置的单元非空，并且不是要找的元素时，发生冲突 */

   while( H->Cells[NewPos].Info!=Empty&&H->Cells[NewPos].Data!=Key ) {

                                          /* 字符串类型的关键词需要 strcmp 函数!! */

       /* 统计1次冲突，并判断奇偶次 */

       if( ++CNum%2 ){ /* 奇数次冲突 */

           NewPos=CurrentPos+ (CNum+1)*(CNum+1)/4; /* 增量为+[(CNum+1)/2]^2 */

           if ( NewPos>=H->TableSize )

               NewPos=NewPos%H->TableSize; /* 调整为合法地址 */

       }

       else { /* 偶数次冲突 */

           NewPos=CurrentPos-CNum*CNum/4; /* 增量为-(CNum/2)^2 */

           while( NewPos<0 )

               NewPos+=H->TableSize; /* 调整为合法地址 */

       }

   }

   returnNewPos; /* 此时NewPos或者是Key的位置，或者是一个空单元的位置（表示找不到）*/

}

boolInsert( HashTableH, ElementTypeKey )

{

   PositionPos=Find( H, Key ); /* 先检查Key是否已经存在 */

   if( H->Cells[Pos].Info!=Legitimate ) { /* 如果这个单元没有被占，说明Key可以插入在此 */

       H->Cells[Pos].Info=Legitimate;

       H->Cells[Pos].Data=Key;

       /*字符串类型的关键词需要 strcpy 函数!! */

       returntrue;

   }

   else {

       printf("键值已存在");

       returnfalse;

   }

}

分离链接法的散列表实现

#define KEYLENGTH 15                   /* 关键词字符串的最大长度 */

typedefcharElementType[KEYLENGTH+1]; /* 关键词类型用字符串 */

typedefintIndex;                     /* 散列地址类型 */

/******** 以下是单链表的定义 ********/

typedefstructLNode*PtrToLNode;

structLNode {

   ElementTypeData;

   PtrToLNodeNext;

};

typedefPtrToLNodePosition;

typedefPtrToLNodeList;

/******** 以上是单链表的定义 ********/

typedefstructTblNode*HashTable; /* 散列表类型 */

structTblNode {   /* 散列表结点定义 */

   intTableSize; /* 表的最大长度 */

   ListHeads;    /* 指向链表头结点的数组 */

};

HashTableCreateTable( intTableSize )

{

   HashTableH;

   inti;

   H= (HashTable)malloc(sizeof(structTblNode));

   /* 保证散列表最大长度是素数，具体见代码5.3 */

   H->TableSize=NextPrime(TableSize);

   /* 以下分配链表头结点数组 */

   H->Heads= (List)malloc(H->TableSize*sizeof(structLNode));

   /* 初始化表头结点 */

   for( i=0; i<H->TableSize; i++ ) {

        H->Heads[i].Data[0] ='\0';

        H->Heads[i].Next=NULL;

   }

   returnH;

}

PositionFind( HashTableH, ElementTypeKey )

{

   PositionP;

   IndexPos;

   

   Pos=Hash( Key, H->TableSize ); /* 初始散列位置 */

   P=H->Heads[Pos].Next; /* 从该链表的第1个结点开始 */

   /* 当未到表尾，并且Key未找到时 */

   while( P&&strcmp(P->Data, Key) )

       P=P->Next;

   returnP; /* 此时P或者指向找到的结点，或者为NULL */

}

boolInsert( HashTableH, ElementTypeKey )

{

   PositionP, NewCell;

   IndexPos;

   

   P=Find( H, Key );

   if ( !P ) { /* 关键词未找到，可以插入 */

       NewCell= (Position)malloc(sizeof(structLNode));

       strcpy(NewCell->Data, Key);

       Pos=Hash( Key, H->TableSize ); /* 初始散列位置 */

       /* 将NewCell插入为H->Heads[Pos]链表的第1个结点 */

       NewCell->Next=H->Heads[Pos].Next;

       H->Heads[Pos].Next=NewCell;

       returntrue;

   }

   else { /* 关键词已存在 */

       printf("键值已存在");

       returnfalse;

   }

}

voidDestroyTable( HashTableH )

{

   inti;

   PositionP, Tmp;

   

   /* 释放每个链表的结点 */

   for( i=0; i<H->TableSize; i++ ) {

       P=H->Heads[i].Next;

       while( P ) {

           Tmp=P->Next;

           free( P );

           P=Tmp;

       }

   }

   free( H->Heads ); /* 释放头结点数组 */

   free( H );        /* 释放散列表结点 */

}

11.4 散列表的性能分析

1. 平均查找长度(ASL)用来度量散列表查找效率：成功、不成功

1. 成功：查找的元素再散列表里
   
2. 不成功：查找的元素不在散列表里
   

2. 关键词的比较次数，取决于产生冲突的多少。影响产生充裕多少有以下三个因素：

1. 散列函数是否均匀(不均匀的话冲突会多，性能就会差)
   
2. 处理冲突的方法
   
3. 散列表的装填因子α(装了多少元素，装的元素少那么冲突少。装的元素多则冲突多)
   

分析：不同冲突处理方法、装填因子对效率的影响

1. 线性探测法的查找性能
   可以证明，线性探测法的期望探测次数满足下列公式：
   网络异常，图片无法展示

   |
   
   

对于线性探测，如果当前装填因子值为0.654321, 此时不成功情况下的期望探测次数小于成功情况下的期望探测次数。错误

2. 平方 探测法和双散列探测法的查找性能
   可以证明，平方探测法和双散列探测法探测次数 满足下列公式：
   网络异常，图片无法展示

   |
   
   
   网络异常，图片无法展示

   |
   
   ASCu:成功ASLs：失败
   

期望探测次数与装填因子α的关系

横坐标：装填因子α

纵坐标：期望探测次数

当装填因子α＜0.5的时候，各种探测法的期望探测次数都不大，也比较接近

合理的最大装入因子α应该不超过0.85(对线性探测来说)

3. 分离链接法的查找性能
   所有地址链表的平均长度定义成装填因子α，α有可能超过1
   不难证明：其期望探测次数p为：
   网络异常，图片无法展示

   |
   
   
   网络异常，图片无法展示

   |
   
   

总结

哈希查找(散列查找)特点

选择合适的h(key)，散列法的查找效率期望是常数O(1)，它几乎与关键词的空间的大小n无关！也适合于还建瓷直接比较计算机大的问题

优点：

1. 不像搜索树一样或者平衡二叉树一样，他的查找基本上是跟问题的规模有关系。所以不发生冲突的话基本上是一次成功
   

特点：

1. 跟问题规模无关，是一个常量时间
   
2. 散列查找在很多情况下，用于字符串的管理(例如web地址名关键词搜索这种字符串管理)，关键词查找
   
3. 它是以较小的α为前提。因此，散列方法是一个以空间换时间
   
4. 散列方法的存储对关键字是随机的，不便于顺序查找关键字，也不适合于范围查找，或最大值最小值查找
   

开放地址法

优：散列表是一个数组，存储效率高，随机查找

缺：散列表有"聚集"现象

分离链法

优：关键字删除不需要"懒惰删除"法，从而没有存储"垃圾"

缺：散列表是顺序存储和链式存储的结合，链表部分的存储效率和查找效率都比较低

太小的α可能导致空间浪费，大的α又将付出更多的时间代价。不均匀的链表长度导致时间效率的严重下降

11.5 应用实例：词频统计

【例】给定一个英文文本文件，统计文件中所有单词出现的频率，并输出词频最大的前10%的单词及其词频。

       假设单词字符定义为大小写字母、数字和下划线，其它字符均认为是单词分隔符，不予考虑。

【分析】关键：对新读入的单词在已有单词表中查找，如果已经存在，则将该单词的词频加1，如果不存在，则插入该单词并记词频为1。

如何设计该单词表的数据结构才可以进行快速地查找和插入？散列表

intmain(){

   intTableSize=10000;//散列表的估计大小

   intwordcount=0,length;

   HashTableH;

   ElementTypeword;

   FILE*fp;

   chardocument[30] ="HarryPotter.txt";//要被统计词频的文件名

   H=InitializeTable( TableSize );//建立散列表(也就是初始化散列表)

   if((fp=fopen(document,"r")) ==NULL) FatalError("无法打开文件!\n");

   while(!feof(fp)){//对文件进行处理，读到不是字母跟数字或者下划线而是分隔符的话，那就返回，获得到一个完整的word

       length=GetAWord(fp,word);//从文件中读取一个单词

       if(length>3){//只考虑适当长度的单词

           wordcount++;//统计文件中单词总数

           InsertAndCount(word,H);//插入哈希表

           //InsertAndCount这个函数作用：到哈希表里去找这个元素单词在不在，不在就插入，如果在就词频加1

       }

   }

   fclose(fp);

   printf("该文档共出现%d个有效单词,"，wordcount);

   Show(H,10.0/100);//显示词频前10%的所有单词

   //Show一共两个参数，一个是我们的散列表，另外一个是我们的要求词频前10%

   //这个函数一共做4件事情：1.统计最大词频;2.用一组数统计从1到最大词频的单词数;3.计算前10%的词频应该是多少;4.输出前10%词频的单词

   DestroyTable(H);//销毁散列表

   return0;

}