附录：所有blog的链接

数据结构学习笔记（1）：基本概念
数据结构学习笔记（2）：线性结构
数据结构学习笔记（3-5）：树
数据结构学习笔记（6-8）：图
数据结构学习笔记（9-10）：排序
数据结构学习笔记（11）：散列查找
数据结构学习笔记（12）：综合习题选讲

第十一讲 散列查找

11.1 散列表

已知的几种查找方法：

顺序查找$O(N)$

二分查找（静态查找）$O(1o{g}_{2}N)$

二叉搜索树$O（h）$， $h$为二叉查找树的高度

平衡二叉树$O(lo{g}_{2}N)$

散列查找解决的问题：

快速搜索到需要的关键词。关键词不方便比较。并且是动态查找的情况居多。

查找的本质：在对象中找位置。

思路一：有序安排对象：全序、半序

思路二：直接“算出”对象位置：散列

散列查找法的两项基本工作：

计算位置：构造散列函数确定关键词存储位置；

解决冲突：应用某种策略解决多个关键词位置相同的问题时间复杂度几乎是常量：$O(1)$，即查找时间与问题规模无关！

散列表（哈希表）的抽象数据类型

存放操作：主要注意操作有冲突的时候

查找操作：怎么放进去怎么查找，是一个逆序的过程

装填因子：（Loading Factor）：设散列表空间大小为m，填入表中元素个数是n，则称a=n/m为散列表的装填因子

在没有冲突的情况下，复杂度很小

“散列（Hashing）”的基本思想是：

以关键字key为自变量，通过一个确定的函数$h$（散列函数），计算出对应的函数值$h(key)$，作为数据对象的存储地址。

可能不同的关键字会映射到同一个散列地址上，即$h(ke{y}_i)=h(ke{y}_j)$（当$ke{y}_i\ne ke{y}_j$），称为“冲突（Collision）”。
—需要某种冲突解决策略

11.2 散列函数的构造方法

构造时考虑因素：

1.计算简单，以便提高转换速度；
2.关键词对应的地址空间分布均匀，以尽量减少冲突。

数字关键词的散列函数构造

1.直接定址法

取关键词的某个线性函数值为散列地址，即$h(key)=a\cdot key+b$（$a$、$b$为常数）

2.除留余数法

散列函数为：$h(key)=key \mod \ p $

为了表格均匀一般取素数

一般把$p$取为表格大小

3.数字分析法

分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址

4.折叠法

把关键词分割成位数相同的几个部分，然后叠加

5.平方取中法

字符关键字的散列函数构造

11.3 冲突处理方法

常用处理冲突的思路：

换个位置：开放地址法（Open Addressing）

一旦产生了冲突（该地址已有其它元素），就按某种规则去寻找另一空地址

同一位置的冲突对象组织在一起：链地址法

开放地址法（Open Addressing）

若发生了第$i$次冲突，试探的下一个地址将增加$d$，基本公式是：
$h_i(key)=(h(key)+d)\mathrm{m}\mathrm{o}\mathrm{d}TableSize（1\le i<TableSize）$，

$d_i$决定了不同的解决冲突方案：

线性探测：$d_i=i$

平方探测：$d_i=\pm i^2$

双散列：$d_i=i\ast h_2(key)$

散列表查找性能分析

成功平均查找长度（ASLs）可以用每一个存放位置的冲突次数加一进行计算，表中的关键字一定是在表中的，在查找过程中可能会遇到情况（之前因为冲突所以没有放在应该放的位置，有一定的偏移），持续的在所有的偏移中去找，直到找到这个元素所需要的查找次数。

不成功平均查找长度（ASLu）对于一个不在表中的数需要分情况去判断，首先求出不同情况的$h(key)$，然后按照情况分类，如果有不同的$h(key)$，每一种判断出表中没有这个元素所需要的判断次数

线性探测法（Linear Probing）

会形成聚集现象，有冲突聚集时，此处的冲突会越来越多

平方探测法（Quardratic Probing）

主要优势避免冲突聚集

是否会存在有空间，但是平方探测（二次探测）就是找不到的情况？

有定理显示：如果散列表长度TableSize是某个4k+3（k是正整数）形式的素数时，平方探测法就可以探查到整个散列表空间。所以说表的长度不能随意设计。

