查找问题 与 Hash散列表|数据结构Ⅴ

查找问题

查找是指在数据集合中寻找满足某种条件的数据元素的过程。
而查找问题则是对数据集合利用不同的数据结构、考虑不同的数据排序情况、设计不同的查找算法使得查找效率更高的问题。

我们定义 平均查找长度（Average Search Length，ASL）为：

$$ASL=\sum_{i=1}^np_ic_i$$

其中，$n$ 为查找表的长度，也即数据个数；$p_i$ 为查找到第$i$ 个元素的概率；$c_i$ 为查找到第$i$ 个元素所需的比较次数。

平均查找长度是衡量一个查找算法的主要指标。

顺序查找

顺序查找又称线性查找，它对顺序表和链表均适用。
其查找思想很简单，即从第一个元素开始，依次往下查询，查找成功就结束。

对于无序表

若无序表中元素个数为$n$，顺序查找从第一个元素开始递增查找，则当查找到第$i$ 个元素并且成功时，其查找次数$c_i=i$.
若每个元素的查找概率相等，即$p_i=1/n$，则：

$$ASL_{success}=\frac1n(1+2+\cdots+n)=\frac{n+1}2$$

而查找失败时，显然所有元素都查了个遍，$ASL_{fail}=n+1$.（算法实现时需要添加“哨兵”用于判定查找结束，所以比元素个数多1）

对于有序表

若对元素个数$n$ 的有序表进行顺序查找，其查找成功的平均长度与无序表一致，均为$(n+1)/2$。但查找失败的判定则不同。

对于有序表来说，以升序表为例，如果关键字 key 大于$L[i]$ ，但又小于$L[i+1]$ ，则说明 key 此后都不会再出现于表中。
所以，查找到第$i$ 个结点失败的查找次数是$c_i=i+1$.
若每个元素的查找概率相等，因为“哨兵”的缘故，所以$p_i=1/(n+1)$，则：

$$ASL_{fail}=\frac1{n+1}[(1+2+\cdots+n)+n]=\frac n2+\frac{n}{n+1}$$

折半查找

这边查找又叫二分查找。其主要针对于顺序表，核心是利用分治策略。
给定一个有序数组$A$，要查找某个元素$x$ 在$A$ 中的位置，利用二分法的思想，先将$x$ 与$A[n/2]$ 进行比较（$n$ 是数组长度），从而可以根据比较结果，锁定$x$ 是属于子数组$A[1..n/2]$ 还是子数组$A[n/2+1..n]$。进而将原问题分解为了规模更小的子问题。迭代求解子问题就可以综合得到原问题的解。

伪代码

$$\begin{aligned} &\text{Algorithm: }\;\text{Binary-Search}(nums,n)\\\\ 1.&\; x\leftarrow nums[1]\\ 2.&\;low\leftarrow1;\;high\leftarrow n\\ 3.&\;\mathbf{while}\;low\leq high\;\mathbf{do}\\ 4.&\;\qquad mid\leftarrow \left \lfloor(low+high)/2\right \rfloor\\ 5.&\;\qquad\mathbf{if}\;nums[mid]= x\;\mathbf{then}\;\mathbf{return}\;mid\\ 6.&\;\qquad\mathbf{else\;if}\;nums[mid]\gt x\;\mathbf{then}\\ 7.&\;\qquad\qquad high\leftarrow mid-1\\ 8.&\;\qquad\mathbf{else}\; low\leftarrow mid+1\\ 9.&\;\mathbf{return}\;-1 \end{aligned}$$

判定树

以有序表 nums = [7,10,12,16,19,29,32,33,37,41,43] 为例，其做折半查找的过程可以用下图所示的二叉树来描述。我们称这种树为 判定树。

事实上，引入判定树的思想也是算法分析中，对于递推类算法进行复杂度分析时常用的递归树思想。

树中每一个圆形结点就代表着顺序表中一个元素，结点中的值是该元素的关键字。而树中的方形结点则代表查找失败的情况，说明需查找的元素$x$ 落在方框里的区间内。

