11.3.6 分离链接法(Separate Chaining)
将相应位置上有冲突的所有关键词存储在同一单链表中
^表示空指针
网络异常，图片无法展示
|
链表实现
typedef struct ListNode*Position,*List; struct ListNode{ ElementType Element; Position Next;//把Next分量分给P，P是下方代码块的一个指针，指向单项链表的第一个元素 }; typedef struct HashTbl*HashTable; struct HashTbl{ int TableSize; List TheLists; };
Position Find(ElementType Key,HashTable H)//哈希表来表示 { Position P; int Pos; 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; return P; }
网络异常，图片无法展示
|
创建开放地址法的散列表
#define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */ typedef int ElementType; /* 关键词类型用整型 */ typedef int Index; /* 散列地址类型 */ typedef Index Position; /* 数据所在位置与散列地址是同一类型 */ /* 散列单元状态类型，分别对应：有合法元素、空单元、有已删除元素 */ typedef enum { Legitimate, Empty, Deleted } EntryType; typedef struct HashEntry Cell; /* 散列表单元类型 */ struct HashEntry{ ElementType Data; /* 存放元素 */ EntryType Info; /* 单元状态 */ }; typedef struct TblNode *HashTable; /* 散列表类型 */ struct TblNode { /* 散列表结点定义 */ int TableSize; /* 表的最大长度 */ Cell *Cells; /* 存放散列单元数据的数组 */ }; int NextPrime( int N ) { /* 返回大于N且不超过MAXTABLESIZE的最小素数 */ int i, 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; /* 否则试探下一个奇数 */ } return p; } HashTable CreateTable( int TableSize ) { HashTable H; int i; H = (HashTable)malloc(sizeof(struct TblNode)); /* 保证散列表最大长度是素数 */ H->TableSize = NextPrime(TableSize); /* 声明单元数组 */ H->Cells = (Cell *)malloc(H->TableSize*sizeof(Cell)); /* 初始化单元状态为“空单元” */ for( i=0; i<H->TableSize; i++ ) H->Cells[i].Info = Empty; return H; }
平方探测法的查找与插入
Position Find( HashTable H, ElementType Key ) { Position CurrentPos, NewPos; int CNum = 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; /* 调整为合法地址 */ } } return NewPos; /* 此时NewPos或者是Key的位置，或者是一个空单元的位置（表示找不到）*/ } bool Insert( HashTable H, ElementType Key ) { Position Pos = Find( H, Key ); /* 先检查Key是否已经存在 */ if( H->Cells[Pos].Info != Legitimate ) { /* 如果这个单元没有被占，说明Key可以插入在此 */ H->Cells[Pos].Info = Legitimate; H->Cells[Pos].Data = Key; /*字符串类型的关键词需要 strcpy 函数!! */ return true; } else { printf("键值已存在"); return false; } }
分离链接法的散列表实现
#define KEYLENGTH 15 /* 关键词字符串的最大长度 */ typedef char ElementType[KEYLENGTH+1]; /* 关键词类型用字符串 */ typedef int Index; /* 散列地址类型 */ /******** 以下是单链表的定义 ********/ typedef struct LNode *PtrToLNode; struct LNode { ElementType Data; PtrToLNode Next; }; typedef PtrToLNode Position; typedef PtrToLNode List; /******** 以上是单链表的定义 ********/ typedef struct TblNode *HashTable; /* 散列表类型 */ struct TblNode { /* 散列表结点定义 */ int TableSize; /* 表的最大长度 */ List Heads; /* 指向链表头结点的数组 */ }; HashTable CreateTable( int TableSize ) { HashTable H; int i; H = (HashTable)malloc(sizeof(struct TblNode)); /* 保证散列表最大长度是素数，具体见代码5.3 */ H->TableSize = NextPrime(TableSize); /* 以下分配链表头结点数组 */ H->Heads = (List)malloc(H->TableSize*sizeof(struct LNode)); /* 初始化表头结点 */ for( i=0; i<H->TableSize; i++ ) { H->Heads[i].Data[0] = '\0'; H->Heads[i].Next = NULL; } return H; } Position Find( HashTable H, ElementType Key ) { Position P; Index Pos; Pos = Hash( Key, H->TableSize ); /* 初始散列位置 */ P = H->Heads[Pos].Next; /* 从该链表的第1个结点开始 */ /* 当未到表尾，并且Key未找到时 */ while( P && strcmp(P->Data, Key) ) P = P->Next; return P; /* 此时P或者指向找到的结点，或者为NULL */ } bool Insert( HashTable H, ElementType Key ) { Position P, NewCell; Index Pos; P = Find( H, Key ); if ( !P ) { /* 关键词未找到，可以插入 */ NewCell = (Position)malloc(sizeof(struct LNode)); 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; return true; } else { /* 关键词已存在 */ printf("键值已存在"); return false; } } void DestroyTable( HashTable H ) { int i; Position P, 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 散列表的性能分析
- 平均查找长度(ASL)用来度量散列表查找效率：成功、不成功
- 成功：查找的元素再散列表里
- 不成功：查找的元素不在散列表里
- 关键词的比较次数，取决于产生冲突的多少。影响产生充裕多少有以下三个因素：
- 散列函数是否均匀(不均匀的话冲突会多，性能就会差)
- 处理冲突的方法
- 散列表的装填因子α(装了多少元素，装的元素少那么冲突少。装的元素多则冲突多)
分析：不同冲突处理方法、装填因子对效率的影响
- 线性探测法的查找性能
可以证明，线性探测法的期望探测次数满足下列公式：网络异常，图片无法展示|
网络异常，图片无法展示
|
对于线性探测，如果当前装填因子值为0.654321, 此时不成功情况下的期望探测次数小于成功情况下的期望探测次数。错误
- 平方 探测法和双散列探测法的查找性能
可以证明，平方探测法和双散列探测法探测次数 满足下列公式：网络异常，图片无法展示|网络异常，图片无法展示|
ASCu:成功 ASLs：失败
期望探测次数与装填因子α的关系
横坐标：装填因子α
纵坐标：期望探测次数
当装填因子α＜0.5的时候，各种探测法的期望探测次数都不大，也比较接近
合理的最大装入因子α应该不超过0.85(对线性探测来说)
网络异常，图片无法展示
|
- 分离链接法的查找性能
所有地址链表的平均长度定义成装填因子α，α有可能超过1
不难证明：其期望探测次数p为：网络异常，图片无法展示|网络异常，图片无法展示|
总结
哈希查找(散列查找)特点
选择合适的h(key)，散列法的查找效率期望是常数O(1)，它几乎与关键词的空间的大小n无关！也适合于还建瓷直接比较计算机大的问题
优点：
- 不像搜索树一样或者平衡二叉树一样，他的查找基本上是跟问题的规模有关系。所以不发生冲突的话基本上是一次成功
特点：
- 跟问题规模无关，是一个常量时间
- 散列查找在很多情况下，用于字符串的管理(例如web地址名关键词搜索这种字符串管理)，关键词查找
- 它是以较小的α为前提。因此，散列方法是一个以空间换时间
- 散列方法的存储对关键字是随机的，不便于顺序查找关键字，也不适合于范围查找，或最大值最小值查找
开放地址法
优：散列表是一个数组，存储效率高，随机查找
缺：散列表有"聚集"现象
分离链法
优：关键字删除不需要"懒惰删除"法，从而没有存储"垃圾"
缺：散列表是顺序存储和链式存储的结合，链表部分的存储效率和查找效率都比较低
太小的α可能导致空间浪费，大的α又将付出更多的时间代价。不均匀的链表长度导致时间效率的严重下降
11.5 应用实例：词频统计
【例】给定一个英文文本文件，统计文件中所有单词出现的频率，并输出词频最大的前10%的单词及其词频。 假设单词字符定义为大小写字母、数字和下划线，其它字符均认为是单词分隔符，不予考虑。 【分析】关键：对新读入的单词在已有单词表中查找，如果已经存在，则将该单词的词频加1，如果不存在，则插入该单词并记词频为1。 如何设计该单词表的数据结构才可以进行快速地查找和插入？散列表
int main(){ int TableSize = 10000;//散列表的估计大小 int wordcount = 0,length; HashTable H; ElementType word; FILE*fp; char document[30] = "HarryPotter.txt";//要被统计词频的文件名 H = Initialize Table( 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);//销毁散列表 return 0; }
小白专场[陈越]：电话聊天狂人-C语言实现
小白-PM.1 题意理解与解法分析
所有电话号码统计一下，打电话或者接电话的总次数是最多的，那这个人就叫做电话聊天狂人
网络异常，图片无法展示
|
解法1：-排序
第1步：读入最多2×10五次方个电话号码，每个号码存为长度为11的字符串
第2步：按字符串非递减顺序排序
第3步：扫描有序数组，累计同号码出现的次数，并且更新最大次数
优势：编程简单快捷
缺点：如果这是在现实应用场合，这些号码不是一次性出现给你的，而是每天没分每秒的不断的在进来，每时每刻我们都可能被停下来问这个聊天狂人是谁。那每次都需要做一个NlogN的排序，要做N次这种事情，所以整个算法的复杂度就变成了N2logN
所以这个算法不好拓展解决动态插入的问题
方法2：-直接映射
为什么是2x10的10次方个单位，因为每个电话有11位，而第一位都是1，把1排除掉
网络异常，图片无法展示
|
优势：编程简单快捷，动态插入快
缺点：下标超过了unsigned long，因为我们平常用到的最长长度的是10位的
直接映射需要存储
个短整型数字，大约是多少字节空间？差不多40GB，
网络异常，图片无法展示
|
我们需要扫描多少个单位才能找到我们需要的那个电话狂人?
=>为了要找2x10的五次方个号码，必须要扫描2x10的10次方个单元，太浪费啦
解法3-带智商的散列
注意：散列表的头节点的个数一共比2N要略大一点
网络异常，图片无法展示
|
小白-PM.2 程序框架搭建
int main() { 创建散列表; 读入号码插入表中; 扫描表输出狂人; return 0; }
int main() { int N,i; ElementType Key;//声明这个为了配合我们HashTable里面声明的类型 HashTable H; scanf("%d",&N); H = CreateTable(N*2);//创建一个散列表 for(i=0;i<N;i++){ scanf("%s",Key);Insert(H,Key);//每次读进来一个号码我把它存在key这个字符串里面，然后把它这个字符串插到表里面 scanf("%s",Key);Insert(H,Key);//每次读入进来的是一对 } ScanAndOutput(H);//ScanAndOutput是自己取的名字 DestoryTable(H);//HashTable的空间要记得释放掉，写在DestoryTable函数里 return 0; }
创建表需要的流程
网络异常，图片无法展示
|
要调用插入函数的话肯定会用到其他两个函数，一个是散列函数Hash，另一个是要找到合适的位置把它插入,Find
ScanAndOutput要做的事情：
网络异常，图片无法展示
|
小白-PM.3 输出狂人
void ScanAndOutput( HashTable H) { int i,MaxCnt = PCnt = 0; ElementType MinPhone; List Ptr; MinPhone[0] = '\0';//最小电话号码初始化为一个空的字符串 for(i=0;i<H->TableSize;i++){//扫描链表 Ptr = H->Heads[i].Next; while(Ptr){ if(Ptr->Count >MaxCnt){//更新最大通话次数 MaxCnt = Ptr->Count; strcpy(Minphone,Ptr->Data);//狂人的电话号码copy到我们将要输出的最小的电话号码里 PCnt = 1;//最狂的只能有一个，初始化次数 } else if(Ptr->Count == MaxCnt ){//狂人不止一个的情况，并列的狂人，最大通话次数一样 PCnt ++;//狂人计数 if(strcmp(Minphone,Ptr->Data)>0)//Ptr->Data>0意味着前面号码大后面号码小，那我们就要把最小号码复制到下方这个更新字符串里面去 strcpy(Minphone,Ptr->Data);//更新狂人的最小手机号码 } Ptr = Ptr->Next; } } printf("%s %d",MinPhone,MaxCnt);//输出一个是最小的电话号码，另一个是记录这个最大的通话次数 id(PCnt > 1) printf("%d",PCnt);//狂人如果大于1的话我还得把这个统计数据输出出来 printf("\n"); }
小白-PM.4 模块的引用与裁剪
网络异常，图片无法展示
|
#define KEYLENGTH 11//关键词字符串的最大长度 //关键词类型用字符 typedef char ElementType[KEYLENGTH+1];//长度要加1是因为在C语言中，里面字符串的结尾还占了一个位置 typedef int Index;//散列地址类型 //分离链接法的部分 typedef struct LNode *PtrToLNode; struct LNode{ ElementType Data;//电话号码 PtrToLNode Next;//指向下一个节点的指针 int Count;//计数器，我们定义为一个整型的Count }; typedef PtrToLNode Position; typedef PtrToLNode List; typedef struct TblNode *HashTable; struct TblNode{//散列表结点定义 int TableSize;//表的最大长度 List Heads;//指向链表头结点的数组 }
NextPrime模块
#define MAXTABLESIZE 1000000 int NextPrime(int N) {/*返回大于N且不超过AXTABLESIZE的最小素数*/ int i,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;//否则试探下一个奇数 } return p; } HashTable CreateTable( int TableSize ) { HashTable H; int i; H = (HashTable)malloc(sizeof(struct TblNode)); H->TableSize = NextPrime(TableSize); H->Heads = (List)malloc(H->TableSize*sizeof(struct LNode)); for( i = 0;i < H->TableSize; i++){ H->Heads[i].Data[0] = '\0';H->Heads[i].Next = NULL; H->Heads[i].Count = 0;//头节点定义为0，虽然不写也没关系，它本身是一个空节点。但写上是个好习惯，表示这个节点里所有的变量都有一个初始化的值，不要有个节点空着的不知道这是干嘛的 } return H; } int Hash(int Key,int P)//Key是整数，当我们把它传给这个Hash函数去处理的时候我们应该已经把那电话号码后五位截取出来了并且把它变成一个整数了，而不是直接把11位电话号码传进来 { //除留余数法，散列函数 return Key%P; }
原始的Find函数
#deine MAXD 5//参与散列映射计算的字符个数，从后往前数5位 Position Find( HashTable H,ElementType Key ) { Position P; Index Pos; //初始散列位置 Pos = Hash(Key,H->TableSize );//在原始的这个是直接把Key传到Hash函数里面去算的 //但在我们这个问题里就不能这么做，在Key传进去之前得先把它后五位截出来变成一个整数，变成 Pos = Hash(atoi(Key+KEYLENGTH-MAXD),H->TableSize)//把数传给atoi转化为整数再把整数传给散列函数去计算 P = H->Heads[Pos].Next;//从该链表的第一个结点开始 //当未到表尾，并且Key未找到时 while(P && strcmp(P->Data,Key)) P = P->Next; return P;//此时P或者指向找到的结点，或者为NULL }
插入函数
bool Insert(HashTable H,ElementType Key) { Position P,NewCell; Index Pos; P = Find(H,Key); if(!P){//关键词未找到，可以插入 NewCell = (Position)malloc(sizeof(struct LNode)); strcpy(NewCell->Data,Key); //初始散列位置 //Pos = Hash(Key,H->TableSize);这里进行改动 NewCell->Count = 1;//当我们要插入新的电话号码的时候，这个新的电话号码节点的计数器要初始化为1 Pos = Hash(atoi(Key+KEYLENGTH-MAXD),H->TableSize); //将NewCell插入为H->Heads[Pos]链表的第一个结点 NewCell->Next = H->Heads[Pos].Next; H->Heads[Pos].Next = NewCell; return true; } else{//关键词已存在 //printf("键值已存在");//表示我找到了这个电话号码，但在实际显示中我们不能显示这一行，需要修改一下 P->Count++;//找到这个电话号码计数器要加1，表示我们多打了一次电话或多接了一次电话 return false; } }
