散列查找思维脑图思维导图

生杀予夺

2023-12-08

浏览量: 9

散列查找

散列函数

处理冲突

处理冲突，常见散列函数等相关内容讲解

树图思维导图提供《散列查找思维脑图》在线思维导图免费制作，点击“编辑”按钮，可对《散列查找思维脑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：40310a455d6a16ad156711c7ad39a3b4

思维导图大纲

概念

散列表（Hash Table）

又称哈希表，是通过将查找码按选定的哈希函数和解决冲突的方法，把结点按查找码转换为地址进行存储的线性表

哈希方法的关键是：选择好的哈希函数和处理冲突的方法

基本思想：用关键字的值决定数据元素的存储地址

散列（哈希）函数

建立“关键字”和“存储地址”的联系：Addr = H(key)

同义词

不同关键字通过散列函数映射到同一个值

冲突

通过散列函数确定的位置已经存放了其他元素

装填因子α

表中记录数/散列表表长

越大越可能冲突

影响查找效率、平均查找长度ASL，且ASL与表长无关

常见散列函数

除留余数法

H(key) = key % p，p是不大于表长的质数

直接定址法

H(key) = key or H(key) = a*key + b

数字分析法

选取数码分布较为均匀的若干位作为散列地址

平方取中法

取关键字平方值的中间几位作为散列地址

选取标准

必须能映射到有限的范围且<表长

如H(key) = key /n，不能当散列函数

映射与查找结果必须一一对应

如H(key) = (key + random(n)) % n，由于随机数的存在，查找时不能确定值

尽可能均匀地散列到各个地址，减少冲突

最好有好的解决冲突方法，且计算哈希函数简单高效

处理冲突

拉链法（链地址法）

关键字为同义词的记录存储在同一链表中，凡是散列地址为i的记录均插在以H[i]为头指针的链表中。

一定不会发生“聚集”（堆积）现象，不受表长限制，插入删除都很方便，称为开散列表，下一个为闭散列表

开放定址法

思想

“聚集”（堆积）现象

同义词之间or 非同义词之间发生冲突

直接影响平均查找长度ASL

线性探测法

di = 0，1，2…m-1

就是冲突之后向后找第1个空闲位置，查找时冲突后一步一步向后找

极易产生“聚集（堆积）”现象

同义词在散列表中不一定相邻，查找成功时探测过的不一定是同义词

K个同义词填入散列表，至少要K(K+1)/2次探测

注意点

查找同义词直到碰到空地址，如果走到头还没空，循环从头走！

平方探测法

di = 0^2，1^2，-1^2，2^2，-2^2…

只有散列表长度m是可以表示为4j+3的素数才可以探测全部位数

相比线性探测不易产生“聚集（堆积）”现象

负数取模：-3%27 = 24

伪随机探测法

di = 一个伪随机序列

不易“聚集（堆积）”

再散列法

在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞

不易“聚集（堆积）”

建立公共溢出区

设H[0……m-1]为基本表，凡是关键字为同义词的记录，都填入溢出区O[0……m-1]

删除操作

拉链法

直接物理删除

开放定址法

不能物理删除，只能做删除标记

该地址可能是该记录同义词查找路径上的地址，物理删除查找时碰到空地址就认为查找失败

计算ASL成功与ASL失败

ASL成功

线性探测法

∑对各关键字散列后在表中找到其需要的比较次数（即各个非空位冲突次数+1） / 关键字个数

拉链法

可以同上

也可以分层求：（第1层结点数 * 1 + 第2层结点数 * 2 + ……） / 关键字个数

ASL失败

设散列函数H = key mod p

线性探测法

对p之前所有位置：

∑从各个位置算起，向后走到第1个空位的比较次数（包括空位） / p

思想：ASL失败 = ∑映射到[0,p-1]区间的查找次数 / p

而映射到i的比较次数 = 从i开始一路查找到第1个空位（包括与空位的比较）

拉链法

一般情况不包括与空指针的比较

∑各个链表从头到尾比较次数（与空指针一般不算一次比较） / p

如果一个数被映射到某一链表，遍历完该链表依然没有找到，就失败了

举例说明

拉链法

ASL成功与ASL失败，此处不包括与空指针的比较

线性探测法

ASL成功与ASL失败，尤其注意ASL失败，在7断开，只看7之前

未名湖案件思维导图

Gloria

2.34

树图思维导图提供《未名湖案件思维导图》在线思维导图免费制作，点击“编辑”按钮，可对《未名湖案件思维导图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：474dd24f7a220bf223a707ffee46939e

安保公司思维脑图思维导图

U170314672

3.76

树图思维导图提供《安保公司思维脑图》在线思维导图免费制作，点击“编辑”按钮，可对《安保公司思维脑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：a52dd3bb37d47db399507e43ac4ea1ed

思维导图模板

IT互联网

产品结构

正文

相似思维导图模版

Python金融大数据分析与应用教学思维导图

2024-03-05 09:45:49

思维导图模版推荐

近代设计（15世纪初期-1769年）思维导图

2023-12-08 15:22:07

发展汉语初级综合I （篇1）思维导图

2023-12-08 15:07:05

首页

我的文件

我的团队

个人中心

﻿散列查找思维脑图思维导图

思维导图大纲

相关思维导图模版

﻿概念

﻿常见散列函数

﻿处理冲突

﻿删除操作

﻿计算ASL成功与ASL失败

相似思维导图模版

思维导图模版推荐

散列查找思维脑图思维导图

概念

常见散列函数

处理冲突

删除操作

计算ASL成功与ASL失败