什么是查找表

查找表是由同一类型的数据元素构成的集合。

一般对于查找表有以下操作：

在查找表中查找某个具体的数据元素
在查找表中插入数据元素
在查找表中删除数据元素
…

静态查找表和动态查找表

在查找表中只做查找操作，而不改动表中数据元素，称此类查找表为静态查找表；

在查找表中做查找操作的同时进行插入数据或者删除数据的操作，称此类表为动态查找表。

关键字

在查找表中查找某个特定元素时，前提是需要知道这个元素的一些属性。例如，每个人上学的时候都会有自己唯一的学号，因为你的姓名、年龄都有可能和其他人是重复的，唯独学号不会重复。而学生具有的这些属性（学号、姓名、年龄等）都可以称为关键字。
关键字又细分为主关键字和次关键字。若某个关键字可以唯一地识别一个数据元素时，称这个关键字为主关键字，例如学生的学号就具有唯一性；反之，像学生姓名、年龄这类的关键字，由于不具有唯一性，称为次关键字。

如何进行查找？

不同的查找表，其使用的查找方法是不同的。例如每个人都有属于自己的朋友圈，都有自己的电话簿，电话簿中数据的排序方式是多种多样的，有的是按照姓名的首字母进行排序，这种情况在查找时，就可以根据被查找元素的首字母进行顺序查找；有的是按照类别（亲朋好友）进行排序。在查找时，就需要根据被查找元素本身的类别关键字进行排序。

顺序查找算法

静态查找表既可以使用顺序表表示，也可以使用链表表示。虽然一个是数组、一个是链表，但两者在做查找操作时，基本上大同小异。

向顺序表的一端添加用户用于搜索的关键字，称作“监视哨”。

顺序查找的实现

见代码。

顺序查找的性能分析

查找算法衡量好坏的依据为：查找成功时，查找的关键字和查找表中的数据元素中进行过比较的个数的平均值，称为平均查找长度（Average Search Length，用 ASL 表示）。

例如，对于具有 n 个数据元素的查找表，查找成功的平均查找长度的计算公式为：

注意：Pi 为第 i 个数据元素被查找的概率，所有元素被查找的概率的和为 1；Ci 表示在查找到第 i 个数据元素之前已进行过比较的次数。若表中有 n 个数据元素，查找第一个元素时需要比较 n 次；查找最后一个元素时需要比较 1 次，所以有
Ci = n – i + 1 。

一般情况，表中各数据元素被查找的概率是未知的。假设含有 n 个数据元素的查找表中，各数据被查找的概率是相同的，则：

换算后，得：

对于含有 n 个数据的表来说，每次查找失败，比较的次数都是 n+1。所以顺序查找算法的平均查找长度的计算公式为：

二分查找算法

在某些情况下相比于顺序查找，使用二分查找算法的效率更高。但是该算法使用的前提是静态查找表中的数据必须是有序的。

二分查找的实现

见代码。

二分查找的性能分析

二分查找的运行过程可以用二叉树来描述，这棵树通常称为“判定树”。

对于具有 n 个结点（查找表中含有 n 个关键字）的判定树，它的层次数至多为：log2n↓ + 1（如果结果不是整数，则做取整操作，例如：log2(11) +1 = 3 + 1 = 4）。

同时，在查找表中各个关键字被查找概率相同的情况下，二分查找的平均查找长度为：ASL = log2(n+1)–1。

总结

通过比较二分查找的平均查找长度，同前面介绍的顺序查找相对比，明显二分查找的效率要高。但是二分查找算法只适用于有序表，同时仅限于查找表用顺序存储结构表示。

二叉查找树（二叉排序树）

动态查找表中做查找操作时，若查找成功可以对其进行删除；如果查找失败，即表中无该关键字，可以将该关键字插入到表中。动态查找表的表示方式有多种，本节介绍一种使用树结构表示动态查找表的实现方法——二叉查找树（又称为“二叉排序树”）。

什么是二叉查找树？

二叉查找树要么是空二叉树，要么具有如下特点：

二叉查找树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；
二叉查找树中，如果其根结点有右子树，那么右子树上所有结点的值都大于根结点的值；
二叉查找树的左右子树也要求都是二叉查找树；

使用二叉查找树查找关键字

