数据结构之散列查找

散列表

散列表对应的值可称为hash（哈希值）
你可以理解为，散列表就是对应地址的映射，只不过
假设x为地址
g(x)就是对应的哈希值
x一样但是对于的g（x）可能一样这就产生了冲突

那么如何处理冲突呢？

一.拉链法

这样进行查找的话也可以

比如
27先代入对应的函数查hash值
然后去对应的hash表找对应的值
遍历对应位置的链表去对比就ok，如果最后都没有的话，就那个散列表就没有

关于查找长度奥

我们只关心对比关键字的次数
不关心对比空指针奥

比如查79
就需要比对14 1 27 和79
那就是4次

平均查找长度分析（ASL）

查找成功下
ASL成功=行数×对应行元素个数/元素数
或者就是所有元素查找之和/元素个数

最理想情况

就是冲突情况越多，查找效率越低
那么能不能设计一个哈希函数去尽可能减少冲突的发生呢？
这个问题后面讲

查找失败情况下的平均查找长度
查找失败，你肯定也是每一个散列表都访问的
这里我们没有查找成功奥
，所以我们不能以元素个数为分母了
我们要以行数，就是哈希表有多少元素做分母
我们用

从哈希表第0个元素到最后的链表所含关键字个数之和作为分子
就是对应行数要找几个呗，也可以说，关键字的个数就是分子
然后分母就是行数，查找失败就是查找不同的行失败呗
最后就是
ASL（失败）=关键字个数/哈希表中的元素个数

此参数也可叫装填因子
很重要！

常见散列函数（冲突比较少的）

1.除留余树法

质数取模，分布更均匀，冲突更少

2.直接定址法

这种是线性变化是不会产生冲突的，但是使用这种方法如果关键字不连续的话会导致空位较多

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

4.平方取中法

取中间的几位

总结

二.开放定址法

差不多就是数码个意思呢
就是有对应的散列函数
1%13=1
案例来说与数组一是同义词
应该放到数组一的位置上，不过他可以放到数组三的位置上
对应的数组不仅可以接收同义词，也可以接收非同义词
那怎么判断这些对应的数组内到底是哪一个关键字呢？
一般规则接收，Hi=(H(key)+di)%m(表长)
那么这个di怎么知道呢？（i理解为第i次冲突，是对应的一个数的第i此冲突啊，不是相对于散列表而言的，不同的数从d0开始重新算）
用下面三种方法喽

1.线性探索法（重点）

只有发生冲突的时候用Hi公式，没有冲突还是按照H（key）的结果
di=0，1…，m-1

比如这个关键字序列
19，14和23的时候都是d0=0
就相当于遵循对应的散列变化呗
不过在1算的时候就和14对应的结果起了冲突
需要把d0变为d1
H=（1+d1）%15=2
所以1就要到2位置上了

之后就是一个个加呗
然后介绍84和19的冲突了呗
d0变为d1
又和20冲突
d1变为d2往后移两位就没冲突了，ok了放到8好位上

最后变成这样

查找

也是奥

比如你要探查27
正常规则就是27%13=1
看1位置是14
不匹配就根据新规则来呗
d0边d1一直到d3
到四位置的时候匹配了
一共匹配了四次

查找失败的话，与NULL对比的那次查找长度也算
，为什么空白就失败
想想
如果你找21，21就按照那个规则肯定是在84的后面且前面的元素肯定存满了，不可能说中间有空位
中间有空位21就应该在那个位置上
所以只要对比的是空白就是失败

删除操作

不能直接删除


你把1删除了，他往后走一看遇到空白以为查找失败
其实后面有27，不合理

所以其实我们弄一个标记记性表示这个元素是否已经删除

一个小弊端

查找效率分析（ASL平均查找长度）

ASL（成功）=每个元素需要的查找成功长度之和/元素个数

ASL（失败）=每个单元位开始查找需要到空白的长度之和/有几个位置可供开始查找

聚集问题影响查找效率

2.平方探测法

本质上就是di的改变
从原来的0到无穷
到现在的
0 1 -1 4 -4…
0 1平方 -（1平方） 2平方 -（2平方）…

一个小难点m必须是一个可以表示成4j+3的素数，才能探测到所有位置


右边的8不能表示为4j+3的素数
所有经过m次探测以后，不能查到列表的所有元素，反而重复查了4 6 和1位置上的数

这个是数学问题奥，这里可以自己搜一搜

3.伪随机序列法

就是给di赋值一个随机生成的数列，（随机一次就固定了）
和前面的搜查方式差不多

总结

再散列法

总结