数据结构 第8章-跳表和散列表.ppt

1、引 言 集合在线性表和树表的表示中，元素在结构中的位置与元素的关键字间无直接确定关系，搜索时需通过关键字的一系列比较完成。 本节的散列表，在元素的关键字与其在结构中的位置建立直接联系，以实现直接快速搜索。,第8章 跳表和散列表,数据结构,DATA STRUCTURE,内容提要 1.介绍散列技术 2.讨论几种常用的散列函数 3.讨论几种解决冲突的方法,8.3 散列表,课堂提要 第8章 跳表和散列表 8.3 散列表 8.3.1 散列技术 8.3.2 散列函数 8.3.3 拉链法 8.3.4 开地址法 8.3.5 线性探查法 8.3.6 其他开地址法,在线性表、二叉排序树、B-树中，元素在存储 结构

2、中的位置与元素的关键字值之间不存在直接的 确定关系。搜索时，需进行一系列关键 字值间的比较。 散列表提供了一种完全不同的存储 和搜索方式：将关键字值映射到表中的 某个位置来存储元素。则通过给定的关 键字值，可以直接计算得到元素的存储 位置。,课堂提要 第8章 跳表和散列表 8.3 散列表 8.3.1 散列技术 8.3.2 散列函数 8.3.3 拉链法 8.3.4 开地址法 8.3.5 线性探查法 8.3.6 其他开地址法,8.3.1 散列技术,在元素的存储位置和关键字值之间建立一种对应 关系h，把关键字值映射到表中的某个位置，即： h(key)=Loc(key) Loc(key)表示关键字值为

3、key的 元素的存储地址。 因此，在理想状态下，可以不进 行任何关键字值的比较，直接通过对 应关系h找到该元素。,散列函数：反映元素的关键字(key) 与其存储位置(loc)之间的关系的函 数(h)，即： h(key)loc(key) 散列表(hash,哈希表)：用散列函数 建立起来的表。 散列表是一种表示集合的数据结构。,课堂提要 第8章 跳表和散列表 8.3 散列表 8.3.1 散列技术 8.3.2 散列函数 8.3.3 拉链法 8.3.4 开地址法 8.3.5 线性探查法 8.3.6 其他开地址法,课堂提要 第8章 跳表和散列表 8.3 散列表 8.3.1 散列技术 8.3.2 散列函数

4、 8.3.3 拉链法 8.3.4 开地址法 8.3.5 线性探查法 8.3.6 其他开地址法,冲突：key1key2,但h(key1)=h(key2)的现象。 同义词：对同一散列函数，具有相同h值的关键字。 上式中key1和key2即为同义词。 显然不允许冲突！,能否避免冲突？不现实 如上例：设计H(key)=各字母编码序列 使keyH(key) （山西，陕西除外） H(SHANXI)=190801142409 但是，关键字变化范围广泛，比地址集合大得多，地址空间有限V(0.30)，而且找一一对应的h很耗费时间，故一般不这样做。,分析上表：h2(key)冲突少于h1(key)， 说明冲突与散列

5、函数有关。 散列函数是一个压缩映象，冲突不可避免！ 可以做到的是： 1、选择“好”的h,尽量减少冲突。 2、若发生冲突，如何处理？用冲突处理技术。,课堂提要 第8章 跳表和散列表 8.3 散列表 8.3.1 散列技术 8.3.2 散列函数 8.3.3 拉链法 8.3.4 开地址法 8.3.5 线性探查法 8.3.6 其他开地址法,8.3.2 散列函数,“好”的散列函数： (1)均分布，少冲突； (2)计算简便，快速。,均分布：元素经散列函数映象到 散列表中的任何位置是等概率的。 下面介绍几种目前比较通用的散 列函数。,h(key)=key mod M (M为散列表表长) 一般取不超过M的素数P

