23 分块查找、散列查找（哈希查找）.md

#数据结构 #算法

[80] 分块查找

1. 算法思想

看起来乱序存放的顺序表中，实质上按照一块一块切分，每一个块内是在一定范围内的。我们对这样的顺序表需要建立索引，“索引表”中保存每个分块的最⼤关键字key和分块的存储区间。

整体呈现特点，块内⽆序、块间有序。

// 索引表
typedef struct {
    ElemType maxValue;
    int low, high;
} Index;

// 顺序表存储实际元素
ElemType List[100];

分块查找，⼜称索引顺序查找，算法过程如下：

1. 在索引表中确定待查记录所属的分块（可顺序、可折半）
2. 在块内顺序查找 （具体代码省略）

2. 查找效率分析

假设，⻓度为 $N$ 的查找表被均匀地分为 $b$ 块，每块 $s$ 个元素 设索引查找和块内查找的平均查找⻓度分别为 $L_I$、 $L_s$ ，则分块查找成功的平均查找⻓度为: $$ASL = L_I + L_s$$

1. ⽤顺序查找查索引表，则： $$L_I = \frac{1 + 2 + ... + b}{b} =\frac{b + 1}{2}$$ $$L_s = \frac{1 + 2 + ... + s}{s} =\frac{s + 1}{2}$$ 因此， $$ASL = \frac{b+1}{2}+\frac{s+1}{2} = \frac{s^2+2s+N}{2s}$$ 当 $s=\sqrt{n}$ ， $ASL_{min} = \sqrt{n} + 1$ 时上式成立。

2. 用折半查找查索引表，则： $$L_I = ⌈\log_2{(b + 1)}⌉$$ $$L_s = \frac{1 + 2 + ... + s}{s} =\frac{s + 1}{2}$$ 因此， $$ASL = ⌈\log_2{(b + 1)}⌉ + \frac{s + 1}{2}$$ 分块查找失败的情况较为复杂，这里暂时不做过多探讨。

[81] 散列查找

1. 基本概念

散列表（Hash Table），⼜称哈希表，是⼀种数据结构。其数据元素的关键字与其存储地址直接相关。

【问题】
如何建⽴“关键字” 与“存储地址” 的联系？

【解决方法】
通过散列函数（哈希函数）： $$Addr = H(key)$$