每个结点值均大于其左子结点值，均小于其右子结点值。对于元素个数为$n$ 的情况，则圆形结点（非叶结点）个数为$n$，方形结点（叶结点）个数为$n+1$。由此我们可以得出，折半查找的判定树是一棵 平衡二叉树。

显然，查找成功时的比较次数$c_i$ 就对应着树中圆形结点所在的层数。所以

$$ASL_{success}=\frac1n(1\times1+2\times2+\cdots+h\times2^{h-1})=\frac{n+1}{n}\log_2(n+1)-1$$

而查找失败时，比较次数是方形结点上方的圆形结点所在层数，因为该圆形结点这是得到虚拟结点的最后一次比较。

以上图为例，有：

$$ASL_{success}=\frac{1·1+2·2+3·4+4·4}{11}=3;\;\;ASL_{fail}=\frac{3·4+4·8}{12}=11/3$$

式中，$h$ 为平衡二叉树的树高，有$h=\lceil\log_2(n+1)\rceil$.
由此也可以得出，二分查找的时间复杂度为$O(\log_2n)$.

以上分析均建立在各元素查找概率相等的情况。
若查找概率不等，二分查找不一定优于顺序查找，此时将表内元素按概率降序排列的话，顺序查找的平均查找长度可达到自身的最小。

与 BST 的比较

二分查找的判定树是唯一的，但 BST 的查找却随着其创建时输入的元素顺序不同而不同。最坏情况下会形成一棵单支树。

就维护表的有序性而言，二叉排序树无需移动结点，只需修改指针，平均执行时间是$O(\log_2n)$。而二分查找的对象是顺序表，插入和删除都需要$O(n)$ 的代价。

当有序表是静态查找表时，宜用顺序表作为其存储结构，采用二分查找实现查找功能；
当有序表是动态查找表时，宜用 BST 作为其逻辑结构。

STL 中的折半查找

#include<algorithm>

待更

分块查找

分块查找又称索引顺序查找。

分块查找吸收了顺序查找和折半查找各自的优点，既有动态结构也适用于快速查找。
基本思想是，把查找表分为若干子块，要求：

1. 块内元素可以无序；
2. 块与块之间必须有序；
3. 第一个块内最大值小于第二个块内最小值，以此类推。

在上述基础上，建立一个索引表。索引表中每个元素含有各子块的最大关键字和各子块内第一个元素的地址。索引表按关键字有序排列。

于是，分块查找的过程可总结为两步：

1. 在索引表中顺序查找或折半查找，找到目标元素属于哪一块；
2. 在目标块内顺序查找元素。

---

若将长度$n$ 的查找表均匀分为$b$ 块，每块有$s$ 个元素。
在索引表内的平均查找长度记为$L_I$，在块内的平均查找长度记为$L_S$，则整个分块查找的ASL值(查找成功)为：

$$ASL_{success }=L_I+L_S=\frac{b+1}2+\frac{s+1}2=\frac{s^2+2s+n}{2s}$$

当$s=\sqrt n$ 时，平均查找长度取得最小值$\sqrt n+1$.

所以，为了使得 ASL 最小，一般我们分块时选择“开方”分法。

散列表|_{Hash Table}

引例

HDU 1425 Sort

Problem Description

给定$n$ 个整数，要求按从大到小的顺序输出其中前$m$ 大的数。

Input
每组测试数据有两行，第一行有两个数$n,m\quad(0<n,m<1000000)$，第二行包含$n$ 个各不相同，且都处于区间$[-500000,500000]$ 的整数。

Output

对每组测试数据按从大到小的顺序输出前$m$ 大的数。

对于本题，很明显能想到使用经典算法的几大排序（比如冒泡排序、选择排序、快速排序等）解决。

亦或者，直接使用STL中提供的 <algorithm> 调用 sort()函数进行求解。时间复杂度$O(n\log{n})$.

然而对于本题，是不能 Accept 的。因此我们需要寻求更快的方法！

在题干中，给出了大区间，这也从另一个角度说明了对本题使用普通排序算法会消耗大量时间；题干中还有明显的“整数”字样，不仅如此还强调每一个整数都 “各不相同”，这就是一个突破口！