二叉查找树中查找某关键字时，查找过程类似于次优二叉树，在二叉查找树不为空树的前提下，首先将被查找值同树的根结点进行比较，会有 3 种不同的结果：

如果相等，查找成功；
如果比较结果为根结点的关键字值较大，则说明该关键字可能存在于其左子树中；
如果比较结果为根结点的关键字值较小，则说明该关键字可能存在于其右子树中；

具体实现：

见代码。

使用二叉查找树插入关键字

二叉查找树本身是动态查找表的一种表示形式，有时会在查找过程中插入或者删除表中元素，当因为查找失败而需要插入数据元素时，该数据元素的插入位置一定位于二叉查找树的叶子结点，并且一定是查找失败时访问的最后一个结点的左孩子或者右孩子。

一个无序序列可以通过构建一颗二叉查找树，从而变成一个有序序列。

具体实现：

见代码。

使用二叉查找树删除关键字

在查找过程中，如果在使用二叉查找树表示的动态查找表中删除某个数据元素时，需要在成功删除该结点的同时，依旧使这棵树为二叉查找树。假设要删除的为结点 p，则对于二叉查找树来说，需要根据结点 p 所在不同的位置作不同的操作，有以下 3 种可能：
1、结点 p 为叶子结点，此时只需要删除该结点，并修改其双亲结点的指针即可； 2、结点 p 只有左子树或者只有右子树，此时只需要将其左子树或者右子树直接变为结点 p 双亲结点的左子树即可； 3、结点 p 左右子树都有，此时有两种处理方式：

令结点 p 的左子树为其双亲结点的左子树；结点 p 的右子树为其自身直接前驱结点的右子树，

用结点 p 的直接前驱（或直接后继）来代替结点 p，同时在二叉查找树中对其直接前驱（或直接后继）做删除操作。如图 4 为使用直接前驱代替结点 p

具体实现：

见代码。

总结

使用二叉查找树在查找表中做查找操作的时间复杂度同建立的二叉树本身的结构有关。即使查找表中各数据元素完全相同，但是不同的排列顺序，构建出的二叉查找树大不相同。

使用二叉查找树实现动态查找操作的过程，实际上就是从二叉查找树的根结点到查找元素结点的过程，所以时间复杂度同被查找元素所在的树的深度（层次数）有关。

平衡二叉树（AVL树）

平衡二叉树，又称为 AVL 树。实际上就是遵循以下两个特点的二叉树：

每棵子树中的左子树和右子树的深度差不能超过 1；
二叉树中每棵子树都要求是平衡二叉树；

注意：其实就是在二叉树的基础上，若树中每棵子树都满足其左子树和右子树的深度差都不超过 1，则这棵二叉树就是平衡二叉树。

平衡因子：每个结点都有其各自的平衡因子，表示的就是其左子树深度同右子树深度的差。平衡二叉树中各结点平衡因子的取值只可能是：0、1 和 -1。

二叉查找树转换为平衡二叉树

当平衡二叉树由于新增数据元素导致整棵树的平衡遭到破坏时，就需要根据实际情况做出适当的调整，假设距离插入结点最近的“不平衡因子”为 a。则调整的规律可归纳为以下 4 种情况：

单向右旋平衡处理

若由于结点 a 的左子树为根结点的左子树上插入结点，导致结点 a 的平衡因子由 1 增至 2，致使以 a 为根结点的子树失去平衡，则只需进行一次向右的顺时针旋转，如下图这种情况：

单向左旋平衡处理

如果由于结点 a 的右子树为根结点的右子树上插入结点，导致结点 a 的平衡因子由 -1 变为 -2，则以 a 为根结点的子树需要进行一次向左的逆时针旋转，如下图这种情况：

双向旋转（先左后右）平衡处理

如果由于结点 a 的左子树为根结点的右子树上插入结点，导致结点 a 平衡因子由 1 增至 2，致使以 a 为根结点的子树失去平衡，则需要进行两次旋转操作，如下图这种情况：

注意：图 7 中插入结点也可以为结点 C 的右孩子，则（b）中插入结点的位置还是结点 C 右孩子，（c）中插入结点的位置为结点 A 的左孩子。

双向旋转（先右后左）平衡处理

如果由于结点 a 的右子树为根结点的左子树上插入结点，导致结点 a 平衡因子由 -1 变为 -2，致使以 a 为根结点的子树失去平衡，则需要进行两次旋转（先右旋后左旋）操作，如下图这种情况：

