一、相关定义

查找——查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。所有这些需要被查的数据所在的集合，它的统称叫查找表。

查找表——是由同一类型的数据元素（或记录）构成的集合。

关键字——关键字是数据元素中某个数据项的值，又称为键值，用它可以标识一个数据元素。也可以标识一个记录的某个数据项（字段），称为关键码。若此关键字可以唯一标识一个记录，则称此关键字为主关键字。主关键字所在的数据项称为主关键码。对于那些可以识别多个数据元素（或记录）的关键字，我们称为次关键字。

查找表按照操作方式来分为两大种：静态查找表和动态查找表。
静态查找表——只作查找操作的查找表。它的主要操作有：
（1）查询某个“特定的”数据元素是否在查找表中。
（2）检索某个“特定的”数据元素和各种属性。
动态查找表——在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。动态查找表的操作有两个：
（1）查找时插入数据元素。
（2）查找时删除数据元素。

为了提高查找的效率，需要专门为查找操作设置数据结构，这种面向查找操作的数据结构称为查找结构。从逻辑上来说，查找所基于的数据结构是集合，集合中的记录之间没有本质关系。可是要想获得较高的查找性能，就不能不改变数据元素之间的关系，在存储时可以将查找集合组织成表、树等结构。

二、顺序表查找（时间复杂度为O(n)）

顺序查找，又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

优缺点：

顺序查找是有很大缺点的，n很大时，查找效率极为低下，不过优点也是有的，这个算法非常简单，对静态查找表的记录没有任何要求，在一些小型数据的查找时，是可以适用的。

三、有序表查找（线性有序时的查找）

3.1折半查找

折半查找技术，又叫做二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。
例如：100以内的正整数猜数

优缺点：

由于折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，这样的算法已经比较好了。但对于需要频繁执行插入和删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

3.2插值查找

插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式{key-a[low]}/{a[high]-a[low]}。

优缺点：

它和折半查找的时间复杂度一样，但对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好很多。

3.3斐波那契查找（是一种有序查找）

斐波那契查找是一种有序查找，它是利用了黄金分割原理来实现的。

优缺点：

斐波那契查找的时间复杂度和折半查找、插值查找一样，但就平均性能来说，斐波那契查找要优于折半查找。

四、线性索引查找

索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一项重要技术。

索引按照结构可以分为线性索引、树形索引和多级索引。此处只介绍线性索引。所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。重点介绍三种线性索引：稠密索引、分块索引和倒排索引。

4.1稠密索引

稠密索引是指在线性索引中，将数据集中的每一个记录对应一个索引项，如图所示：

对于稠密索引这个索引表来说，索引项是一定按照关键码有序的排列。索引项有序也就意味着，我们要查找关键字时，可以用折半、插值、斐波那契等有序查找算法，大大提高了效率。

优缺点：

如果数据集非常大，比如上亿，那也就意味着索引也得同样的数据集长度规模，对于内存有限的计算机来说，可能就需要反复去访问磁盘，查找性能反而大大下降了。

4.2分块索引

稠密索引由于索引项与数据集的记录个数相同，所以空间代价很大。为了减少索引项的个数，可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数。

分块有序，是把数据集的记录分成了若干块，并且这些块满足两个条件：
（1）块内无序，即每一块内的记录不要求有序。当然，如果能让块内有序，对查找来说更加理想，不过这就需要付出大量时间和空间的代价，因此通常不要求块内有序。
（2）块间有序，例如，要求第二块所有记录的关键字均要大于第一块中所有记录的关键字，第三块的所有记录的关键字均要大于第二块的所有记录的关键字.......因为只有块间有序，才有可能给查找带来效率。

对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。如图所示：此分块索引的索引项结构分为三个数据项。
（1）最大关键码——它存储每一块中的最大关键字，这样的好处在于可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大。
（2）存储了块中记录的个数，以便于循环时使用。
（3）用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。

在分块索引表中查找，就是分两步进行：
1.在分块索引表中查找要查关键字所在的块。由于分块索引表是块间有序的，因此很容易利用折半、插值等算法得到结果。
2.根据块首指针找到相应的块，并在块中顺序查找关键码。因为块中可以是无序的，因此只能顺序查找。

优缺点：

分块索引的效率比之顺序查找的O(n)是高了不少，不过显然它与折半查找相比还有不小的差距。因此在确定所在块的过程中，由于块间有序，所以可以应用折半、插值等手段来提高效率。总的来说，分块索引在兼顾了对细分块不需要有序的情况下，大大增加了整体查找的速度，所以普遍被用于数据库表查找等技术的应用中。

