Loading... # 查找 查找是数据处理领域最常用的一种重要运算，也称为检索。查找的对象可以是线性表，也可以是复杂的树形结构和文件结构。本章主要讨论基于线性表的查找。 <!--more--> ## 基本概念 为了提高查找的速度，也常常针对不同场合采用不同的存储结构。衡量一个查找算法的好坏的依据主要是查找过程中需要执行的平均比较次数，或者称为平均查找长度，通常用E(n)来表示，其中n为线性表中的结点个数。此外，还要考虑算法所需要的附加存储空间，以及算法本身的复杂性等。 为方便起见，在本章以后的讨论中，均假设结点是等长的，查找都是基于关键码的查找，且关键码都是整数。这些假设是合理的，因为，如果结点是不等长，则可以讨论结点的目录表;如果关键码不是整数，则可以在关键码和整数之间建立一一对应的关系。 ## 顺序查找 ```c typedef struct { int key; }T; int SeqSearch(T A[],int key,int n) { int i; for(i=0;i<n;i++) if(A[i].key==key) { printf("seq:key%d is found,subscript is%d\n",key,i); return i; } retrun -1; } ``` 最好为O(1)，最差为O(n)，平均查找长度约为n/2 两种提高查找效率的办法： (1)将查找概率大的数据元素放在线性表的前面，这时检索成功的平均查找长度不会超过$\frac {n+1}2 $ 数学上，上述结论可表述为设$i\lt j , p_i \ge p_j,p_i$为检索第i个元素的概率，$\sum_{i=1}^{n}p_i = 1$则 $$ \sum_{i=1}^{n}p_i\times i \le\frac{n+1}2 $$ 上述结论可由数学归纳法证明。 **证明：** 当n=2时，因 $p_1\cdot1+p_2\cdot2=p_1+p_2+p_2=1+p_2\le1+\frac12=\frac{2+1}2 $ 结论成立。 设上式对于n=k成立，k为大于2的自然娄，当n=k+1时， $$ \begin{equation}\begin{split} \sum_{i=1}^{k+1}p_{i}\cdot i&=\sum_{i=1}^{k}p_{i}\cdot i+p_{k+1}\cdot(k+1)\\ &=\sum_{i=1}^k(p_i+\frac{p_{k+1}}k)\cdot i - \frac1k\sum_{i=1}^k p_{k=1}\cdot i+p_{k+1}\cdot(k+1)\\ &=\sum_{i=1}^k(p_i+\frac{p_{k+1}}k)\cdot i + \frac{p_{k+1}}2(k+1) \end{split}\end{equation} $$ 因 $$ \sum_{i=1}^k(p_i+\frac{p_{i+1}}k)=1 \tag{1} $$ 由归纳假设法得 $$ \sum_{i+1}^k (p_i+\frac {p_{k+1}}k)\cdot i\le\frac{k+1}2 $$ 与 $$ p_{k+1}\le\frac1{k+1} $$ 代入(1)式得 $$ \sum_{i=1}^{k+1}p_{i} \cdot i \le \frac{k+1}2+\frac{p_{k+1}}2\cdot(k+1)\le{k+1+1}2 $$ (2)顺序查找，将关键码先排序，再行进顺序查找，此时，查找失败不必比较到线性表的表尾，平均查找长度将会缩小。 ## 折半查找 如果待查找的结点是顺序存储而且是有序的(已经按关键字排好序)，可以有更高效的查找算法，这就是折半查找算法，也称为“二分法查找算法”。 ```c int BinarySearch(T A[],int key, int n) { int low, high, mid; low=0; high=n-1; while(low<high) { mid=(low+high)>>1; if(key==A[mid].key) { printf("Binary: key %d is found, subscript is %d \n,key,mid); return mid; } else if (key>A[mid].key) low=mid+1; else high=mid-1; } return -1; } ``` 时间复杂度最好是O(1)，最坏是$log_2n$次比较，时间复杂性为$O(log_2n)$ 事实上，当$n=2^j-1$时，用于折半查找的最大比较次数为j次；当$n=2^j-1$时，用于折半查找最大比较次数为j次；当$j=1,2,\cdots$当$2^j-1\lt n\le2^{j+1}-1$时，最大查找长度为 $\lceil log_2(n+1)\rceil$设线性表中的结点数n=2^j-1则平均查找长度为 $E(n)=\frac 1n(\sum_{i=1}^ji\times2^{i-1})=\frac{n+1}nlog_2(n+1)-1$ 有明显的高效率。 ## 分块查找 分块查找要求把一个大的线性表分解成若干块，在每一块中的结点可以任意存放，但块与块之间必须排序。假设排序是按关键码值非递减的，那么，这种块与块之间必须是已排序的要求，实际上就是对于任意的i，第i块中所有结点的关键码值必须都小于第i+1块中所有结点的关键码值。此外，还要建立一个索引表，把每块中的最大关键码值作为索引 表的关键码值，按块的顺序存放一个辅助数组中，显然，这个辅助数组是按关键码值非递减排序的。查找时，首先在索引表中进行查找，确定要找的结点所在的块，由于索引表是排序的，因此，对索引表的查找可以采用顺序查找或折半查找;然后，在相应的块中采用顺序查找，即可查找到对应的结点。 分块查找的平均查找长度由两部分组成，一个是对索引表进行查找的平均查找长度$E_b$，一个是对块内结点进行查找的平均查找长度 $E_w$，总的平均查找长度为$E(n)=(E_b+E_w)$。线性表中共有n个结点，分成大小相等的b块，每块有s=n/b个结点。假定对索引表也采用顺序查找，只考虑查找成功的情况，并假定对每个结点的查找概率是相等的，则对每块的查找概率为1/b，对块内每个结点的查找概率为1/s。因为 $$ E_b=\sum_{i=1}^{b}(i\times 1/b)=\frac{b+1}2 $$ $$ E_w=\sum_{i=1}^s(i\times \frac1s)=\frac{s+1}2 $$ $$ E(n)=E_b+E_w=\frac{b+1}2+\frac{s+1}2=\frac{n+s^2}{2s}+1 $$ 当$s=\sqrt{n} $ $$ E(n)=\sqrt{n}+1 $$ ## 散列查找 ### 概述 散列函数，也称哈希（Hash）函数，利用这个函数，将分散的关键码值映射到一个较小的区间，再利用映射后的值作为访问结点的下标。由于采用了一个转换函数，关键码不一定要求是整数，也可以是字符串，只要针对具体类型的关键码构造一个合适的散列函数，将关键码值转换成整数即可。 假设有一组关键码值为整数的同类型结点，散列函数将关键码值映射到 0～n—1 范围内的整数值。与散列函数相关联的是一个表，其索引范围也是0～n一1。这个表称为散列表或哈希表（Hash Table），该表用来存放结点的数据或数据的引用。 散列函数经常是"多对一"的，这就必然导致了"冲突（Collisions）"，也称为"碰撞"，具有相同散列值的关键码值称为"同义词"。当冲突发生后，两个或多个结点被关联到散列表的同一个表项。但两个结点不可能占据同一个位置，所以，必须设计一种解决冲突的策略。为了更好地讨论冲突及其解决办法以及评价散列法的检索效率，引入一个散列法的重要参数-"负载因子"，负载因子$\alpha$定义为： $$ \alpha=\frac{散列表中的结点数目}{散列表的长度} $$ ### 散列函数 散列函数必须将关键码值映射到指定的 0～n-1范围内的整数值。设计散列函数时，应该考虑两个主要方面∶一是散列函数应该能够有效地减少冲突;二是散列函数必须具有很高的执行效率。有几种主要的散列函数构造方法可以满足这些要求。因为任何不是整数的关键码都可以通过建立 1-1 映射转换成为整数型的关键码，所以，下面的讨论中，假定关键码都是整数。 1. 除留余数法 除留余数法是最常用的一种散列方法，它利用求余数运算将整数型的关键码值映射到0～n—1的范围内。选择一个适当的正整数p，用p去除关键码值，所得余数就是对应关键码值的散列值。这个方法的关键是选取适当的p，如果p为偶数，则它总是把奇数转换成奇数，把偶数转换成偶数，这无疑会增加冲突的发生。如果选择p为10的幂次也不好，因为这等于只取关键码值的最后几位，同样不利于减少冲突。一般地，选p为不大于散列表长度n的最大素数比较好。 2. 数字分析法 当关键码的位数很多时，可以通过对关键码的各位进行分析，丢掉分布不均匀的位，留下分布均匀的位作为散列值。数字分析法只适合于静态的关键码值集合，当关键码值集合发生变化后，必须重新进行数字分析。这无疑限制了数字分析法在实际中的应用。 3. 平方取中法 首先计算关键码值的平方值，然后从平方值的中间位置选取连续若干位，将这些位构成的数作为散列值。 4. 随机乘数法 随机乘数法使用一个随机实数f（$0\le f\lt 1$）。乘积f×key的分数部分在0～1之间，用这个分数部分的值与n（散列表的长度）相乘，乘积的整数部分就是对应的散列值，显然，这个散列值落在0～n-1之间。 5. 折叠法 如果关键码值的位数比散列表长度值的位数多出很多，可以采用折叠法。折叠法是将关键码值分成若干段，其中至少有一段的长度等于散列表长度值的位数，把这些多段数相加、并舍弃可能产生的进位，所得的整数作为散列值。  6. 基数转换法 将关键码值看成是在另一个基数数制上的数，然后把它转换成原来基数上的数，再选择其中的若干位作为散列值。一般取大于原来基数的数作转换的基数，并且两个基数应该是互素的。 ### 冲突的处理 两个或多个数据项可能具有相同的散列值，但它们不能占用散列表的同一个位置。可能的选择只有两种，要么将引起冲突的新数据项存放在表中另外的位置，要么为每个散列值单独建立一个表以存放具有相同散列值的所有数据项。这两种不同的选择代表了解决冲突的两种经典策略，这就是"开放地址法"和"链表地址法"。 **开放地址法** 开放地址法假定散列表的每个表项有一个是否被占用的标志。当试图加入新的数据项到散列表中时，首先判断散列值指定的表项是否已被占用。如果位置已被占用，则依据一定的规则在表中寻找其他空闲的表项。 最简单的探测空闲表项的方法是线性探测法，当冲突发生时，就顺序地探测下一个表项是否空闲。如果 Hash（key）=d，但第d项表项已经被占用，即发生了冲突，那么探测序列为∶d，d＋1，d+2…，n-1，0，1，…，d-1。 一般而言，由于散列表的长度大于实际的数据项，因此，沿着这个探测序列，总可以找到一个空闲的表项。 下面这个算法完成散列表的查找，散列表使用线性探测解决冲突，函数的参数为散列表 ht、要查找的关键码值 key 和散列表的大小 n。 容易发生堆积 **双散列函数探测法** 这个方法是使用2 个散列函数Hash1和 Hash2，其中 Hash1 以关键码值为自变量，产生一个0～n-1 之间的散列值Hash2也以关键码值为自变量，产生一个1～n-1之间的数。当n为素数时，Hash2（key）可以是1～n-1之间的任何数;当n是2的幂次数时，Hash2（key））可以是1～n一1之间的任何奇数。Hash1用来产生基本的散列值，当发生冲突时，利用 Hash2 计算探测序列因此，使用双散列函数探测法，可以使探测序列跳跃式地散列到整个存储区域里，从而有助于减少"堆积"的产生。 设Hashl（key）=d时发生冲突，则再计算 k=Hash2（key），得到探测序列为∶(d+k)%n,(d+2*k)%n，(d+3*k)%n， 算法略 链表地址法是为散列表的每个表项建立一个单链表，用于链接同义词子表，为此，每个表项需增加一个指针域。 同义词子表建立在什么地方呢?有两种不同的处理方法。一种办法是在散列表的基本存储区域外开辟一个新的区域用于存储同义词子表，这种方法称为"分离的同义词子表法"，或称"独立链表地址法"，这个分离的同义词子表所在的区域称为"溢出区"。另一种方法是不建立溢出区，而是将同义词子表存储在散列表所在的基本存储区域里，例如，可以在基本存储区域里从后往前探测空闲表项，找到后就将其链接到同义词子表中，这个方法称为"结合的同义词子表法"，或称"公共链表地址法"。   独立链表地址法是查找效率最好的解决冲突的方法，速度要快于开放地址法，因为独立链表地址法在作散列查找时仅仅需要搜索同义词子表。开放地址法要求表长是固定的，而独立链表地址法中的表项则是动态分配的，其表长仅受内存空间的限制。链表法的主要缺点是需要为每个表项（包括分离的同义词子表的每个结点）设立一个指针域。 ### 散列查找的效率  Last modification：January 20, 2023 © Allow specification reprint Like 如果觉得我的文章对你有用，请留下评论。