考虑用数组下标来映射实际数值，如读取到关键字$k$ 时，对以$k$ 为下标的数组元素置1，即：$a[k]\leftarrow 1$（初始化数组全零）。
以这种方式来保存数据的话，相当于利用数组（下标）的连续性自动进行了所有排序，于是时间复杂度为$O(n)$。

事实上，这更类似于 桶排序，当数据存储完毕之时，也是数据排序完毕之时。

那，话不多说，直接贴出AC代码：

/* 注：
	1.使用scanf与printf比cin和cout更快
	2.由于原题要求区间在[-500000,500000]之间，所以开数组时应该考虑加减问题
	3.注意格式要求，比如空格与回车
*/

#include<iostream>
#include<string.h>
using namespace std;
int a[1000001];
int main(void){
    int tmp,num,m;
    while(scanf("%d%d",&num,&m) == 2){
        memset(a,0,sizeof(a));
        for(int i = 0; i < num; i++){
            scanf("%d",&tmp);
            a[tmp+500000] = 1;
        }
        for(int i = 1000000; i >= 0; i--){
            if(m && a[i] != 0){
                if(m > 1) printf("%d ",i-500000);
                else printf("%d",i-500000);
                m--;
                if(m == 0) break;
            }
        }
        printf("\n");
    }
    return 0;
}

## 散列算法简介

散列算法（Hash Algorithm），又称哈希算法，杂凑算法，是一种从任意文件中创造小的数字「指纹」的方法。简而言之，就是映射。

• 散列函数（Hash 函数）：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为：$H(key)=Addr$。这里的地址可以是数组下标、索引或内存地址等。
• 散列表（Hash 表）：根据关键字而直接进行访问的数据结构。也就是说散列表建立了关键字和存储地址之间的一种之间映射关系。

Hash 算法就是对 Hash 函数的设计。使得对任意一个关键字或任意长度的明文可以映射为唯一的内容，并且要求不同的明文很难映射为相同的 Hash 值，即具有较好的抗冲突性。

给定一组范围确定的关键字（个数为$n$ ），并依次将其通过 Hash 函数求得的 Hash 值与之组成唯一的键值对存放于表中，则这个表就是 Hash 表。
如果采用顺序存储，数组记为$A[1..n]$，则可以直接用数组及其下标分别代表关键字及其哈希值，于是就有：

$$A[H(key)]=key$$

特点

• 正向快速：给定明文和 Hash 算法，在有限时间和有限资源内能计算得到 Hash 值。
• 逆向困难：给定 Hash 值，在有限时间内很难逆推出明文。
• 输入敏感：原始输入信息发生任何变化，新的 Hash 值都应该出现很大变化。
• 冲突避免：很难找到两段内容不同的明文，使得它们的 Hash 值一致。

种类

常见 Hash 算法有 MD5 和 SHA 系列，目前 MD5 和 SHA1 已经被破解，一般推荐至少使用 SHA2-256 算法。

Hash 函数是把一个大范围映射到一个小范围，目的往往是为了节省空间，使得数据容易保存，另外 Hash 函数也会应用于查找上。

散列函数的构造

直接定位法

直接取关键字的某个线性函数值为散列地址，即：

$$H(key)=key\quad\text{or}\quad H(key)=a\times key+b$$

此方法计算简单且不会发生碰撞冲突，适合关键字分布基本连续的情况，否则会使得空位较多，造成存储空间的浪费。

在引例中，我们就是用$H(x) = x+500000$ 这样的函数来进行映射的。

除留余数法

除留余数法是一种最简单也是最常用的方法。
假定 Hash 表的表长为$n$，取一个不大于$n$ 但最接近$n$ 的质数$p$，则可利用下式构造 Hash表：

$$H(key) = key \mod{p}$$

此方法的关键是选取最合适的$p$，以使得每个关键字都能通过哈希函数转换后能等概率地映射到哈希表的任一位置，以减少冲突的可能性。

数字分析法

假设关键字集合中的每个关键字都是$r$ 进制数，而分析关键字集中的全体，并从中提取$r$ 个数码在每一位上出现的频率，通过频率的分布情况进行哈希值的选择。以均匀分布的若干位或它们的组合作为地址。丢掉分布不均匀的位。