4.3倒排索引

例如：
1.Books and friends should be few but good.
2.A good book is a good friend.

在这里，这个单词表就是索引表，索引项的通用结构是：
1.次关键码，例如上面的“英文单词”。
2.记录号表，例如上面的“文章编号”。
其中记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）。这样的索引方法就是倒排索引。

优缺点：

倒排索引的优点显然就是查找记录非常快，基本等于生成索引表后，查找时都不用去读取记录，就可以得到结果。但它的缺点是这个记录号不定长，维护比较困难。

五、二叉排序树（动态查找表）

对集合{62,88,58,47,35,73,51,99,37,93}做查找，考虑用二叉树结构，而且是排好序的二叉树来创建，如图所示：

二叉排序树又称为二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树：
（1）若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值。
（2）若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值。
（3）它的左、右子树也分别为二叉排序树。

优缺点：

构造一棵二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。不管如何，在一个有序数据集上的查找，速度总要快于无序的数据集的，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。

二叉排序树总结：

二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为1次，即根结点就是要找的结点，最多也不会超过数的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状。

六、平衡二叉树（AVL树）

平衡二叉树是一种二叉排序树，其中左子树和右子树的高度差至多等于1。将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF，那么平衡二叉树上所有结点的平衡因子只可能是-1,0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，称为最小不平衡子树。如图所示：

平衡二叉树的实现原理：

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。（BF为正右旋，BF为负左旋）

平衡二叉树总结：

如果需要查找的集合本身没有顺序，在频繁查找的同时也需要经常的插入和删除操作，显然我们需要构建一棵二叉排序树，但是不平衡的二叉排序树，查找效率是非常低的，因此需要在构建时，就让这棵二叉排序树是平衡二叉树，此时时间复杂度和有序表查找一样。

七、多路查找树（B树）

多路查找树，其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。

7.1 2-3树

2-3树是这样一棵多路查找树：其中的每一个结点都具有两个孩子（称之为2结点）或三个孩子（称之为3结点）。

一个2结点包含一个元素和两个孩子（或没有孩子），且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。不过，与二叉排序树不一样的是，这个2结点要么没有孩子，要么就有两个孩子，不能只有一个孩子。

一个3结点包含一小一大两个元素和三个孩子（或没有孩子），一个3结点要么没有孩子，要么具有3个孩子。如果某个3结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。

并且2-3树中所有的叶子都在同一层次上。如图所示：是一个有效的2-3树。

2-3树小结：

2-3树复杂的地方就是新结点的插入和已有结点的删除。毕竟，每个结点可能是2结点也可能是3结点，要保证所有叶子都在同一层次，是需要进行复杂操作的。

7.2 2-3-4树

2-3-4树是在2-3树的基础上增加了4结点的使用。一个4结点包含大中小三个元素和四个孩子（或没有孩子），一个4结点要么没有孩子，要么具有4个孩子。如果某个结点有孩子的话，左子树包含小于最小元素的元素；第二子树包含大于最小元素，小于第二元素的元素；第三子树包含大于第二元素，小于最大元素的元素；右子树包含大于最大元素的元素。构建数组为{7,1,2,5,6,9,8,4,3}的2-3-4树的过程，如图所示：

7.3 B树

B树是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶，因此，2-3树是3阶B树，2-3-4树是4阶B树。
一个m阶的B树具有如下属性：
（1）如果根结点不是叶节点，则其至少有两棵子树。
（2）每一个非根的分支结点都有k-1个元素和k个孩子，其中m/2<=k<=m。每一个叶子结点n都有k-1个元素，其中m/2<=k<=m。
（3）所有叶子结点都位于同一层次。
（4）每个结点中的元素从小到大排列，结点当中k-1个元素正好是k个孩子包含的元素的值域分划。
（5）所有分支结点包含下列信息数据（n,A0,K1,A1,K2,A2,...Kn,An），其中：Ki（i=1,2,...n）为关键字，且Ki<Ki+1（i=1,2,...n-1）；Ai（i=0,2,...n）为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki（i=1,2,...n），An所指子树中所有结点的关键字均大于Kn，n（[m/2]-1<=n<=m-1）为关键字的个数（或n+1为子树的个数）。

将下图中的2-3-4树转成B树示意图如下：左侧灰色方块表示当前结点的元素个数。

B树小结：

在B树上查找的过程是一个顺时针查找结点和在结点中查找关键字的交叉过程。由于B树每结点可以具有比二叉树多得多的元素，所以与二叉树的操作不同，它们减少了必须访问结点和数据块的数量，从而提高了性能。可以说，B树的数据结构就是为内外存的数据交互准备的。

