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

11.1 散列表

11.1.1 引子：散列的基本思路

C语言变量名必须：

先定义(或者声明)后使用

编译处理时，涉及变量及属性(如：变量类型)的管理：

插入：新变量定义(将变量名及其定义插到我们要管理的这个集合里面去)
查找：变量的引用(在编译的时候，会查找你使用的这个变量是否定义，在根据变量的类型去进行判别看能不能这么使用)

编译处理中对变量管理：

动态查找问题

利用查找树(搜索树)进行变量管理？

两个变量名(字符串)比较效率不高，因为变量名比较比整数的比较要复杂。
整数比较一次比较大小相等就行了，而变量是字符串，需要一个字符一个字符的比过去
是否可以先把字符串转换为数字再处理？这样就是进行比较两个数字的方式了，这就是散列查找

已知的几种查找方法：

顺序查找：要查找的放数组列表，从头到尾慢慢找，效率差
二分查找(静态查找)：从小到大排好然后用二分查找这样，查找效率高
二叉搜索树，平衡二叉树

网络异常，图片无法展示

问题：如何快速搜索到需要的关键词？如果关键词不方便比较怎么办？

查找的本质：已知对象找位置

有序安排对象：全序(典型的二分查找，从小到大排好)，半序(某些关键词之间存在一个秩序，例如查找树，任何一个结点都比左边左子树的所有结点要来得大，比右边右子树的所有结点要来得小，但并不像二分查找一样完全有序)
直接"算出"对象位置：散列

散列查找法的两项基本工作：

计算位置：构造散列函数确定关键词存储位置
解决冲突：应用某种策略解决多个关键词位置相同的问题

时间复杂度几乎是常量：O(1)，即查找时间与问题规模无关！

散列如果在函数的计算方面还有冲突策略提得好，效率就会非常高

11.1.2 什么是散列表

类型名称：符号表(SymbolTable)
数据对象集：符号表是“名字(Name)-属性(Attribute)”对的集合。
操作集：Table∈SymbolTable,Name∈NameType,Attr∈AttributeType
1.SymbolTable InitializeTable(int TableSize )://表的初始化
  创建一个长度为TableSize的符号表；
2.Boolean IsIn(SymbolTable Table,NameType Name)://判别一个对象是不是在这个表里
  查找特定的名字Name是否在符号表Table中；
3.AttributeType Find(SymbolTable Table,NameType Name)://在表里查找属性
  获取Table中指定名字Name对应的属性；
4.SymbolTable Modefy(SymbolTable Table,NameType Name,AttributeType Attr)：//把表中属性改掉
  将Table中指定名字Name的属性修改为Attr;
5.SymbolTable Insert(SymbolTable Table,NameType Name,AttributeType Attr)://在表里插入一个新的对象
  向Table中插入一个新名字Name及其属性Attr;
6、SymbolTable Delete(SymbolTable Table,NameType Name)://从表里删除
  从Table中删除一个名字Name及其属性。
        主要操作：上面的3、5、6

网络异常，图片无法展示

装填因子：散列表在外面这里是个数组，这个数组被充满的程度

冲突的设计：采用二维数组，同一个地址的就放在同一行，有冲突的在所在那行后一列继续放，如图所示：

网络异常，图片无法展示

哈希函数设计：

哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数。
一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。 理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系，使每个关键字和结构中一个唯一的存储位置相对应。

只要不冲突的话效率还是很高的

网络异常，图片无法展示