注意：图 8 中插入结点也可以为结点 C 的右孩子，则（b）中插入结点的位置改为结点 B 的左孩子，（c）中插入结点的位置为结点 B 的左孩子。

具体实现

见代码。

总结

使用平衡二叉树进行查找操作的时间复杂度为 O(logn)。

B-Tree（平衡多路查找树）

一颗 m 阶的 B-Tree，或者本身是空树，否则必须满足以下特性:

树中每个结点至多有 m 棵子树；
若根结点不是叶子结点，则至少有两棵子树；
除根之外的所有非终端结点至少有棵子树；

所有的非终端结点中包含下列信息数据：（n，A0，K1，A1，K2，A2，…，Kn，An）；

n 表示结点中包含的关键字的个数，取值范围是：m/2↑-1≤n≤m-1。Ki （i 从 1 到 n）为关键字，且 Ki < Ki+1；Ai代表指向子树根结点的指针，且指针Ai-1 所指的子树中所有结点的关键字都小于Ki，An
所指子树中所有的结点的关键字都大于Kn。

所有的叶子结点都出现在同一层次，实际上这些结点都不存在，指向这些结点的指针都为 NULL；

如下图所示就是一棵 4 阶的 B-Tree，这棵树的深度为 4：

下图是深度为 4 的 B-Tree :

在使用 B-Tree 进行查找操作时，例如在如图所示的 B-Tree 中查找关键字 47 的过程为：

从整棵树的根结点开始，由于根结点只有一个关键字 35，且 35 < 47，所以如果 47 存在于这棵树中，肯定位于 A1 指针指向的右子树中；
然后顺着指针找到存有关键字 43 和 78 的结点，由于 43 < 47 < 78，所以如果 47 存在，肯定位于 A1 指针所指的子树中；
然后找到存有 47、53 和 64 三个关键字的结点，最终找到 47，查找操作结束； B-Tree 中插入关键字（构建 B-Tree）

B-Tree构建过程，也是从空树开始，通过不断地插入新数据元素构建的。但是 B-Tree 构建的过程同前面章节的二叉查找树和平衡二叉树不同，B-Tree 在插入新的数据元素时并不是每次都向树中插入新的结点。

因为对于 m 阶的 B-Tree 来说，在定义中规定所有的非终端结点（终端结点即叶子结点，其关键字个数为 0）中包含关键字的个数的范围是[m/2↑ -1, m-1]
，所以在插入新的数据元素时，首先向最底层的某个非终端结点中添加，如果该结点中的关键字个数没有超过 m-1，则直接插入成功，否则还需要继续对该结点进行处理。

可以总结出以下结论：

在构建 B-Tree 的过程中，假设 p 结点中已经有 m-1 个关键字，当再插入一个关键字之后，此结点分裂为两个结点，如下图所示

提示：如图 9 所示，结点分裂为两个结点的同时，还分裂出来一个关键字 K⌈m/2⌉，存储到其双亲结点中。

B-Tree 中删除关键字

在 B-Tree 中删除关键字时，首先前提是找到该关键字所在结点，在做删除操作的时候分为两种情况，一种情况是删除结点为 B-Tree 的非终端结点（不处在最后一层）；另一种情况是删除结点为 B-Tree 最后一层的非终端结点。

例如图 3 来说，关键字 24、45、53、90 属于不处在最后一层的非终端结点，关键字 3、12、37 等属于最后一层的非终端结点。

如果该结点为非终端结点且不处在最后一层，假设用 Ki 表示，则

只需要找到指针 Ai 所指子树中最小的一个关键字代替 Ki，同时将该最小的关键字删除即可。

如果该结点为最后一层的非终端结点，有下列 3 种可能：

被删关键字所在结点中的关键字数目不小于⌈m/2⌉ ，则只需从该结点删除该关键字 Ki 以及相应的指针 Ai 。
被删关键字所在结点中的关键字数目等于⌈m/2⌉ -1，而与该结点相邻的右兄弟结点（或者左兄弟）结点中的关键字数目大于⌈m/2⌉
-1，只需将该兄弟结点中的最小（或者最大）的关键字上移到双亲结点中，然后将双亲结点中小于（或者大于）且紧靠该上移关键字的关键字移动到被删关键字所在的结点中。
被删除关键字所在的结点如果和其相邻的兄弟结点中的关键字数目都正好等于⌈ m/2⌉ -1，假设其有右兄弟结点，且其右兄弟结点是由双亲结点中的指针 Ai所指，则需要在删除该关键字的同时，将剩余的关键字和指针连同双亲结点中的
Ki一起合并到右兄弟结点中。