数字分析法只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。

平方取中法

由于整数相除的运行速度通常比相乘要慢，所以有意识地避免使用除余法运算可以提高散列算法的运行时间。

平方取中法的具体实现是：先通过求关键字的平方值，从而扩大相近数的差别，然后根据表长度取中间的几位数（往往取二进制的比特位）作为哈希值。
因为一个乘积的中间几位数与乘数的每一数位都相关，所以由此产生的散列地址较为均匀。

该方法适用于关键字每一位取值都不够均匀或小于散列地址所需位数的情况。

举例如下：

关键字	关键字的平方	哈希值
1234	1522756	227
2143	4592449	924
4132	17073424	734
3214	10329796	297

解决碰撞冲突

不难发现既然输入关键字的大小（不是个数）是不固定的，而输出的哈希值却是固定长度的，这就意味着哈希值是一个有限集合。而输入数据则可以是无穷多个，那么建立一对一关系明显是不现实的。

因此“碰撞”是必然会发生的，所以一个成熟的哈希算法会有较好的抗冲突性，同时在实现哈希表的结构时也要考虑到哈希冲突的问题。

开放定址法

一般地，可以在发生冲突时，为关键字找到下一个“空”的 Hash 地址后，再将此地址作为其哈希值。

开放定址法是指可存放新表项的空闲地址既向它的同义词表项开放（即哈希值等于此地址的关键字），也向它的非同义词表项开放。简而言之无论如何，只要按照某种算法能将某一关键字放入该地址，那么此地址就允许放入，无所谓是否同义。

以$H_i$ 表示对一个关键字的第$i$ 次探测得到的散列地址，在第$k$ 次找到空地址，则有：

$$H_i=[H(key)+d_i]\mod n$$

其中，$i=0,1,2,\cdots,k\quad(k\leq n-1)$ ，$n$ 为散列表长度（区别于除留余数法的$p$ ），$d_i$ 为增量序列。

对于$d_i$ 的选取方式不同，也可以得到不同的结果，选取方式也对应着不同的方法。

在开放定址情况下，不能物理删除表中已有元素。若删除元素将会截断其他具有相同散列地址的元素查找地址。所以，欲删除元素，可以为其做一个删除标记，进行逻辑删除。
此外，此处理方式也有弊端，执行多次删除后会出现散列表看似很满，实则都是已删除元素的情况，因此需要定期对散列表进行维护。

线性探测法

增量序列$d_i=0,1,2,\cdots,n-1$ 时，称为线性探测法。（也叫线性探测再散列）
即冲突发生时，顺序查看表中的下一个单元，再冲突再查，查到表尾时再冲突则下一步回到表首继续查，直到找到第一个空位或表完全遍历了一遍结束。

线性探测法可能使第$i$ 个散列地址的同义词存入到第$i+1$ 的位置，这就使得原本应该存放在$i+1$ 的关键字又顺延到第$i+2$ 的位置，考虑最坏情况就会导致散列地址上产生大量堆积（也叫“聚集”），大大降低了查找效率。

堆积现象对存储效率、散列函数和填装因子均无影响，只有平均查找程度 ASL 因堆积现象而增大。

平方探测法

增量序列$d_i=0^2,1^2,-1^2,2^2,-2^2\cdots,k^2,-k^2$ 时，称为平方探测法/二次探测再散列。其中，$k\leq n/2$，且散列表长度$n$ 必须是一个可以表示成$4k+3$ 的质数。

平方探测法是一种处理冲突较好的方法，可以避免堆积问题，但不能探测到散列表的所有单元，至少能探测一半的单元。

双散列法

取增量序列$d_i=i\times Hash_2(key)$ 时，称为 双散列法。
即使用两个散列函数. 通过第一个散列函数$Hash_1(key)$ 发生冲突时，利用第二个散列函数计算地址增量，有：

$$H_i=[Hash_1(key)+i\times Hash_2(key)]\mod n$$

此处的$i$ 是冲突次数，初始为零。

通过该方法最多经过$n-1$ 次探测就会遍历完表中所有位置，回到$H_0=Hash_1(key)\%m$ 处。

