散列查找思维脑图思维导图
处理冲突，常见散列函数等相关内容讲解
树图思维导图提供 散列查找思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 散列查找思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：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之前
相关思维导图模板
树图思维导图提供 职业成长地图思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 职业成长地图思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：0f7b52de05b5dc17d48004ff3a4fb340
树图思维导图提供 辨百草学习单思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 辨百草学习单思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：a2f0a34a73bff04fce8d41cbf3eb9af4
沪公网安备 31011502019485号
上海工商