6、会更好。 例：M=1000,P=997 关键字 内部编码 散列地址 KEYA 11052501 756 KEYB 11052502 757 AKEY 01110502 864 BKEY 02110502 873 散列地址相近，可以先将关键字的内部编码循环移若干位后，再%。,1、除留余数法,h(key)=(key)2的中间若干位k 其中：位数k应满足：10k-1n10k ，n为集合中元素个数。 例：n=765, k取3。 103-1765103 , 故k=3, 即取k=3。 关键字 (内部编码）2 散列地址 KEYA 122157778355001 778 KEYB 12215780046000

7、4 800 AKEY 001233265775625 265 BKEY 004454315775625 315,2、平方取中法,把关键字值自左到右，分成位数相等的几部分，每一部分 位数与散列表地址的位数相同，只有最后一部分的位数可 以短些。把这些部分的数据叠加起来，得到该关键字的散 列地址。 （1）移位法：把各部分最后一位对齐相加 （2）分界法：沿各部分的分界来回折叠，然后对齐相加,3、折叠法,例：设关键字key=12320324111220，散列地址取3位， 则key被划分位5段： 123 203 241 112 20,适用于关键字很长的情况,取分布均匀的若干位。 例如，一组关键字如下： 位

8、 1 2 3 4 5 6 关键字 9 4 2 1 4 8 9 4 2 3 5 6 9 4 2 5 7 2 9 4 2 6 6 4 9 4 3 3 9 5 9 4 2 4 7 2 9 4 2 7 3 1 9 4 1 2 8 7 9 4 2 3 4 5 通过分析，可以看出第4、5、6位分布均匀，故取第4、5、6位这三位为散列函数的值。,4、数字分析法,冲突是不可避免的。当冲突发生时，必须对冲突进行处理。 处理冲突的方法有： （1）拉链法 （2）线性开地址法 （3）二次探查法 （4）双散列法,课堂提要 第8章 跳表和散列表 8.3 散列表 8.3.1 散列技术 8.3.2 散列函数 8.3.3 拉链

9、法 8.3.4 开地址法 8.3.5 线性探查法 8.3.6 其他开地址法,将所有具有同义词的关键字建立一个单链表，单链表可以按升序排列。所有单链表的头指针存入一数组中。,0 1 2 3 4 5,11,36,16,33,55,66,69,49,82,散列函数采用除留余数法，除数取11。H(key)=key % 11 有n个元素的散列表，其每个单链表的平均长度为n/M。,8.3.3 拉链法,8.3.4 开地址法,基本思想：从h(key)开始，按照某种规定的次序探查 允许插入新元素的空位置。 基位置：h(key) 探查序列：如果h(key)已经被占用，采用解决冲突的 策略，产生不同的需要被检查的位

10、置的序列。 根据生成探查序列的规则的不同，开地址方法有： 1、线性探查法 2、二次探查法 3、双散列法,使用下列线性循环探测序列进行探测，直到某个位置为空时，将关键字为key的元素插入该位置。 h(key),h(key)+1,M-1,0,1,h(key)-1 如下例：（散列函数采用除留余数法，除数取11）,0 1 2 3 4 5 6 7 8 9 10,80,40,65,ht,插入58，24。,0 1 2 3 4 5 6 7 8 9 10,80,40,65,ht,24,58,插入35。,0 1 2 3 4 5 6 7 8 9 10,80,40,65,ht,24,58,35,1、线性探查法,线性开

11、地址法散列表的C+类 Template class HashTable:DynamicSet public: HashTable(int divisor=11); HashTable() delete ht; delete empty; ResultCode Search(T /标志域 ,线性开地址法散列表的构造函数 template HashTable :HashTable(int divitor) M=divitor; ht=new TM; empty=new boolM; int i; for(i=0; iM; i+) emptyi=true; /标志位空 for(i=0; iM; i+

12、) hti=NeverUsed;/空值 ,线性探查散列表的搜索 搜索思想：从基位置h(key)开始,按照线性循环探查序列 查找该元素。 搜索成功：找到关键字值为key的元素； 搜索失败：1、遇到一个空位置（emptyi=true） 2、回到h(key)（表满） 注意：标志位用于散列表的搜索； 空值用于散列表的插入。,课堂提要 第8章 跳表和散列表 8.3 散列表 8.3.1 散列技术 8.3.2 散列函数 8.3.3 拉链法 8.3.4 开地址法 8.3.5 线性探查法 8.3.6 其他开地址法,template ResultCode HashTable:Find(T /设置首次遇到的空值位置

13、，返回 ,template ResultCode HashTable:Search(T ,线性开地址法散列表的插入 函数探查第一个空值位置，即关键字值为NeverUsed的位置，以便插入新元素。函数Insert首先调用Find函数判定是否存在重复元素或表是否已满。若htb=NeverUsed，则在该处插入元素e，插入成功；否则插入失败。插入失败包括元素重复和表满。,课堂提要 第8章 跳表和散列表 8.3 散列表 8.3.1 散列技术 8.3.2 散列函数 8.3.3 拉链法 8.3.4 开地址法 8.3.5 线性探查法 8.3.6 其他开地址法,程序8.9 线性探查散列表的插入 templat

14、e ResultCode HashTable:Insert(T /表满 ,线性探查散列表的删除,散列表中删除元素的过程 删除58：,58,80,40,65,24,35,若直接删除，后果是什么？,例如：搜索35,遇到空位置，搜索失败！,如何解决？,线性探查散列表的删除 删除时需考虑两点： 1、不能简单清除元素，否则会隔离探查序列后面的元素， 影响搜索； 2、删除后，该元素的位置能够重新使用。 方法：首先搜索该元素，若搜索 成功，则置该位置为空值， 但empty域不作更改！,课堂提要 第8章 跳表和散列表 8.3 散列表 8.3.1 散列技术 8.3.2 散列函数 8.3.3 拉链法 8.3.4

15、开地址法 8.3.5 线性探查法 8.3.6 其他开地址法,解决的办法：为每个元素增加标志域,删除58时，不改变标志位，仍为false，元素处改为 NeverUsed。 搜索终止条件改为：遇到标志位True或回到h(key) 插入时，找到的第1个空位置处，其值为NeverUsed,程序8.10 线性探查散列表的删除 template ResultCode HashTable:Remove(T ,8.3.6 其他开地址法,58,80,40,65,24,35,线性探查法的缺点：易使元素在表中连成一片，使得探查 次数增加，影响搜索效率基本聚焦 改进方法：1、二次探查法 2、双散列法,课堂提要 第8章

16、 跳表和散列表 8.3 散列表 8.3.1 散列技术 8.3.2 散列函数 8.3.3 拉链法 8.3.4 开地址法 8.3.5 线性探查法 8.3.6 其他开地址法,1、二次探查法,二次探测法使用下列探测序列进行探测，直到某个位置 为空时，将关键字为key的元素插入该位置。 h(key),h1(key),h2(key),h2i-1(key),h2i(key),。 探测序列由下列函数得到： h2i-1(key)=(h(key)+i2) % M h2i(key)=(h(key)-i2) % M i=1,2,(M-1)/2 M是表长，应该是4k+3的素数，k是一整数。 i=1， h1(key)=(

17、h(key)+12) % M h2(key)=(h(key)-12) % M i=2, h3(key)=(h(key)+22) % M h4(key)=(h(key)-22) % M,如下例：（散列函数采用除留余数法，除数取11） 即 h(key)=key%11,插入35,h(key)=35%11=2 h1(key)=(h(key)+12)%11=3 h2(key)=(h(key)-12)%11=1,35,插入13,h(key)=13%11=2 h1(key)=(h(key)+12)%11=3 h2(key)=(h(key)-12)%11=1 h3(key)=(h(key)+22)%11=6,

18、13,2、双散列法 二次探测法能改善“线性聚集”，但是当二个关键字散列到同一位置时，则会有相同的探测序列，产生“二次聚集”。双散列法可以避免“二次聚集”。 使用下列探测序列进行探测，直到某个位置为空时，将关键字为key的元素插入该位置。 h1(key),(h1(key)+ h2(key)%M，(h1(key)+ 2h2(key)%M，。 或 hi=(h1(key)+ ih2(key) % M (i=0,1,M-1) h2(key)应该是小于M且与M互质的整数，以保证探测序列能够最多经过M次探测即可遍历表中所有地址。 若M为素数，则可取h2(key)=key % (M-2)+1,例如，h1(key)=key %