总结

由于 B-Tree 具有分支多层次少的特点，使得它更多的是应用在数据库系统中。

B-Tree 结构的数据可以让系统高效的找到数据所在的磁盘块，为了描述 B-Tree，首先定义一条记录为一个二元组[key, data]，key 为记录的键值，对应表中的主键值，data 为一行记录中除主键外的数据，对于不同的记录，key
值互不相同。

Tree 中的每个结点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个 3 阶的 B-Tree:

B+Tree

本节介绍一种应文件系统所需而生的一种 B-Tree 的变型树 — B+Tree。

什么是 B+Tree?

一颗 m 阶的 B+Tree 和 m 阶的 B-Tree 的差异在于：

有 n 棵子树的结点中含有 n 个关键字；

在上一节中，在 B-Tree 中的每个结点关键字个数 n 的取值范围为⌈m/2⌉-1≤n ≤ m-1，而在B+Tree中每个结点中关键字个数n的取值范围为：⌈m/2⌉≤n ≤m。

所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序连接。
所有的非终端结点（非叶子结点）可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。

例如，图 1 中所示的就是一棵深度为 4 的 3 阶 B+Tree：

如图 1 所示，B+Tree 中含有两个头指针，一个指向整棵树的根结点，另一个指向关键字最小的叶子结点。同时所有的叶子结点依据其关键字的大小自小而大顺序连接，所有的叶子结点构成了一个以 sqt 指针为头指针的链表。

所以，B+Tree 可以进行两种查找运算：一种是利用 sqt 链表做顺序查找，另一种是从树的根结点开始，进行类似于二分查找的查找方式。

在 B+Tree 中，所有非终端结点都相当于是终端结点的索引，而所有的关键字都存放在终端结点中，所有在从根结点出发做查找操作时，如果非终端结点上的关键字恰好等于给定值，此时并不算查找完成，而是要继续向下直到叶子结点。

注意：B+Tree 的查找操作，无论查找成功与否，每次查找操作都是走了一条从根结点到叶子结点的路径。

B+Tree 中插入关键字

在 B+Tree 中插入关键字时，需要注意以下几点：

插入的操作全部都在叶子结点上进行，且不能破坏关键字自小而大的顺序；
由于 B+Tree中各结点中存储的关键字的个数有明确的范围，做插入操作可能会出现结点中关键字个数超过阶数的情况，此时需要将该结点进行“分裂”；

B+Tree 中做插入关键字的操作，有以下 3 种情况：

若被插入关键字所在的结点，其含有关键字数目小于阶数 M，则直接插入结束
若被插入关键字所在的结点，其含有关键字数目等于阶数 M，则需要将该结点分裂为两个结点，一个结点包含⌊ M/2⌋，另一个结点包含⌈ M/2⌉。同时，将⌈ M/2⌉ 的关键字上移至其双亲结点。假设其双亲结点中包含的关键字个数小于
M，则插入操作完成。
在第 2 情况中，如果上移操作导致其双亲结点中关键字个数大于 M，则应继续分裂其双亲结点。

注意：如果插入的关键字比当前结点中的最大值还大，破坏了 B+Tree 中从根结点到当前结点的所有索引值，此时需要及时修正后，再做其他操作。例如，在图 1 的 B+Tree 种插入关键字 100，由于其值比 97
还大，插入之后，从根结点到该结点经过的所有结点中的所有值都要由 97 改为 100。改完之后再做分裂操作。

B+Tree 中删除关键字

在 B+Tree 中删除关键字时，有以下几种情况：

找到存储有该关键字所在的结点时，由于该结点中关键字个数大于⌈ M/2⌉ ，做删除操作不会破坏 B+Tree，则可以直接删除。
当删除某结点中最大或者最小的关键字，就会涉及到更改其双亲结点一直到根结点中所有索引值的更改。
当删除该关键字，导致当前结点中关键字个数小于⌈ M/2⌉ ，若其兄弟结点中含有多余的关键字，可以从兄弟结点中借关键字完成删除操作。
第 3 种情况中，如果其兄弟结点没有多余的关键字，则需要同其兄弟结点进行合并。
当进行合并时，可能会产生因合并使其双亲结点破坏 B+Tree 的结构，需要依照以上规律处理其双亲结点。