info主要功能是用来区分是被删掉还是没有元素

双散列探测法（Double Hashing）

再散列（Rehashing）

当散列表元素太多（即装填因子$\alpha$太大）时，查找效率会下降；

实用最大装填因子一般取$0.5\le a\le 0.85$

当装填因子过大时，解决的方法是加倍扩大散列表，这个过程叫做“再散列（Rehashing）”

分离链接法（Separate Chaining）

分离链接法：将相应位置上冲突的所有关键词存储在同一个单链表中。

11.4 散列表的性能分析

平均查找长度（ASL）

平均查找长度（ASL）用来度量散列表查找效率：成功、不成功

关键词的比较次数，取决于产生冲突的多少影响产生冲突多少

有以下三个因素：

• （1）散列函数是否均匀；
• （2）处理冲突的方法；
• （3）散列表的装填因子a。

分析：不同冲突处理方法、装填因子对效率的影响

线性探测法的查找性能

可以证明，线性探测法的期望探测次数满足下列公式：
p = { 1 2 [ 1 + 1 ( 1 − α ) 2 ] （对插入和不成功查找而言） 1 2 ( 1 + 1 1 − α ) （对成功查找而言） p=\left\{

$$\begin{array}{l} \frac{1}{2}\left[1+\frac{1}{(1-\alpha)^{2}}\right]\text{（对插入和不成功查找而言）} \\ \frac{1}{2}\left(1+\frac{1}{1-\alpha}\right)\text{（对成功查找而言）} \end{array}$$ \right. p={21​[1+(1−α)21​]（对插入和不成功查找而言）21​(1+1−α1​)（对成功查找而言）​

当a=0.5时

插入操作和不成功查找的期望ASLu=2.5次

成功查找的期望ASLs=1.5次

平方探测法和双散列探测法的查找性能

可以证明，平方探测法和双散列探测法探测次数满足下列公式：
p = { 1 1 − α  (对插入和不成功查找而言  ) − 1 α ln ⁡ ( 1 − α )  (对成功查找而言)  p=\left\{

$$\begin{array}{l} \left.\frac{1}{1-\alpha} \text { (对插入和不成功查找而言 }\right) \\ -\frac{1}{\alpha} \ln (1-\alpha) \quad \text { (对成功查找而言) } \end{array}$$ \right. p={1−α1​ (对插入和不成功查找而言 )−α1​ln(1−α) (对成功查找而言) ​

当a=0.5时

插入操作和不成功查找的期望ASLu=2次

成功查找的期望ASLs=1.39次

期望探测次数与装填因子a的关系。

分离链接法的查找性能

所有地址链表的平均长度定义成装填因子$\alpha$，$\alpha$有可能超过1。
不难证明：其期望探测次数$p$为：
p = { α + e − α  (对插入和不成功查找而言)  1 + α 2  (对成功查找而言  ) p=\left\{

$$\begin{array}{ll} \alpha+e^{-\alpha} & \text { (对插入和不成功查找而言) } \\ 1+\frac{\alpha}{2} & \text { (对成功查找而言 } ) \end{array}$$ \right. p={α+e−α1+2α​​ (对插入和不成功查找而言)  (对成功查找而言 )​

当$\alpha =1$时，

插入操作和不成功查找的期望ASLu=1.37次

成功查找的期望ASLs=1.5次。

关于散列查找的评价

选择合适的$h(key)$，散列法的查找效率期望是常数$O(1)$，它几乎与关键字的空间的大小$n$无关！也适合于关键字直接比较计算量大的问题

它是以较小的$\alpha$为前提。因此，散列方法是一个以空间换时间

散列方法的存储对关键字是随机的，不便于顺序查找关键字，也不适合于范围查找，或最大值最小值查找。

开放地址法VS分离链法：

• 开放地址法:散列表是一个数组，存储效率高，随机查找。散列表有“聚集”现象
• 分离链法：
  散列表是顺序存储和链式存储的结合，链表部分的存储效率和查找效率都比较低。关键字删除不需要“懒惰删除”法，从而没有存储“垃圾”。太小的$\alpha$可能导致空间浪费，大的$\alpha$又将付出更多的时间代价。不均匀的链表长度导致时间效率的严重下降。

11.5 应用实例：词频统计