导图社区 查找思维导图
查找算法相关知识思维导图,本图的知识包括线性表查找、树表查找以及散列表查找(杂湊法、散列法)--散列表Hash(哈希表)三部分,适用于预习、复习的参照。
栈和队列相关知识学习思维导图,内容涵盖他们的定义及特点、实现方式、分类等知识,适用于预习、复习的参照。
图像分割方法综述思维导图,内容包括传统图像分割方法、性能分析比较与总结、分割网络模型等等,有兴趣的可以看下。
社区模板帮助中心,点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
查找
线性表查找
顺序查找
折半查找
分块查找
树表查找
二叉排序树
平衡二叉树
B-树
B+树
散列表查找(杂湊法、散列法)--散列表Hash(哈希表)
思想:通过对某元素的关键字值进行运算,直接求出元素的地址,即使用关键字到地址的直接转化方式,无需反复比较
术语
散列函数和散列地址——p=H(key)
H:散列函数
p:散列地址
散列表
有限连续的地址空间==常用一维数组,散列地址就是数组下标
用来存储按散列函数计算得到相应散列地址的数据记录
冲突和同义词——key1!=key2而H(key1)=H(key2)
冲突::key1!=key2而H(key1)=H(key2)的现象
同义词:key1与key2互成为同义词
散列函数的构造方法
考虑因素
散列表长度
关键字
长度
分布情况
计算散列函数所需时间
记录查找频率
关键问题--构造散列函数原则
简单:不存在很大的计算量--查找效率低下
均匀:函数值尽量均匀散步在地址空间--保证存储空间有效利用,减少冲突
散列函数实现方法
直接定址法
H(key)=a*key=b
不足
使用中不能提前知道key值集合
适用范围:
提前知道关键码
关键吗集合不大,较为连续且不离散
除留余数法
H(key)=key mod p
p选取不当,导致冲突率上升
优点
最简单、最常用
不要求事先知道关键码的分布
数字分析法
对不同数据进行不同分析,写出合适的H(x)
平方取中法
折叠法
冲突处理方法
开放地址法
链地址法(开散列方法、拉链法)==闭散列表
开散列方法
思路:由关键码得到的散列地址发生冲突,寻找下一个空的散列地址,存入记录
寻找下一个空散列地址的方法
线性探测法
公式:Hi=(H(key)+di)MODm (di=1,2,...,m-1)
堆积现象:非同义词对同一个散列地址争夺现象
二次探测法
公式:Hi=(H(key)+di) (di=1^2,-1^2,2^2,-2^2,...,q^2,-q^2且q<=m/2)
随机探测法
发生冲突时,下一位移量是一个随机数列
公式:Hi=(H(key)+round) (round为随机数)
再hash法
闭散列方法
拉链法
建立公共溢出区
散列表查找方法
缺陷
一般不适合在允许多个记录有同样关键码的情况下使用
消除冲突
不适用于范围查找
查找最大值或者最小值
不可能找到某一范围内的记录