【问题】
有⼀堆数据元素，关键字分别为: {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，散列函数： $$H(key) = key % 13$$

若不同的关键字通过散列函数映射到同⼀个值，则称它们为“同义词”。通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”。如图中1和14对13取余，均是1，发生了冲突。

为解决以上冲突，⽤拉链法（⼜称链接法、链地址法）处理“冲突”：即把所有“同义词”存储在⼀个链表中。如图，建立了一个数组，数组内部有13个指针，数组的每个指针指向该数据元素。

举例，如果需要查找27，那27%13=1，对27查找，查找⻓度 = 3；
同理，对20的查找长度为1。21的查找⻓度=0，表示查找失败。66的查找⻓度=4，查找失败。

【查找⻓度】
在查找运算中，需要对⽐关键字的次数称为查找⻓度。

计算平均查找长度：

• 查找成功:
  $$ASL_{s} = \frac{1 × 6 + 2 × 4 + 3 + 4}{12} = 1.75$$
  或者：
  $$ASL_{s} = \frac{1+2+3+4+1+2+1+2+1+1+2+1}{12} = 1.75$$ 因为数据总共有12个，每个数据查找的都是1/12。对比顺序查找可能需要6次左右，散列查找 具有明显优势。

• 查找失败: $$ASL_{f} = \frac{0 × 7 + 1 × 2 + 2 × 4 + 4}{13} = 0.92$$ 这个值，叫做装填因子 $α$， $$α = \frac{表中记录数}{散列表⻓度}$$
  装填因⼦会直接影响散列表的查找效率。装填因子越大，表示冲突的可能性更大，需要查找的平均长度越长。

【问题】 如何通过设计冲突更少的哈希函数，使查找效率提高？最理想的情况是，散列查找时间复杂度可到达 $O(1)$。

2. 常见散列函数

除留余数法

$$H(key) = key % p$$ 散列表表⻓为m，取⼀个不⼤于m但最接近或等于m的质数p。 注意：这里选择质数，能够使得冲突尽可能少。

如果对有一定特征的数字（偶数）进行取余：

• 左侧对8 取余，各关键字的散列地址集中在0，2，4，6；
• 右侧对7 取余，各关键字的散列地址分布均匀。

直接定址法

$$H(key) = key$$ 或者 $$H(key) = a × key + b$$ 其中，a和b是常数。这种⽅法计算最简单，且不会产⽣冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

例：存储同⼀个班级的学⽣信息，班内学⽣学号为 (1120112176~1120112205) $$H(key) = key - 1120112176$$

数字分析法

数字分析法，选取数码分布较为均匀的若⼲位作为散列地址。
设关键字是r进制数（如⼗进制数），⽽r个数码在各位上出现的频率不⼀定相同，可能在某些位上分布均匀⼀些，每种数码出现的机会均等；⽽在某些位上分布不均匀，只有某⼏种数码经常出现，此时可选取数码分布较为均匀的若⼲位作为散列地址。这种⽅法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

例如：以“⼿机号码”作为关键字设计散列函数:

平方取中法

平⽅取中法，取关键字的平⽅值的中间⼏位作为散列地址。
具体取多少位要视实际情况⽽定。这种⽅法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布⽐较均匀，适⽤于关键字的每位取值都不够均匀或均⼩于散列地址所需的位数。

散列查找是典型的“⽤空间换时间”的算法，只要散列函数设计的合理，则散列表越⻓，冲突的概率越低。

3. 冲突的处理

1. 拉链法/链地址法：

把所有“同义词”存储在⼀个链表中。

2. 开放定址法：

指可存放新表项的空闲地址既向它的同义词表项开放，⼜向它的⾮同义词表项开放。其数学递推公式为： $$H_i = (H(key) + d_i) % m$$ 其中， $i = 0, 1, 2,…, k(k≤m - 1)$ ， $m$ 表示散列表表⻓， $d_i$ 为增量序列， $i$ 可理解为“第 $i$ 次发⽣冲突”。

开放定址法主要分为三类：线性探测法、平方探测法、伪随机序列法。

1. 线性探测法

$d_i = 0, 1, 2, 3, …, m - 1$ ；即发⽣冲突时，每次往后探测相邻的下⼀个单元是否为空。依然以该堆数据元素为例。
【问题】
有⼀堆数据元素，关键字分别为 {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，散列函数 $$H(key) = key % 13$$ 1与14的地址发生了冲突。 $$H(key)= 1%13 =1$$
$$H_0=(1+d_0)%16=1$$ 仍然冲突 $$H_1=(1+d_1)%16=2$$ 在2处存入1。

哈希函数值域[0,12]，冲突处理函数值域[0,15]。

如何使用线性探测法进行查找呢？

查找成功的话，以27为例。
$H(key) = 27%13 = 1$ (冲突下一个) ---> $H_1 = 2$ (冲突下一个) ---> $H_2 = 3$ (冲突下一个) ---> $H_3 = 4$ ---> 查找成功，查找长度 = 4。
使用开放定址法，同义词、⾮同义词都需要被检查。

查找失败的话，以21为例。
$H(key) = 21%13 = 8$ (冲突下一个) ---> $H_1 = 9$ (冲突下一个) ---> $H_2 = 10$ (冲突下一个) ... ---> $H_5 = 13$ ---> 查找失败，查找长度 = 6。

注意：采⽤“开放定址法”时，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填⼊散列表的同义词结点的查找路径，可以做⼀个“删除标记”，进⾏逻辑删除。

查找效率分析： 查找成功 $$ASL_{s}=\frac{1 + 1 + 1 + 2 + 4 + 1 + 1 + 3 + 3 + 1 + 3 + 9}{12} = 2.5$$ 查找失败 $$ASL_{f}=\frac{1 + 13 + 12 + 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2}{13} = 7$$ 初次探测的地址 $H_0$ 只有可能在[0,12]。

2. 平方探测法

$$H_i = (H(key) + d_i) % m$$ $i = 0, 1, 2,…, k(k≤m - 1)$， $m$ 表示散列表表⻓； $d_i$ 为增量序列。

当 $d_i = 0, 1^2, -1^2, 2^2, -2^2, …, k^2, -k^2$ 时，称为平⽅探测法，⼜称⼆次探测法其中 $k≤m/2$ 。

注意负数的模运算， $(-3) % 27 = 24$ ，⽽不是3。

数论中模运算的规则： $$a MOD m == (a+km) MOD m$$ 其中， $k$ 为任意整数比起线性探测法更不易产⽣“聚集（堆积）”问题。

3. 伪随机序列法

$$H_i = (H(key) + d_i) % m$$ $i = 0, 1, 2,…, k(k≤m - 1)$ ， $m$ 表示散列表表⻓； $d_i$ 为增量序列； $d_i$ 是⼀个伪随机序列，如 $d_i= 0, 5, 24, 11 ...$

3. 再散列法 / 再哈希法

除了原始的散列函数 $H(key)$ 之外，多准备⼏个散列函数， 当散列函数冲突时，⽤下⼀个散列函数计算⼀个新地址，直到不冲突为⽌： $$H_i = RH_i(Key),i=1,2,3….,k$$