|
|
|
查找是非数值数据处理中一种常用的基本运算，查找运算的效率与查找表所采用的数据结构和查找方法密切相关。
|
|
|
|
|
|
查找表是指由同一类型的数据元素（或记录）构成的集合。由于“集合”这种数据结构中的数据元素之间存在着完全松散的关系，因此，查找表是一种非常灵活的数据结构，分为静态查找表和动态查找表，哈希表是一种动态查找表。
|
|
|
|
（1）静态查找表。对查找表经常要进行的两种操作如下：
|
|
|
|
|
|
|
|
|
|
（2）动态查找表。对查找表经常要进行的另外两种操作如下：
|
|
|
|
|
|
|
|
若在查找过程中还可能插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称相应的查找表为动态查找表。
|
|
|
|
（3）关键字。关键字是数据元素（或记录）的某个数据项的值，用它来识别（标识）这个数据元素（或记录）。主关键字是指能唯一标识一个数据元素的关键字；次关键字是指能标识多个数据元素的关键字。
|
|
|
|
（4）查找。根据给定的某个值，在查找表中确定是否存在一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找成功，此时或者给出整个记录的信息，或者指出记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时的查找结果用一个“空记录”或“空指针”表示。
|
|
|
|
（5）平均查找长度。对于查找算法来说，其基本操作是“将记录的关键字与给定值进行比较”。因此，通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量查找算法好坏的依据。
|
|
|
|
为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。
|
|
|
|
对于含有n个记录的表，查找成功时的平均查找长度定义为：
|
|
|
|
|
其中，Pi为对表中第i个记录进行查找的概率，且 ，一般情况下，均认为查找每个记录的概率是相等的，即Pi=1/n；Ci为找到表中其关键字与给定值相等的记录时（为第i个记录），和给定值已进行过比较的关键字个数。显然，Ci随查找方法的不同而不同。
|
|
|
|
|
|
从表中的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字与给定值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。
|
|
|
|
顺序查找的方法对于顺序存储和链式存储方式的查找表都适用。
|
|
|
|
从顺序查找的过程可见，Ci取决于所查记录在表中的位置。若需查找的记录正好是表中的第一个记录时，仅需比较一次；若查找成功时找到的是表中的最后一个记录，则需比较n次。一般情况下，Ci=n-i+1，因此在等概率情况下，顺序查找成功的平均查找长度为：
|
|
|
|
|
|
也就是说，成功查找的平均比较次数约为表长的一半。若所查记录不在表中，则至少进行n次比较才能确定失败。
|
|
|
|
与其他查找方法相比，顺序查找方法在n值较大时，其平均查找长度较大，查找效率较低。但这种方法也有优点，那就是算法简单且适应面广，对查找表的结构没有要求，无论记录是否按关键字有序排列均可应用。
|
|
|
|
|
|
折半查找也称为二分查找，其基本思想是：先令查找表中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时（表明查找不成功）为止。
|
|
|
|
设查找表的元素存储在一维数组r［1..n］中，那么在表中的元素已经按关键字递增（或递减）排序的情况下，进行折半查找的方法是：首先比较key值与表r中间位置（下标为mid）的记录的关键字，若相等，则查找成功。若key>r［mid］.key，则说明待查记录只可能在后半个子表r［mid+1..n］中，下一步应在后半个子表中再进行折半查找；若keyr的前半个子表中进行折半查找。这样通过逐步缩小范围，直到查找成功或子表为空时失败为止。
|
|
|
|
【函数】设有一个整型数组中的元素是按非递减的方式排列的，在其中进行折半查找的算法如下：
|
|
|
|
|
|
折半查找的过程可以用一棵二叉树描述，方法是：以当前查找区间的中间位置上的记录作为根，左子表和右子表中的记录分别作为根的左子树和右子树上的结点，这样构造的二叉树称为折半查找判定树。例如，具有11个结点的折半查找判定树如下图所示，结点中的数字表示元素的序号。
|
|
|
|
|
|
|
从折半查找判定树可以看出，查找成功时，折半查找的过程恰好走了一条从根结点到被查结点的路径，关键字进行比较的次数即为被查找结点在树中的层数。因此，折半查找在查找成功时进行比较的关键字数最多不超过树的高度，而具有n个结点的判定树的高度为 ，所以折半查找在查找成功时和给定值进行比较的关键字个数至多为 。
|
|
|
给判定树中所有结点的空指针域加上一个指向一个方型结点的指针，称这些方型结点为判定树的外部结点（与之相对，称那些圆形结点为内部结点），如下图所示。那么折半查找不成功的过程就是走了一条从根结点到外部结点的路径。和给定值进行比较的关键字个数等于该路径上内部结点个数。因此，折半查找在查找不成功时和给定值进行比较的关键字个数最多也不会超过 。
|
|
|
|
|
|
|
|
那么折半查找的平均查找长度是多少呢？为了方便起见，不妨设结点总数为n=2h-1，则判定树是深度为h=log2（n+1）的满二叉树。在等概率情况下，折半查找的平均查找长度为：
|
|
|
|
|
|
当n值较大时，ASLbs≈log2（n+1）-1。
|
|
|
|
折半查找比顺序查找的效率要高，但它要求查找表进行顺序存储并且按关键字有序排列。因此，折半查找适用于表不易变动，且又经常进行查找的情况。
|
|
|
|
|
|
索引顺序查找又称分块查找，是对顺序查找方法的一种改进。
|
|
|
|
在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的，即后一块中所有记录的关键字均大于前一个块中最大的关键字。此外，还建立了一个“索引表”，索引表按关键字有序，如下图所示。
|
|
|
|
|
|
|
|
因此，查找过程分为两步：第一步在索引表中确定待查记录所在的块；第二步在块内顺序查找。
|
|
|
|
由于分块查找实际上是两次查找的过程，因此整个分块查找的平均查找长度应该是两次查找的平均查找长度（块内查找与索引查找）之和，所以分块查找的平均查找长度为ASLbs=Lb+Lw，其中Lb为查找索引表的平均查找长度，Lw为块内查找时的平均查找长度。
|
|
|
进行分块查找时可将长度为n的表均匀地分成b块，每块含有s个记录，即 。在等概率的情况下，块内查找的概率为 ，每块的查找概率为 ，若用顺序查找方法确定元素所在的块，则分块查找的平均查找长度为：
|
|
|
|
|
可见，其平均查找长度在这种条件下不仅与表长n有关，而且和每一块中的记录数s有关。可以证明，当s取 时，ASLbs取最小值 ，这时的查找效率较顺序查找要好得多，但远不及折半查找。
|
|
|
|
|
|
二叉查找树、B-树、红黑树等是常见的以树表方式组织的查找表。
|
|
|
|
|
|
二叉查找树是一种动态查找表，其特点是表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。
|
|
|
|
根据定义，非空的二叉查找树中左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根结点的关键字，因此，可将二叉查找树看成是一个有序表，其查找过程与折半查找过程相似。
|
|
|
|
在二叉查找树上进行查找的过程为：若二叉查找树非空，将给定值与根结点的关键字值相比较，若相等，则查找成功；若不等，则当根结点的关键字值大于给定值时，到根的左子树中进行查找，否则到根的右子树中进行查找。若找到，则查找过程是走了一条从树根到所找到结点的路径；否则，查找过程终止于一棵空树。
|
|
|
|
设二叉查找树以二叉链表为存储结构，结点的类型定义如下：
|
|
|
|
|
|
|
|
|
|
|
|
二叉查找树是通过依次输入数据元素并把它们插入到二叉树的适当位置上构造起来的，即每读入一个元素，首先在二叉查找树中进行查找，若找到则不再插入，否则根据查找时得到的位置信息进行插入。其过程为：若二叉查找树为空，则为新元素创建结点并作为二叉查找树的根结点；若二叉查找树非空，则将新元素的值与根结点的值相比较，如果小于根结点的值，则继续在左子树中查找，否则在右子树中继续查找，直到某结点的值与新元素的值相等，或者到达空的子树为止，此时创建新元素的结点并替换该空的子树完成插入处理。设关键字序列为｛46，25，54，13，29，91｝，则对应的二叉查找树构造过程如下图（a）~（g）所示。
|
|
|
|
|
|
|
|
从上面的插入过程还可以看到，每次插入的新结点都是二叉查找树上新的叶子结点，因此在进行插入操作时，不必移动其他结点，仅需改动某个结点的指针域，由空变为非空即可。这就相当于在一个有序序列上插入一个记录而不需要移动其他记录。
|
|
|
|
另外，由于一棵二叉查找树的形态完全由输入序列决定，所以在输入序列已经有序的情况下，所构造的二叉查找树是一棵单枝树。从二叉查找树的查找过程可知，这种情况下的查找效率与顺序查找的效率相当。
|
|
|
|
|
|
一棵m阶的B_树，或为空树，或为满足下列特性的m叉树。
|
|
|
|
|
|
|
（3）除根之外的所有非终端结点最少有 棵子树。
|
|
|
|
|
|
（n，A0，K1，A1，K2，A2，…，Kn，An）
|
|
|
其中，Ki（i=1，2，…，n）为关键字，且Ki<Ki+1（i=1，2，…，n-1）；Ai（i=0，1，…，n）为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki（i=1，2，…，n），An所指子树中所有结点的关键字均大于Kn，n为结点中关键字的个数且满足 。
|
|
|
|
（5）所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。
|
|
|
|
|
|
|
|
|
|
由B_树的定义可知，在B_树上进行查找的过程是：首先在根结点所包含的关键字中查找给定的关键字，若找到则成功返回；否则确定待查找的关键字所在的子树并继续进行查找，直到查找成功或查找失败（指针为空）时为止。
|
|
|
B_树上的插入和删除运算较为复杂，因为要保证运算后结点中关键字的个数大于等于 ，因此涉及结点的“分裂”及“合并”问题。
|
|
|
|
在B_树中插入一个关键字时，不是在树中增加一个叶子结点，而是首先在低层的某个非终端结点中添加一个关键字，若该结点中关键字的个数不超过m-1，则完成插入；否则，要进行结点的“分裂”处理。所谓“分裂”，就是把结点中处于中间位置上的关键字取出来插入到其父结点中，并以该关键字为分界线，把原结点分成两个结点。“分裂”过程可能会一直持续到树根。
|
|
|
同样，在B_树中删除一个结点时，首先找到关键字所在的结点，若该结点在含有信息的最后一层，且其中关键字的数目不少于 ，则完成删除；否则需进行结点的“合并”运算。
|
|
|
|
若待删除的关键字所在的结点不在含有信息的最后一层，则将该关键字用其在B_树中的后继替代，然后删除其后继元素，即将需要处理的情况统一转化为在含有信息的最后一层再进行删除运算。
|
|
|
|
|
|
对于前面讨论的几种查找方法，由于记录的存储位置与其关键码之间不存在确定的关系，所以查找时都要通过一系列对关键字的比较，才能确定被查记录在表中的位置，即这类查找方法都建立在对关键字进行比较的基础之上。理想的情况是依据记录的关键码直接得到对应的存储位置，即要求记录的关键码与其存储位置之间存在一一对应关系，通过这个关系，能很快地由关键码找到记录。哈希表就是按这种思想组织的查找表。
|
|
|
|
|
|
根据设定的哈希函数Hash（key）和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表，这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。
|
|
|
|
在构造哈希表时，是以记录的关键字为自变量计算一个函数（称为哈希函数）来得到该记录的存储地址并存入元素，因此在哈希表中进行查找操作时，必须计算同一个哈希函数，首先得到待查记录的存储地址，然后到相应的存储单元去获得有关信息再判定查找是否成功。
|
|
|
|
对于某个哈希函数Hash和两个关键字K1和K2，如果K1≠K2而Hash（K1）=Hash（K2），则称为出现了冲突，对该哈希函数来说，K1和K2则称为同义词。
|
|
|
|
一般情况下，只能尽可能地减少冲突而不能完全避免，所以在建造哈希表时不仅要设定一个“好”的哈希函数，而且要设定一种处理冲突的方法。
|
|
|
|
釆用哈希法主要考虑的两个问题是哈希函数的构造和冲突的解决。
|
|
|
|
|
|
解决冲突就是为出现冲突的关键字找到另一个“空”的哈希地址。常见的处理冲突的方法有开放定址法、链地址法（拉链法）、再哈希法、建立公共溢出区法等，在处理冲突的过程中，可能得到一个地址序列，记为Hi（i=1，2，…，k）。下面简要介绍开放定址法和链地址法。
|
|
|
|
|
|
Hi=（Hash（key）+di）%mi=l，2，…，k（k≤m-1）
|
|
|
|
其中，Hash（key）为哈希函数；m为哈希表的表长；di为增量序列。
|
|
|
|
|
|
.di=1，2，3，…，m-1，称为线性探测再散列。
|
|
|
|
.di=12，-12，22，-22，32，…，±k2（k≤m/2），称为二次探测再散列。
|
|
|
|
|
|
最简单的产生探测序列的方法是进行线性探测。也就是发生冲突时，顺序地到存储区的下一个单元进行探测。
|
|
|
|
例如，某记录的关键字为key，哈希函数值H（key）=j。若在哈希地址j发生了冲突（即此位置已存放了其他元素），则对哈希地址j+1进行探测，若仍然有冲突，再对地址j+2进行探测，以此类推，直到将元素存入哈希表。
|
|
|
|
|
|
|
|
|
|
（b）根据哈希函数，计算出关键码47的哈希地址为3，在该单元处无冲突，因此插入47。此后关键码34和19需要插入的哈希地址1和8处也没有冲突，因此在对应位置直接插入后如下所示。
|
|
|
|
|
|
（c）将关键码12存入哈希地址为1的单元时发生冲突，探测下一个单元（即哈希地址为2的单元），不再冲突，因此将12存入哈希地址为2的单元后如下所示。
|
|
|
|
|
|
（d）将关键码52存入哈希地址为8的单元时发生冲突，探测下一个单元（即哈希地址为9的单元），不再冲突，因此将52存入哈希地址为9的单元后如下所示。
|
|
|
|
|
|
（e）在哈希地址为5的单元存入关键码38，没有冲突；在哈希地址为0的单元中存入关键码33，没有冲突。因此将38和33先后存入哈希地址为5和0的单元后如下所示。
|
|
|
|
|
|
（f）在哈希地址为2的单元存入关键码57时发生冲突，探测下一个单元（即哈希地址为3的单元），仍然冲突，再探测哈希地址为4的单元，不再冲突，因此将57存入哈希地址为4的单元后如下所示。
|
|
|
|
|
|
（g）在哈希地址为8的单元存入关键码63时发生冲突，探测下一个单元（即哈希地址为9的单元），仍然冲突，再探测哈希地址为10的单元，不再冲突，因此将63存入哈希地址为10的单元后如下所示。
|
|
|
|
|
|
（h）在哈希地址为10的单元存入关键码21时发生冲突，用线性探测法解决冲突，算出哈希地址11，不再冲突，因此将21存入哈希地址为11的单元后如下所示，此时得到最终的哈希表。
|
|
|
|
|
|
线性探测法可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“聚集”起来的现象，大大降低了查找效率。为此，可采用二次探测再散列法或随机探测再散列法，以降低“聚集”现象。
|
|
|
|
（2）链地址法。链地址法是一种经常使用且很有效的方法。它将具有相同哈希函数值的记录组织成一个链表，当链域的值为NULL时，表示已没有后继记录。
|
|
|
|
例如，哈希表表长为11、哈希函数为Hash（key）=key mod 11，对于关键码序列47，34，13，12，52，38，33，27，3，使用链地址法构造的哈希表如下图所示。
|
|
|
|
|
|
|
|
|
|
在线性探测法解决冲突的方式下，进行哈希查找有两种可能：第一种情况是在某一位置上查到了关键字等于key的记录，查找成功；第二种情况是按探测序列查不到关键字为key的记录而又遇到了空单元，这时表明元素不在表中，表示查找失败。
|
|
|
|
在用链地址法解决冲突构造的哈希表中查找元素，就是根据哈希函数得到元素所在链表的头指针，然后在链表中进行顺序查找的过程。
|
|
|