伪随机序列法

顾名思义，当$d_i$ 取伪随机数时，称为伪随机序列法。

---

拉链法 |Chaining

为了避免非同义词的占用发生的冲突，可以采用链表数组的方式将同义词都存储在同一数组下标所指的一条链表中，该下标由散列函数唯一给出。

拉链法适用于经常插入和删除的情况。

下图是利用除留余数法构造 Hash函数，利用拉链法解决冲突的一个示例图。

散列算法的使用

下面给出一例题，可利用 Hash 函数的思想进行求解：

HDU 1496 Equations（已翻译）

---

Problem Description

给出如下等式:

$$a x_1^2+bx_2^2+cx_3^2+dx_4^2=0$$

$a, b, c, d$ 是范围在$[-50,50]$ 内的整数 ，且均不为 0.

考虑给出一个解：$( x_1,x_2,x_3,x_4 )$ 使得上述等式成立 , 其中$x_i\in [-100,100]$ ，且$x_i \neq 0, i=1,2,3,4$.

对于给定的$a,b,c,d$ 请编程得出解决方案共有多少组。

Input

输入包含多组测试. 每行输入 4 个整数分别表示 a, b, c, d, 用空格隔开

Output

对于给定的每组数据, 输出一行结果.

Sample Input

1 2 3 -4
1 1 1 1

Sample Output

39088
0

本题题目很简单，与最经典的算法题：百元买百鸡 如出一辙。

因此首先会想到最常规的方法，即：使用四层嵌套循环依次得出符合要求的数据，再利用计数变量统计方案数。

显然，从 -100 到 100 每一层循环都要运算201次，时间复杂度非常之高。

因此我们必须考虑使用其他算法……

---

考虑将原式变形，得到：

$$a x_1^2+bx_2^2=-(cx_3^2+dx_4^2)$$

接下来再一步步优化算法。

1. 【空间减少】由于题目所给的$x$ 区间$[-100,100]$ 是对称的，所以，其实$x_i^2$ 是可以只用100个数据代表的（题目中说$x_i$ 不为0）；
2. 【剪枝】 对于$a x_1^2+bx_2^2+cx_3^2+dx_4^2=0$ ，当所给$a,b,c,d$ 均大于0 或 均小于0时，不用考虑，方案数直接为0；
3. 【循环减少】 两层循环保存左边的$a x_1^2+bx_2^2$，两层循环验证右边的$-(cx_3^2+dx_4^2)$ ,如果相等，计数变量+1；

上述优化中的第三点就比较耐人寻味了，因为如何进行“验证相等”成了一个难点。

这时，我们就可以把Hash表用上来了。

可以建立映射：

$$MarkNum=Hash(data)$$

在验证时将右边得到的数据作为变量，通过hash函数得出是否出现过，如果出现，出现了几次。

相应的，我们在计算左边数据的时候需要利用hash函数将数据保存并将其做标记。

这样一来，如果右边得出的数据通过hash能够得出的结果是已经做了标记，就说明二者相等，验证完成。

• 同样的，我们开一个大数组，用下标表示数据，数值表示标记变量，即

• $Hash[data] = MaekNum$

之后，便可以得到AC代码：

#include "stdio.h"
#include "memory.h"
int xx[101];
int hash[2000003];
int main(void){
    int a,b,c,d;
    int i,j,sum;
    for(i=1;i<101;i++)
        xx[i] = i*i;//保存100内x的平方
    while(scanf("%d %d %d %d",&a,&b,&c,&d)!=EOF){
        if((a>0 && b>0 && c>0 && d>0)||(a<0 && b<0 && c<0 && d<0)){      
            printf("0\n");
              continue;
        }//剪枝
     	memset(hash,0,sizeof(hash));//hash初始化
     	for(i=1;i<=100;i++)
           for(j=1;j<=100;j++)
               hash[a * xx[i] + b * xx[j] + 1000000]++;//保存左边数值到hash表
     	 sum = 0;//计数变量
      	for(i=1;i<=100;i++)
          	for(j=1;j<=100;j++)
             	sum += hash[-(c * xx[i] + d * xx[j]) + 1000000];
      	printf("%d\n",sum*16);
    }
}