7.4 B+树

B+树是应文件系统所需而出的一种B树的变形树。在B树中，每一个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支结点上。而在B+树中，出现在分支结点中的元素会被当做它们在该分支结点位置的中序后继者（叶子结点）中再次列出。另外，每一个叶子结点都会保存一个指向后一叶子结点的指针。如图所示就是一棵B+树，灰色关键字即是根结点中的关键字在叶子结点再次列出，并且所有叶子结点都链接在一起。

一棵m阶的B+树和m阶的B树的差异在于：
（1）有n棵子树的结点中包含有n个关键字。
（2）所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小到大顺序链接。
（3）所有分支结点可以看成是索引，结点中仅含有其子树中的最大（或最小）关键字。

B+树小结：

B+树的结构特别适合带有范围的查找。B+树的插入、删除过程也都与B树类似，只不过插入和删除的元素都是在叶子结点上进行而已。

八、散列表查找（哈希表）

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。对应关系f称为散列函数，又称为哈希函数。按这个思想，采用散列技术将记录存储在一块联系的存储空间中，这块连续存储空间称为散列表或哈希表。那么关键字对应的记录存储位置称为散列地址。

散列表查找步骤：

（1）在存储时，通过散列函数计算记录的散列地址，并按此地址存储该记录。
（2）当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录。

散列表查找小结：

散列技术既是一种存储方法也是一种查找方法。散列技术的记录之间不存在什么逻辑关系，它只与关键字有关。因此，散列主要是面向查找的存储结构。

散列技术最适合的求解问题是查找与给定值相等的记录。对于查找来说，简化了比较过程，效率就大大提高。但散列技术也有缺点：
（1）比如那种同样的关键字，它能对应很多记录的情况，却不适合用散列技术。
（2）同样散列表也不适合范围查找。

九、散列函数的构造方法

两个关键字key1不等于key2，但是却有f（key1）=f（key2），这种现象叫做冲突，并把key1和key2称为这个散列函数的同义词。

好的散列函数有两个原则：
（1）计算简单：散列函数的计算时间不应该超过其他查找技术与关键字比较的时间。
（2）散列地址分布均匀：尽量让散列地址均匀的分布在存储空间中，这样可以保证存储空间的有效利用，并减少为处理冲突而耗费的时间。

9.1直接定址法

如果要统计80后出生年份的人口数，如表所示，我们对出生年份这个关键字可以用年份减去1980来作为地址，此时f（key）=key-1980。

取关键字的某个线性函数值为散列地址，即：f（key）=a*key+b（a、b为常数）

小结：

这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。由于这样的限制，在现实应用中，此方法虽然简单，但却不常用。

9.2数字分析法

如果关键字是位数较多的数字，例如电话号，如表所示：

选择后面的四位称为散列地址就是不错的选择。如果这样的抽取工作还是容易产生冲突，还可以对抽取出来的数字再进行反转、右环移位、左环移位等方法。总的目的就是为了提供一个散列函数，能够合理的将关键字分配到散列表的各位置。

小结：

抽取方法是使用关键字的一部分来计算散列存储位置的方法，这在散列函数中是常常用到的手段。数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。

9.3平均取中法

如果关键字是1234，那么它的平方就是1522756，再抽取中间的三位227用做散列地址。

小结：

平均取中法比较适合于不知道关键字的分布、而位数又不是很大的情况。

9.4折叠法

折叠法是将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

小结：

折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。

9.5除留余数法

此方法为最常用的构造散列函数方法。对于列表长为m的散列函数公式为：f(key)=key mod p （p<=m）
mod是取模。事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。很显然，本方法的关键就在于选择合适的p，p如果选得不好就会容易产生同义词。

9.6随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址。也就是f(key)=random(key)。此处的random是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

十、处理散列冲突的方法

开放定址法、再散列函数法、链地址法、公共溢出区法

总结

二叉排序树是动态查找最重要的数据结构，它可以在兼顾查找性能的基础上，让插入和删除也变得效率较高。不过为了达到最优的状态，二叉排序树最好是构造成平衡的二叉树才最佳。

B树这种数据结构是针对内存与外存之间的存取而专门设计的。由于内外存的查找性能更多取决于读取的次数，因此在设计中要考虑B树的平衡和层次。

散列表是一种非常高效的查找数据结构，在原理上也与前面的查找不尽相同，它回避了关键字之间反复比较的繁琐，而是直接一步到位查找结果。当然，这也就带来了记录之间没有任何关联的弊端。应该说，散列表对于那种性能要求高，记录之间关系无要求的数据有非常好的适用性