查找是非数值数据处理中一种常用的基本运算。

（一）查找表及查找效率

查找表：指由同一类型的数据元素（或记录）构成的集合。数据元素之间存在着完全松散的关系。

分类：静态查找表和动态查找表，哈希表是一种动态查找表。

（1）静态查找表

①查询某个“特定”的数据元素是否在查找表中。

②检索某个“特定"的数据元素的各种属性。

静态查找表：只进行元素查询和检索元素属性两种操作。

（2）动态查找表

①在查找表中插入一个数据元素。

②从查找表中删除一个数据元素。

动态查找表：在查找过程中，可能插入原本不存在的数据元素，或者删除已存在的某数据元素。

（3）关键字

关键字是数据元素（或记录）的某个数据项的值，用来识别（标识）这个数据元素（或记录）。

主关键字：指能唯一标识一个数据元素的关键字；

次关键字：指能标识多个数据元素的关键字。

（4）查找

根据给定的某个值，在查找表中确定是否存在一个其关键字等于给定值的记录或数据元素。

若存在，则查找成功，给出整个记录信息，或者指出记录在查找表中的位置：

若不存在，则查找不成功，查找结果用一个“空记录”或“空指针"表示。

（5）平均查找长度

通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量查找算法好坏的依据。

平均查找长度：和给定值进行比较的查询成功的关键字个数的期望值。

（二）顺序查找

从表中一端开始，逐个进行记录关键字和给定值的比较，若相等则查找成功，否则查找失败。

顺序查找的方法，对于顺序存储和链式存储方式的查找表都适用。

从顺序查找的过程可见，e取决于所查记录在表中的位置。若需查找的记录正好是表中的第一个记录时，仅需比在等概率情况下，顺序查找成功的平均查找长度为：(n+1)/2

优缺点：

①在n值较大时，平均查找长度较大，查找效率较低。

②算法简单且适应面广，对查找表结构没有要求。

（三）折半查找（二分查找）

基本思想：先比较查找表中间位置记录的关键字和给定值，若相等，则查找成功；若不等，则缩小范围，直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时（不成功）为止。

折半查找判定树：以当前查找区间的中间位置上的记录作为根，左子表和右子表中的记录分别作为根的左子树和右子树上的结点。

查找成功时，折半查找的过程恰好走了一条从根结点到被查结点的路径，关键字进行比较的次数即为被查找结点在树中的层数。折半查找在查找成功时，进行比较的关键字数最多不超过树的高度。

折半查找比顺序查找的效率高，但要求查找表进行顺序存储且按关键字有序排列。折半查找适用于表不易变动，且又经常进行查找的情况。

（四）索引顺序查找

定义：又称分块查找，是对顺序查找方法的改进。

方法：首先将表分成若干块，每一块中关键字不一定有序，但块之间有序，即后一块中所有记录的关键字均大于前一个块中最大的关键字。此外，还建立了一个“索引表”，索引表按关键字有序。

查找过程分为两步：

①在索引表中确定待查记录所在的块；

②在块内顺序查找。

平均查找长度是两次查找的平均查找长度（块内查找与索引查找）之和。

（五）树表查找

二叉查找树、B-树、红黑树等是常见的以树表方式组织的查找表。

（1）二叉查找树

是一种动态查找表，特点是表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。

根据定义，非空的二叉查找树中左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根结点的关键字，可将二叉查找树看成是一个有序表，其查找过程与折半查找过程相似。

（2）B-树

（3）红黑树

是一种平衡二叉查找树的变体。

（六）哈希查找

思想：记录的关键码与其存储位置之间存在一一对应关系，能很快地由关键码找到记录。

1）哈希造表

哈希表：根据设定的哈希函数Hash（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，该映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。

在哈希表中进行查找操作时，必须计算同一个哈希函数，首先得到待查记录的存储地址，然后到相应存储单元去获得有关信息，再判定查找是否成功。

哈希冲突：对于某个哈希函数Hash和两个关键字K1和K2，如果K1≠K2，却出现Hash(K1)=Hash(K2)。

一般情况下，只能尽可能减少冲突而不能完全避免。

采用哈希法需要考虑：哈希函数的构造和冲突的解决。

2）处理冲突

为出现冲突的关键字找到另一个“空”的哈希地址。

常见处理冲突方法：开放定址法、链地址法（拉链法）、再哈希法、建立公共溢出区法等。

（1）开放定址法

最简单的产生探测序列的方法是线性探测，也就是发生冲突时，顺序地到存储区的下一个单元进行探测。

举例：某记录的=关键字为key，哈希函数值H(key)=j。若在哈希地址j发生冲突（此位置己存放其他元素），则对哈希地址j+1进行探测，若仍有冲突，再对地址j+2进行探测，以此类推，直到将元素存入哈希表。

缺点：线性探测法可能使第i个哈希地址的同义词存入第i+1个哈希地址……可能出现很多元素在相邻哈希地址上“聚集”起来的现象，降低了查找效率。可采用二次探测再散列法或随机探测再散列法，以降低“聚集”现象。

（2）链地址法

是一种经常使用且很有效的方法。将具有相同哈希函数值的记录组织成一个链表，当链域的值为NULL时，表示已没有后继记录。

举例：哈希表表长为11、哈希函数为Hash（key）=key mod 11，对于关键码序列47，34，13，12， 52， 38， 33， 27， 3，使用链地址法构造哈希表。

3）哈希查找

在线性探测法解决冲突的方式下，进行哈希查找有两种可能：

①在某位置上查到了关键字等于key的记录，查找成功；

②按探测序列查不到关键字为key的记录，而又遇到了空单元，表明元素不在表中，表示查找失败。

用链地址法解决冲突构造的哈希表中查找元素，就是根据哈希函数得到元素所在链表的头指针，然后在链表中进行顺序查找的过程。