❔Q：为什么保存 hash 时要+1000000？
✅A：本题中，$a,b,c,d$ 出现负数，最值是 -50，其次，$x^2$ 最值是10000。因此，负数的极限值是：$50\times10000+50\times10000$

❔Q：为什么 sum 要乘以16？
✅A：算法只给出了$x_1\sim x_4$ 的情况，事实上这4个量全排列可以得到16种情况（题目问的是总方案数）

---

然而，事实上整个算法还可以再优化！

两层循环最多只可能产生10000个不同的结果,

开200W的数组将会浪费很多初始化的时间,所以开小数组+处理冲突会比较好.

​ ——by LaiLi

#include<stdio.h>
#include<memory.h>

#define MAX 50021//为一较大的素数

//利用数组f进行哈希表保存
int f[MAX],g[MAX];

//使用hash函数进行冲突处理
int hash(int data){
    int pos = data%MAX;
    if(pos < 0)
        pos += MAX;//对数据除余
    while(f[pos] != 0 && g[pos] != data)
        pos = (pos+1)%MAX;
    //当其在哈希表中已有，且不是自己本身时：
    //将其存入哈希表下一个区域中并返回位置下标
    return pos;
}

int main(void){
    int a,b,c,d,pos,i,j,data,cnt,xx[101];
    for(i = 1; i <= 100; i++)
        xx[i] = i*i;
    while(scanf("%d%d%d%d",&a,&b,&c,&d) == 4){
        if(a>0&&b>0&&c>0&&d>0||a<0&&b<0&&c<0&&d<0){
            printf("0\n");
            continue;
        }//剪枝
        memset(f,0,sizeof(f));//哈希表初始化
        cnt = 0;//计数变量初始化
        for(i=1;i<=100;i++)
            for(j=1;j<=100;j++){
                data = a*xx[i]+b*xx[j];
                pos = hash(data);
                //通过返回的位置下标，进行存表
                g[pos] = data;
                f[pos]++;
            }
        for(i=1;i<=100;i++)
            for(j=1;j<=100;j++){
                data = -(c*xx[i]+d*xx[j]);
                pos = hash(data);
                cnt += f[pos];
            }
        printf("%d\n",cnt*16);
    }
}

散列查找与性能分析

对散列表的查找过程与散列表的构造过程是基本一致的，此处不再赘述。
而因为冲突的解决所使用的方法不同，将导致并不是每次查找都能一次就查找成功，需要查找多次，即探测多次。因此，这个探测次数，即比较关键字的次数成了查找效率主要的指标。

我们还是可以用 平均查找长度（Average Search Length，ASL）来作为主要指标，在等概率情况下，查找成功的ASL有：

$$ASL=\frac1n\sum_{i=1}^nk_i$$

式中，$n$ 为散列表中含有的关键字个数，$k_i$ 为第$i$ 个关键字的查找次数。

而查找失败的ASL有：

$$ASL=\frac1{n'}\sum_{i=1}^{n'}k_i$$

式中，$n'$ 是经过散列函数计算所得结果的所有可能性个数。即$H=\cdots\mod ?$ 的 问号处的数字与散列表长度取最小。一般情况下，查找比较次数还需算上查到空地址的一次。（有的教材则不计入此次数，具体到题目中若未说明，则算上一次空地址）

填装因子

散列查找的效率取决于散列函数、处理冲突的方法、填装因子。

填装因子用$\alpha$ 表示，定义为一个散列表装满的程度，即：

$$\alpha=\frac{Number\;of\;Keys}{HashTable's\;Length}$$

应当注意，散列表的ASL依赖于填装因子$\alpha$，而不直接依赖于关键字个数和散列表长度。
定性分析，$\alpha$ 越大，散列表装得越满，发生冲突的可能性就越大。

字符串哈希

待更

参考资料

1.十大经典排序算法|博客园

2.哈希算法简介|CSDN

3.HDForum-Hash及其应用|刘春英

4.字符串哈希详解| dgklr

5.常见字符串哈希函数汇总 |CSDN