总之，在 B+Tree 中做删除关键字的操作，采取如下的步骤：

删除该关键字，如果不破坏 B+Tree 本身的性质，直接完成操作；
如果删除操作导致其该结点中最大（或最小）值改变，则应相应改动其父结点中的索引值；
在删除关键字后，如果导致其结点中关键字个数不足，有两种方法：一种是向兄弟结点去借，另外一种是同兄弟结点合并。

注意：这两种方式有时需要更改其父结点中的索引值。

总结

本节介绍了有关 B+Tree 的查找、插入和删除操作，由于其更多的是用于文件索引系统，所以没有介绍具体地代码实现，只需要了解实现过程即可。

InnoDB 存储引擎就是用 B+Tree 实现其索引结构。

B+Tree 相对于 B-Tree 有几点不同：

非叶子结点只存储键值信息
所有叶子结点之间都有一个链指针
数据记录都存放在叶子结点中

通常在 B+Tree 上有两个头指针，一个指向根结点，另一个指向关键字最小的叶子结点，而且所有结点（即数据结点）之间是一种链式环结构，因此可以对 B+Tree 进行两种查找运算：一种是利用 sqt
链表做顺序查找，另一种是从树的根结点开始，进行类似于二分查找的查找方式。

InnoDB 存储引擎中页的大小为 16KB，一般表的主键类型为 INT（占用 4 个字节）或 BIGINT（占用 8 个字节），指针类型也一般为 4 或 8 个字节，也就是说一个页（B+Tree 中的一个节点）中大概存储 16KB/(
8B+8B)=1K 个键值（因为是估值，为方便计算，这里的 K 取值为 10^3）。也就是说一个深度为 3 的 B+Tree 索引可以维护 10^3 * 10^3 * 10^3 = 10 亿条记录。

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree 的高度一般都在 2~~4 层。MySQL的 InnoDB 存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要 1~~3 次磁盘 I/O 操作。

数据库中的 B+Tree 所以可以分为聚簇索引和
辅助索引。聚簇索引的叶子结点存放的是整张表的行记录数据，辅助索引和聚簇索引的区别在于辅助索引的叶子结点并不包含记录的全部数据，而是存储相应行数据的索引，即主键，当通过辅助索引来查询数据时，InnoDB
存储引擎会遍历辅助索引找到主键，然后再通过主键在聚簇索引中找到完整的行记录数据。

什么是哈希表（散列表）

前面介绍了静态查找表以及动态查找表中的一些查找方法，其查找的过程都无法避免查找表中的数据进行比较，查找算法的效率很大程序取决于同表中数据的查找次数。而哈希表可以通过关键字直接找到数据的存储位置，不需要进行任何的比较，其查找的效率相较于前面所介绍的查找算法是更高的。

哈希表的构建

哈希表的建立同函数类似，把函数中的 x 用查找记录时使用的关键字来代替，然后将关键字的值带入一个精心设计的公式中，就可以求出一个值，用这个值来表示记录存储的哈希地址。即：数据的哈希地址 = f(关键字的值)

注意：哈希地址只是表示在查找表中的存储位置，而不是实际的物理存储位置。f()是一个函数，通过这个函数可以快速求出该关键字对应的的数据的哈希地址，称之为“哈希函数”。

在构建哈希表时，最重要的是哈希函数的设计。例如设计电话簿案例中的哈希函数为：每个名字的姓的首字母的 ASCII 值即为对应的电话号码的存储位置。这时会发现，张三和赵六两个关键字的姓的首字母都是
Z，最终求出的电话号码的存储位置相同，这种现象称为冲突。在设计哈希函数时，要尽量地避免冲突现象的发生。

注意：对于哈希表而言，冲突只能尽可能地少，无法完全避免。

哈希函数的构造

常用的哈希函数的构造方法有 6 种：直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。

直接定址法：其哈希函数为一次函数，即以下两种形式：

H(key) = key 或者 H(key) = a*key + b

