数据结构与算法_查找

2023-02-16 14:39 作者:昵昵酱紫 0人读过 | 我要投稿

查找（Search）又称为搜索，指从数据表中找出符合条件的记录。如今我们处在信息爆炸的大数据时代，如何从海量信息中快速找到需要的信息，就需要查找技术。如果有什么不懂得，要查询得东西，都会在网上搜索一下，查找是最常见得应用。

查找算法得性能和下面几个因素有关：

1) 算法；

2) 数据规模；

3) 待查关键字在数据表中得位置;

4）查找得频率;

评价一个查找算法得好坏，一般采用平均查找长度（Average Search Length,ASL）来衡量。分为查找成功得平均查找长度和查找失败得平均查找长度。平均查找长度的计算公式：

其中，n为数据规模，pi为查找第i个记录的概率，ci为查找第i个记录所需要的关键字比较次数。

根据在查找过程是否对表有修改，分为静态查找和动态查找；

根据数据结构的不同又分为线性查找，树查找和散列表查找。散列表查找是一种比较特殊的查找技术。

线性表的查找非常简单，如果线性表无序，则采用顺序查找，如果线性表有序，则采用折半查找。

顺序查找：

算法分析：

算法优化：

折半查找：

（1）非递归算法

（2）递归算法：

因为递归有自调用问题，那么就需要增加两个参数low和high来标记搜索范围的开始和结束。

哈希表：

线性表和树表的查找都是通过比较关键字的方法，查找的效率取决于关键字的比较次数。有没有一种查找方法，不进行关键字比较，直接找到目标？

散列表是根据关键字直接进行访问的数据结构。散列表通过散列函数将关键字映射到存储地址，建立了关键字和存储地址之间的一种直接映射关系，这里的存储地址可以是数字下标，索引，内存地址等等。

例如，关键字key = (17,24,48,25)，散列函数H(key) = key%5。散列函数将关键字映射到存储地址下标，将关键字存储到散列表的对应位置。如图所示：

如果要查找48，就可以通过散列函数得到其存储地址，直接找到该关键字。散列表查找的时间复杂度与表中的元素个数无关。理想情况下，散列表查找的时间复杂度为O(1)。但是，散列函数可能会把两个或两个以上的关键字映射到同一个地址，发生“冲突”，这种发生冲突的不同关键字称为同义词。例如，13通过散列函数计算的映射地址也是3，与48的映射地址相同，13和48为同义词。因此，设计散列函数时应尽量减少冲突，如果冲突无法避免，则需要设计处理冲突的方法。

散列函数（Hash function）又称为哈希函数，是将关键字映射到存储地址的函数。

记为：hash(key) = Addr。设计散列函数时需要遵循2个原则：

1）散列函数尽可能简单，能够快速计算出任一关键字的散列地址。

2）散列函数映射的地址应均匀分布整个地址空间，避免聚集，以减少冲突。

散列函数设计原则为：简单、均匀。

设计方法：

1.直接定址法

直接取关键字的某个线性函数作为散列函数，散列函数形式如下：

hash(key) = a*key + b, 其中，a、b为常数。

适用于事先知道关键字，关键字集合不是很大且连续性较好。关键字如果不连续，则有大量空位，造成空间浪费。

例如，学生的学号{30331，30332，30333，30334，30335，......, 303369}。那么可以设计散列函数为：H(key) = key - 30330

这样可以将学生的学号直接映射到存储地址下标。符合简单均匀的原则。

2.除留余数法

除留余数法是一种最简单、最常用的构造散列函数的方法，并且不需要事先知道关键字的分布。假定散列表的表厂为m，取一个不大于表厂的最大素数p,设计散列函数为：

hash(key) = key%p

为什么要选择素数p?

选择p为素数的原因是为了避免冲突。因为在实际应用中，访问往往具有某种周期性，若周期与p有公共的素因子，则冲突的概率将急剧上升。例如，手表中的齿轮，两个交合齿轮的齿数最好是互质的。否则出现齿轮磨损绞断的概率很大。因此，发生冲突的概率随着p所含素因子的增多而迅速增大，素因子越多，冲突越多。

3.随机数法

随机可以让关键字分布的更均匀一些，因此可以将关键字随机化，然后再使用除留余数法得到存储地址。散列函数为：

hash(key） = rand(key) % p

其中，rand()为C、C++中的随机函数，rand(n)表示求0~n-1的随机数。p的取值和除留存余法相同。

4.数字分析法

数字分析法根据每个数字在各个位上的出现概率，选择均匀分布的若干位，作为散列地址。该方法适用于已知关键字集合，通过观察分析得到。

例如，一个关键字集合，如图所示。第1，2位的数字完全相同，不需要考虑。4、7、8位的数字只有个别不同，而3、5、6位的数字均匀分布，可以将3，5，6位的数字作为散列地址，或者将3，5，6位的数字求和作为散列地址。

5.平方取中法

对关键字平方后，按散列表大小，取中间的若干位作为散列地址（平方后截取）。使用于事先不知道关键字的分布且关键码的位数不是很大。

例：散列地址为3位，则关键码10123的散列地址位475：

10123**2 = 102475129

6.折叠法

将关键字从左到右分割成位数相等的几部分，将这几部分叠加求和，取后几位作为散列地址。适用于关键字位数很多，事先不知道关键字分布。折叠法分为 1）移位折叠和 2）边界折叠两种。

移位折叠是将分割后的每个部分的最低位对齐，然后相加求和；

边界折叠如同折纸，将相邻部分沿边界来回折叠，然后对齐相加。

例如：设关键字为 4 5 2 0 7 3 7 9 6 0 3,散列地址为三位。因为散列地址为3位，因此将关键字每3位划分一块，叠加后将进位舍去，移位叠加得到的散列地址位324，边界叠加得到的散列地址位648.如下如所示。

7.基数转换法

例如，将十进制数转换位其它的进制表示，如345的九进制表示为423。另外散列函数大多是基于整数的，如果关键字是浮点数，可以将关键字乘以M并四舍五入得到整数，再使用散列函数，或者将关键字表示为二进制数然后再使用散列函数；如果关键字是字符，可以将字符转换R进制的整数，然后再使用散列函数。

8.全域散列法（很少用，了解）

如果对关键字了解不多，可以使用全域散列法。即将多种备选的散列函数放在一个集合H中，在实际应用中，随机选择其中的一个作为散列函数。如果任意两个不同的关键字key1 ≠ key2，hash(key1) = hase(key2)的散列函数个数最多位H/m,H最为集合中散列函数的个数，m为表长，则称H是全域的。

冲突处理方法

无论如何设计散列函数，都无法避免冲突问题。如果发生冲突，就需要进行冲突处理。冲突处理方法分为3种：开放地址法，链地址法，建立公共溢出区。

1.开放地址法

开放地址法是在线性存储空间上的解决方案，也称为闭散列。当发生冲突时，采用冲突处理方法在线性存储空间上探测其他的位置。