▣“散列(Hashing)”的基本思想是：
(1)以关键字key为自变量，通过一个确定的函数h(散列函数)，计算出对应的函数值h(key),作为数据对象的存储地址。
(2)可能不同的关键字会映射到同一个散列地址上，即h(keyi）=h(keyj）(当keyi不等于keyj),称为“冲突(Collision)”。---需要某种冲突解决策略

11.2 散列函数的构造方法

11.2.1 数字关键词的散列函数构造

一个"好"的散列函数一般应考虑下列两个因素：

计算简单，以便提高转换速度
关键词对应的地址空间分布均匀，以尽量减少冲突

数字关键词的散列函数构造

直接定址法：取关键词的某个线性函数值为散列地址，即h(key) = a×key+b (a、b为常数)

网络异常，图片无法展示
|
除留余数法(常用)：//其实就是把一个大的整数把它转换成一个小的整数，这个小的整数就相当于散列表里面的地址

散列函数为：h(key) = key mod p

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

数字分析法：分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址

比如：取11位收集号码key的后4位作为地址：散列函数为：h(key)=atoi(key+7) (char*key)

网络异常，图片无法展示
|
int atoi(char*s)：将类似"5678"的字符串转换为整数5678
如果关键词key是18位的身份证号码：

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

折叠法：把关键词分割成位数相同的几个部分，然后叠加

网络异常，图片无法展示
|
平方取中法：

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

如果仅改变56793542的最后一位，观察散列值会有什么变化（原散列值为641）。

请计算一下，按照平方取中法,key为56793543的散列值是多少=652

11.2.2 字符串关键词的散列函数构造

字符关键词的散列函数构造

一个简单的散列函数——ASCII码加和法(ASCII码相加在求个余数)

网络异常，图片无法展示
|
假如每个字符的变化范围在0-127，我们把它∑起来，∑后的值在0-1270之间，而变量名实际上的这种变化是非常多的，如果以很窄的计算结果来对付一个很广的这个变量范围就会使得这样的一个哈希函数很容易产生聚集，所以这不是一个很好的办法

简单的改进——前3个字符移位法

h(key)=(key[0] x 27² + key[1] x 27 + key[2])mod TableSize
这种方法仍然会产生冲突：string、street、strong、structure等等(前三位是一样的)；空间浪费：3000/26³≈30
空间浪费原因：字符一共有26种变化，所以三个字符的变化一共就26的三次方。而前三位一般出现的情况是3000种，而我们实际上考虑到26³去了，通过上面可以知道浪费的空间足足有30倍

好的散列函数——移位法

网络异常，图片无法展示
|
将数值巨大化，采用32进制相乘

网络异常，图片无法展示
|
优化方法：(a32+b) =>((a32+b)32+c)=>(((a32+b)32+c)32+d)

如果直接计算'a'*32^4+'b'*32^3+'c'*32^2+'d'*32+'e'所需要的乘法总次数是4+3+2+1=10次。
采用 ((('a'*32+'b')*32+'c')*32+'d')*32+'e'的计算方法，乘法总次数是多少？
（顺便思考一下两者时间效率的差别）4

Index Hash(const char*Key,int TableSize)
{
    unsigned int h = 0;//散列函数值，初始化为0
    while(*Key != ‘\0’)//位移映射，这里就是值不为空的意思 
        h = ( h << 5 ) + *Key++;//h << 5是左移五位的意思
    return h % TableSize;//最后求余得到地址
}

11.3 冲突处理方法

11.3.1 开放定址法

处理冲突的方法

常用冲突的思路：

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

开放地址法(Open Addressing)

一旦产生了冲突(该地址已有其他元素)，就按某种规则去寻找另一空地址
网络异常，图片无法展示
|
di决定了不同的解决冲突方案：线性探测、平方探测、双散列(三种典型的开放地址法)

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

11.3.2 线性探测

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

网络异常，图片无法展示

会形成聚集现象

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

散列表查找性能分析

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

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

网络异常，图片无法展示

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

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

余数-哈希函数

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

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

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

1%7=8%7=1
2%7=9%7=2

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

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

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

哈希函数（散列函数）

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

散列过程

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

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

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

选择适当的正整数P，以关键码除以P的余数作为散列地址
通常P为小于或等于表长（最好接近）的最小质数或不包含小于 20 质因子的合数

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

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

网络异常，图片无法展示

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

11.3.4 平方探测法(Quadratic Probing)

也可以叫做：二次探测

网络异常，图片无法展示

平方探测法(Quadratic Probing)

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

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

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

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

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

11.3.5 平方探测法的实现

typedef struct HashTbl*HashTable;
struct HashTbl{
    int TableSize;//当前表的实际大小
    Cell*TheCells;//代表自己是一个数组，实际上是一个指针
}H;
HanshTable InitializeTable(int TableSize)
{
    HashTable H;
    int i;
    if( TableSize < MinTableSize ){//判别散列表的大小，太小就没必要做散列，直接放在数组就行了
        Error("散列表太小");
        return NULL;
    }
    //分配散列表
    H = (HashTable)malloc(sizeof(struct HashTbl));//申请空间赋给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;
    return H;
}

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

网络异常，图片无法展示

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

//表的初始化
Position Find(ElementType Key,HashTable H)//平方探测
{
    Position CurrentPos,NewPos;
    int CNum;//记录冲突次数
    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;
        }
    }
    return NewPos;
}

网络异常，图片无法展示

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

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

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

void Insert(ElementType Key,HashTable H)
{
    //插入操作
    Position Pos;
    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)

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

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

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

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

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

11.1 散列表

11.1.1 引子：散列的基本思路

11.1.2 什么是散列表

11.2 散列函数的构造方法

11.2.1 数字关键词的散列函数构造

11.2.2 字符串关键词的散列函数构造

11.3 冲突处理方法

11.3.1 开放定址法

11.3.2 线性探测

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

11.3.4 平方探测法(Quadratic Probing)

11.3.5 平方探测法的实现

双散列探测法(Double Hashing)

再散列(Rehashing)

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

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

11.1 散列表

11.1.1 引子：散列的基本思路

11.1.2 什么是散列表

11.2 散列函数的构造方法

11.2.1 数字关键词的散列函数构造

11.2.2 字符串关键词的散列函数构造

11.3 冲突处理方法

11.3.1 开放定址法

11.3.2 线性探测

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

11.3.4 平方探测法(Quadratic Probing)

11.3.5 平方探测法的实现

双散列探测法(Double Hashing)

再散列(Rehashing)

热门文章

最新文章

相关课程

相关电子书