数字分析法：如果关键字由多位字符或者数字组成，就可以考虑抽取其中的 2 位或者多位作为该关键字对应的哈希地址，在取法上尽量选择变化较多的位，避免冲突发生。
平方取中法：对关键字做平方操作，取中间的几位作为哈希地址，此方法是比较常用的构造哈希函数的方法。
折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后这几部分的叠加和（舍去进位）作为哈希地址，此方法适合关键字位数较多的情况。
除留余数法：若已知整个哈希表的最大长度为 m，可以取一个不大于 m 的数 p，然后对该关键字 key 做取余操作，即 H(key) = key % p。
随机数法：取关键字的一个随机函数值作为它的哈希地址，即 H(key) = random(key)，此方法适用于关键字长度不等的情况。

处理冲突的方法

对于哈希表的建立，需要选取合适的哈希函数，但是对于无法避免的冲突，需要采取适当的措施去处理。通常用的处理冲突的方法有以下几种：

开放地址法

H（key）=（H（key）+ d）MOD m（其中 m 为哈希表的表长，d 为一个增量）。当得出的哈希地址产生冲突时，选取以下 3 种方法中的一种获取 d 的值，然后继续计算，直到计算出的哈希地址不再冲突为止，这 3 种方法为：

线性探测法：d=1，2，3，…，m-1

二次探测法：d=12，-12，22，-22，32，…

伪随机数探测法：d=伪随机数

再哈希法：当通过哈希函数求得的哈希地址同其他关键字产生冲突时，使用另一个哈希函数计算，直到冲突不再发生。
链地址法：将所有产生冲突的关键字所对应的数据全部存储在同一个线性链表中。例如有一组关键字为{19,14,23,01,68,20,84,27,55,11,10,79}，其哈希函数为：H(key)=key MOD
13，使用链地址法所构建的哈希表如图 3 所示：

建立一个公共溢出区：建立两张表，一张为基本表，另一张为溢出表。基本表存储没有发生冲突的数据，当关键字由哈希函数生成的哈希地址产生冲突时，就将数据填入溢出表。

总结

本节主要介绍了哈希表的构造及其在构造过程中对产生的冲突进行处理的方法。在选择具体使用哪种方法时，要根据查找表的实际情况具体问题具体分析。

哈希查找算法

在哈希表中进行查找的操作同哈希表的构建过程类似，其具体实现思路为：对于给定的关键字
K，将其带入哈希函数中，求得与该关键字对应的数据的哈希地址，如果该地址中没有数据，则证明该查找表中没有存储该数据，查找失败：如果哈希地址中有数据，就需要做进一步的证明（排除冲突的影响），找到该数据对应的关键字同 K
进行比对，如果相等，则查找成功；反之，如果不相等，说明在构造哈希表时发生了冲突，需要根据构造表时设定的处理冲突的方法找到下一个地址，同地址中的数据进行比对，直至遇到地址中数据为 NULL（说明查找失败），或者比对成功。

具体实现（开放地址法）

见代码。

查找算法的效率分析

在构造哈希表的过程中，由于冲突的产生，使得哈希表的查找算法仍然会涉及到比较的过程，因此对于哈希表的查找效率仍需以平均查找长度来衡量。

在哈希表的查找过程中需和给定值进行比较的关键字的个数取决于以下 3 个因素：

哈希函数：哈希函数的“好坏”取决于影响出现冲突的频繁程度。但是一般情况下，哈希函数相比于后两种的影响，可以忽略不计。
处理冲突的方式：对于同一组关键字，设定相同的哈希函数，使用不同的处理冲突的方式得到的哈希表是不同的，表的平均查找长度也不同。
哈希表的装填因子：在一般情况下，当处理冲突的方式相同的情况下，其平均查找长度取决于哈希表的装满程度：装的越满，插入数据时越有可能发生冲突；反之则越小。

装填因子=哈希表中数据的个数/哈希表的长度，用字符 α 表示（是数学符号，而不是字符 a）。装填因子越小，表示哈希表中空闲的位置就越多。经过计算，在假设查找表中的所有数据的查找概率相等的情况下，对于表长为 m，数据个数为 n 的哈希表：

其查找成功的平均查找长度约为：-1/α * ln(1-α)

其查找不成功的平均查找长度约为：1/(1-α)

通过公式可以看到，哈希表的查找效率只同装填因子有关，而同哈希表中的数据的个数无关，所以在选用哈希表做查找操作时，选择一个合适的装填因子是非常有必要的。