查找

【考纲内容】

1. 查找的基本概念
2. 顺序查找法
3. 分块查找法
4. 折半查找法
5. B 树及其基本操作、B+ 树的基本概念
6. 散列表
7. 查找算法的分析及应用

【复习提示】

本章是考研命题的重点。对于散列查找，应掌握散列表的构造、冲突处理方法（各种方法的处理过程）、查找成功和查找失败的平均查找长度、散列查找的特征和性能分析。对于折半查找，应掌握折半查找的过程、构造判定树、分析平均查找长度等。B 树和 B+ 树是本章的难点。对于 B 树，考研大纲要求掌握插入、删除和查找的操作过程；对于B+树，仅要求了解其基本概念和性质。

查找的基本概念

• 查找。在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果一般分为两种：一 是查找成功，即在数据集合中找到了满足条件的数据元素；二是查找失败。
• 查找表（查找结构）。用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成，可以是一个数组或链表等数据类型。对查找表经常进行的操作一般有 4 种：
  1. 查询某个特定的数据元素是否在查找表中
  2. 检索满足条件的某个特定的数据元素的各种属性
  3. 在查找表中插入一个数据元素
  4. 从查找表中删除某个数据元素。
• 静态查找表。若一个查找表的操作只涉及上述操作 1 和 2，则无须动态地修改查找表，此类查找表称为静态查找表。与此对应，需要动态地插入或删除的查找表称为动态查找表。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等；适合动态查找表的查找方法有二叉排序树的查找、散列查找等。二叉平衡树和 B 树都是二叉排序树的改进。
• 关键字。数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。例如，在由一个学生元素构成的数据集合中，学生元素中“学号”这一数据项的值唯一地标识一名学生。
• 平均查找长度。在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为：$$ASL=\sum_{i=1}^{n}P_iC_i$$式中，$n$ 是查找表的长度；$P_i$ 是查找第 $i$ 个数据元素的概率，一般认为每个数据元素的查找概率相等，即 $P_i=\frac{1}{n}$；$C_i$ 是找到第 $i$ 个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。

顺序查找和折半查找

顺序查找

顺序查找又称线性查找，主要用于在线性表中进行查找。顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的顺序表的顺序查找。下面分别进行讨论。

一般线性表的顺序查找

作为一种最直观的查找方法，其基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置；若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。下面给出其算法，主要是为了说明其中引入的“哨兵”的作用。

typedef struct {   // 查找表的数据结构（顺序表）
    int *elem;     // 动态数组基址
    int TableLen;  // 表的长度
} SSTable;

// 顺序查找
int Search_Seq(SSTable ST, int key) {
    ST.elem[0] = key;  // "哨兵"，存放在数组索引0的位置
    int i;
    for (i = ST.TableLen; ST.elem[i] != key; --i) {  // 从后往前找
        return i;  // 查找成功，则返回元素下标；查找失败，则返回0
    }
}

在上述算法中，将 ST.elem[0] 称为“哨兵”。引入它的目的是使得 Search_ Seq 内的循环不必判断数组是否会越界，因为满足 i==0 时，循环一定会跳出。需要说明的是，在程序中引入“哨兵”并不是这个算法独有的。引入“哨兵”可以避免很多不必要的判断语句，从而提高程序效率。

对于有 $n$ 个元素的表，给定值 key 与表中第 $i$ 个元素相等，即定位第 $i$ 个元素时，需进行 $n-i+ 1$ 次关键字的比较，即 $C_i=n-i+1$。查找成功时，顺序查找的平均长度为$$ASL=\sum_{i=1}^{n}P_i(n-i+1)$$当每个元素的查找概率相等，即 $P_i=\frac{1}{n}$ 时，有：$$ASL=\sum_{i=1}^{n}P_i(n-i+1)=\frac{n+1}{2}$$查找不成功时，与表中各关键字的比较次数显然是 $n + 1$ 次，从而顺序查找不成功的平均查找长度为 $ASL=n+1$ 。

通常，查找表中记录的查找概率并不相等。若能预先得知每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由小至大重新排列。

综上所述，顺序查找的缺点是当 $n$ 较大时，平均查找长度较大，效率低；优点是对数据元素的存储没有要求，顺序存储或链式存储皆可。对表中记录的有序性也没有要求，无论记录是否按关键字有序，均可应用。同时还需注意，对线性的链表只能进行顺序查找。

有序表顺序查找

若在查找之前就已经知道表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。

假设表 L 是按关键字从小到大排列的，查找的顺序是从前往后，待查找元素的关键字为 key，当查找到第 $i$ 个元素时，发现第 $i$ 个元素对应的关键字小于 key，但第 $i+ 1$ 个元素对应的关键字大于 key，这时就可返回查找失败的信息，因为第 $i$ 个元素之后的元素的关键字均大于 key，所以表中不存在关键字为 key 的元素。

可以用查找判定树来描述有序顺序表的查找过程。树中的圆形结点表示有序顺序表中存在的元素；树中的矩形结点称为失败结点（若有 $n$ 个结点，则相应地有 $n + 1$ 个查找失败结点），它描述的是那些不在表中的数据值的集合。若查找到失败结点，则说明查找不成功。

在有序表的顺序查找中，查找成功的平均查找长度和一般线性表的顺序查找一样。查找失败时，查找指针一定走到了某个失败结点。这些失败结点是我们虚构的空结点，实际上是不存在的，所以到达失败结点时所查找的长度等于它上面的一个圆形结点的所在层数。查找不成功的平均查找长度在相等查找概率的情形下为：$$ASL=\sum_{j=1}^{n} q_j(l_j-1)=\frac{1+2+\cdots+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$$式中，$q_j$ 是到达第 $j$ 个失败节点的概率，在相等查找概率的情况下，它为 $\frac{1}{n+1}$；$l_i$ 是第 $j$ 个失败结点所在的层数。

注意，有序表的顺序查找和后面的折半查找的思想是不一样的，且有序表的顺序查找中的线性表可以是链式存储结构。

折半查找

折半查找又称二分查找，它仅适用于有序的顺序表。

折半查找的基本思想：首先将给定值 key 与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分（例如，在查找表升序排列时，若给定值 key 大于中间元素，则所查找的元素只可能在后半部分）。然后在缩小的范围内继续进行同样的查找，如此重复，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。算法代码实现如下：

int Binary_Search(SeqList L, ElemType key) { // 升序排列
    int low = 0, high = L.TableLen - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;  // 取中间位置
        if (L.elem[mid] == key) {
            return mid;  // 查找成功则返回所在位置
        } else if (L.elem[mid] > key) {
            high = mid - 1;  //从前半部分继续查找}
        } else {
            low = mid + 1;  // 从后半部分继续查找
        }
        return -1;  // 查找失败，返回-1
    }
}

折半查找的过程可用二叉树来描述，称为判定树。树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值；树中最下面的叶结点都是方形的，它表示查找不成功的情况。

从判定树可以看出，查找成功时的查找长度为从根结点到目的结点的路径上的结点数，而查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数；每个结点值均大于其左子结点值，且均小于于其右子结点值。若有序序列有 $n$ 个元素，则对应的判定树有 $n$ 个圆形的非叶结点和 $n+ 1$ 个方形的叶结点。显然，判定树是一棵平衡二叉树。

由上述分析可知，用折半查找法查找到给定值的比较次数最多不会超过树的高度。在等概率查找时，查找成功的平均查找长度为：$$ASL=\frac{1}{n} \sum_{i=1}^{n} l_i=\frac{1}{n}(1\times 1+2\times 2+\cdots +h \times 2^{h-1})=\frac{n+1}{n} \log_{2}{(n+1)}-1\approx \log_{2}{(n+1)-1}$$式中，$h$ 是树的高度，并且元素个数为 $n$ 时树高 $h = \left \lceil \log_{2}{(n+1)} \right \rceil $。所以，折半查找的时间复杂度为 $O(\log_{2}{n})$，平均情况下比顺序查找的效率高。

因为折半查找需要方便地定位查找区域，所以它要求线性表必须具有随机存取的特性。因此，该查找法仅适合于顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排列。

分块查找

分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。

分块查找的基本思想：将查找表分为若干子块。块内的元素可以无序，但块间的元素是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

// 索引表
typedef struct{
    ElemType maxValue;
    int low,high;
}Index;
// 顺序表存储实际元素
ElemType List[100];

分块查找的过程分为两步：

1. 在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表；
2. 在块内顺序查找。

若索引表中不包含目标关键字，则折半查找索引表最终停在 low > high 要在 low 所指分块中查找。原因是最终 low 左边一定小于目标关键字，high 右边一 定大于目标关键字。而分块存储的索引表中保存的是各个分块的最大关键字。

分块查找的平均查找长度为索引查找和块内查找的平均长度之和。设索引查找和块内查找的平均查找长度分别为 $L_I$，$L_S$，则分块查找的平均查找长度为：$$ASL=L_I+L_S$$将长度为 $n$ 的查找表均匀地分为 $b$ 块，每块有 $s$ 个记录，在等概率情况下，若在块内和索引表中均采用顺序查找，则平均查找长度为：$$ASL=L_I+L_S=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2s}$$此时，若 $s=\sqrt{n} $，则平均查找长度取最小值 $\sqrt{n}+1 $；若对索引表采用折半查找时，则平均查找长度为：$$ASL=L_1+L_2= \left \lceil \log_{2}{(b+1)} \right \rceil+\frac{s+1}{2}$$

B 树和 B+ 树

B 树可视化

https://www.cs.usfca.edu/~galles/visualization/BTree.html

B 树及其基本操作

B 树，又称多路平衡查找树，B 树中所有结点的孩子个数的最大值称为 B 树的阶，通常用 $m$ 表示。一棵 $m$ 阶 B 树或为空树，或为满足如下特性的 $m$ 叉树：

1. 树中每个结点至多有 $m$ 棵子树，即至多含有 $m-1$ 个关键字。
2. 若根结点不是终端结点，则至少有两棵子树。
3. 除根结点外的所有非叶结点至少有 $\left \lceil \frac{m}{2} \right \rceil $ 棵子树，即至少含有 $\left \lceil \frac{m}{2} \right \rceil -1$ 个关键字。（保证查找效率）
4. 所有非叶结点的结构如下：[ $n$ | $P_0$ | $K_1$ | $P_1$ | $K_2$ | $P_2$ | $\cdots $| $K_n$ | $P_n$ ]。其中，$K_i\ (i=1,2,\cdots ,n)$ 为结点的关键字，且满足 $K_1<K_2<\cdots K_n$ ；$P_i\ (i=0,1,\cdots ,n)$ 为指向子树根结点的指针，且指针 $P_{i-1}$ 所指子树中所有结点的关键字均小于 $K_i$ ，$P_i$ 所指子树中所有结点的关键字均大于 $K_i$，$n \ (\left \lceil \frac{m}{2} \right \rceil -1\le n \le m-1)$ 为结点中关键字的个数。
5. 所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。（对于任何一个结点，其所有子树的高度都要相同）

$m$ 阶 B 树的核心特性：

1. 根节点的子树数 $\in [2,m]$，关键字数 $\in [i,m-1]$；其他结点的子树数 $\in [ \left \lceil \frac{m}{2} \right \rceil ,m ]$；关键字数 $\in [ \left \lceil \frac{m}{2} \right \rceil -1,m-1 ]$
2. 对于任何一个结点，其所有子树的高度都要相同

B 树是所有结点的平衡因子均等于 0 的多路平衡查找树。

下图所示的 B 树中所有结点的最大孩子数 $m=5$，因此它是一棵 5 阶 B 树，在 $m$ 阶 B 树中结点最多可以有 $m$ 个孩子。

可以借助该实例来分析上述性质：

1. 结点的孩子个数等于该节点中关键字个数加 1。
2. 如果根结点没有关键字就没有子树，此时 B 树为空；如果根节点有关键字，则其子树必然大于等于两棵，因为子树个数等于关键字个数加 1。
3. 除根结点外的所有非终端结点至少有 $\left \lceil \frac{m}{2} \right \rceil = \left \lceil \frac{5}{2} \right \rceil =3$ 棵子树（即至少有 $\left \lceil \frac{m}{2} \right \rceil -1=\left \lceil \frac{5}{2} \right \rceil -1=2$ 个关键字），至多有 5 棵子树（即至多有 4 个关键字）。
4. 结点中关键字从左到右递增有序，关键字两侧均有指向子树的指针，左边指针所指向子树的所有关键字均小于该关键字，右边指针所指子树的所有关键字均大于该关键字。或者看成下层结点关键字总是落在由上层结点关键字所划分的区间内，如第二层最左结点的关键字划分成了 3 个区间：$(-\infty, 5),(5, 11),(11, +\infty)$，该结点 3 个指针所指子树的关键字均落在这 3 个区间内。
5. 所有叶结点均在第 4 层，代表查找失败的位置。

B 树的高度（磁盘存取次数）

B 树中的大部分操作所需的磁盘存取次数与 B 树的高度成正比。

下面来分析 B 树在不同情况下的高度。当然，首先应该明确 B 树的高度不包括最后的不带任何信息的叶结点所处的那一层（有些书对 B 树的高度的定义中，包含最后的那一层）。

若 $n\ge 1$，则对任意一棵包含 $n$ 个关键字、高度为 $h$ 、阶数为 $m$ 的 B 树：

1. 因为 B 树中每个结点最多有 $m$ 棵子树， $m-1$ 个关键字，所以在一棵高度为 $h$ 的 $m$ 阶 B 树中关键字的个数应满足 $n\le (m-1)(1+m+m^2+\cdots +m^{h-1}=mh-1)$ ，因此有 $h\ge \log_{m}{(n+1)}$ 。最小高度
2. 若让每个结点中的关键字个数达到最少，则容纳同样多关键字的 B 树的高度达到最大。由 B 树的定义：第一层至少有 1 个结点；第二层至少有 2 个结点；除根结点外的每个非终端结点至少有 $\left \lceil \frac{m}{2} \right \rceil $ 棵子树，则第三层至少有 $ 2 \left \lceil \frac{m}{2} \right \rceil $ 个结点……第 $h+ 1$ 层至少有 $2(\left \lceil \frac{m}{2} \right \rceil )^{h-1}$ 个结点，注意到第 $h+ 1$ 层是不包含任何信息的叶结点。对于关键字个数为 $n$ 的 B 树，叶结点即查找不成功的结点为 $n+ 1$ ，由此有 $n+ 1\ge 2(\left \lceil \frac{m}{2} \right \rceil )^{h-1}$，即 $h\le \log_{\left \lceil \frac{m}{2} \right \rceil }{(\frac{n+1}{2})+1} $。

故含 $n$ 个关键字、高度为 $h$ 、阶数为 $m$ 的 B 树有：$ \log_{m}{(n+1)}\le h\le \log_{\left \lceil \frac{m}{2} \right \rceil }{(\frac{n+1}{2})+1} $

B 树的查找

在 B 树上进行查找与二叉查找树很相似，只是每个结点都是多个关键字的有序表，在每个结点上所做的不是两路分支决定，而是根据该结点的子树所做的多路分支决定。B 树的查找包含两个基本操作：

1. 在B树中找结点；
2. 在结点内找关键字。

由于 B 树常存储在磁盘上，因此前一个查找操作是在磁盘上进行的，而后一个查找操作是在内存中进行的，即在找到目标结点后，先将结点信息读入内存，然后在结点内采用顺序查找法或折半查找法。在 B 树上查找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应的指针信息到所指的子树中去查找。查找到叶结点时（对应指针为空指针），则说明树中没有对应的关键字，查找失败。

B 树的插入

与二叉查找树的插入操作相比，B树的插入操作要复杂得多。在二叉查找树中，仅需查找到需插入的终端结点的位置。但是,在 B 树中找到插入的位置后，并不能简单地将其添加到终端结点中，因为此时可能会导致整棵树不再满足 B 树定义中的要求。将关键字 key 插入 B 树的过程如下：

1. 定位。利用前述的 B 树查找算法，找出插入该关键字的最低层中的某个非叶结点（在 B 树中查找 key 时，会找到表示查找失败的叶结点，这样就确定了最底层非叶结点的插入位置。注意：插入位置一定是最低层中的某个非叶结点）。
2. 插入。在 B 树中，每个非失败结点的关键字个数都在区间 $[\left \lceil \frac{m}{2} \right \rceil -1,m- 1]$ 内。插入后的结点关键字个数小于 $m$ ，可以直接插入；插入后检查被插入结点内关键字的个数，当插入后的结点关键字个数大于 $m-1$ 时，必须对结点进行分裂。

分裂的方法是：取一个新结点，在插入 key 后的原结点，从中间位置（$\left \lceil \frac{m}{2} \right \rceil $）将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（$\left \lceil \frac{m}{2} \right \rceil $）的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致 B 树高度增 1。

B 树的删除

B 树中的删除操作与插入操作类似，但要稍微复杂一些，即要使得删除后的结点中的关键字个数 $\ge \left \lceil \frac{m}{2} \right \rceil -1$ ，因此将涉及结点的“合并”问题。

当被删关键字 $k$ 不在终端结点（最低层非叶结点）中时，可以用 $k$ 的前驱（或后继） $k’$ 来替代 $k$ ，然后在相应的结点中删除 $k’$， 关键字 $k$ 必定落在某个终端结点中，则转换成了被删关键字在终端结点中的情形。

• 直接前驱：当前关键字左侧指针所指子树中“最右下”的元素。
• 直接后继：当前关键字右侧指针所指子树中“最左下”的元素。

当被删关键字在终端结点（最低层非叶结点）中时，有下列三种情况：

1. 直接删除关键字。若被删除关键字所在结点的关键字个数 $\ge \left \lceil \frac{m}{2} \right \rceil -1$ ，表明删除该关键字后仍满足 B 树的定义，则直接删去该关键字。
2. 兄弟够借。若被删除关键字所在结点删除前的关键字个数$=\left \lceil \frac{m}{2} \right \rceil -1$，且与此结点相邻的右（或左）兄弟结点的关键字个数$\ge \left \lceil \frac{m}{2} \right \rceil$，则需要调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法），以达到新的平衡。当右兄弟很宽裕时，用当前结点的后继、后继的后继来填补空缺；当左兄弟很宽裕时，用当前结点的前驱、前驱的前驱来填补空缺。
3. 兄弟不够借。若被删除关键字所在结点删除前的关键字个数 $=\left \lceil \frac{m}{2} \right \rceil -1$，且此时与该结点相邻的左、右兄弟结点的关键字个数均 $=\left \lceil \frac{m}{2} \right \rceil -1$，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并。在合并过程中，双亲结点中的关键字个数会减 1 。 若其双亲结点是根结点且关键字个数减少至 0 （根结点关键字个数为 1 时，有 2 棵子树），则直接将根结点删除，合并后的新结点成为根；若双亲结点不是根结点，且关键字个数减少到 $=\left \lceil \frac{m}{2} \right \rceil -2$，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合 B 树的要求为止。

B+ 树的基本概念

B+ 树是应数据库所需而出现的一种 B 树的变形树。

一棵 $m$ 阶的 B+ 树需满足下列条件：

1. 每个分支结点最多有 $m$ 棵子树（孩子结点）。
2. 非叶根结点至少有两棵子树，其他每个分支结点至少有 $\left \lceil \frac{m}{2} \right \rceil $ 棵子树。
3. 结点的子树个数与关键字个数相等。
4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。(支持顺序查找)
5. 所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针。（类似分块查找）

$m$ 阶的 B+ 树与 $m$ 阶的 B 树的主要差异如下：

1. 在 B+ 树中，具有 $n$ 个关键字的结点只含有 $n$ 棵子树，即每个关键字对应一棵子树；而在 B 树中，具有 $n$ 个关键字的结点含有 $n+1$ 棵子树。
2. 在 B+ 树中，每个结点（非根内部结点）的关键字个数 $n$ 的范围是 $\left \lceil \frac{m}{2} \right \rceil \le n \le m$ （根结点：$1\le n \le m$）；在 B 树中，每个结点（非根内部结点）的关键字个数 $n$ 的范围是 $\left \lceil \frac{m}{2} \right \rceil -1 \le n \le m-1 $ （根结点：$1\le n \le m-1$）。
3. 在 B+ 树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
4. 在 B+ 树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在 B 树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

分支结点的某个关键字是其子树中最大关键字的副本。通常在 B+ 树中有两个头指针：一个指向根结点，另一个指向关键字最小的叶结点。因此，可以对 B+ 树进行两种查找运算：一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找。

B+ 树的查找、插入和删除操作和 B 树的基本类似。只是在查找过程中，非叶结点上的关键字值等于给定值时并不终止，而是继续向下查找，直到叶结点上的该关键字为止。所以，在 B+ 树中查找时，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径。

在 B+ 树中，非叶结点不含有该关键字对应记录的存储地址。可以使一个磁盘块可以包含更多个关键字，使得 B+ 树的阶更大，树高更矮，读磁盘次数更少，查找更快。

散列表

散列表的基本概念

在前面介绍的线性表和树表的查找中，记录在表中的位置与记录的关键字之间不存在确定关系，因此，在这些表中查找记录时需进行一系列的关键字比较。这类查找方法建立在“比较”的基础上，查找的效率取决于比较的次数。

散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为 Hash(key)=Addr （这里的地址可以是数组下标、索引或内存地址等）。

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词。一方面，设计得好的散列函数应尽量减少这样的冲突；另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。

散列表：根据关键字而直接进行访问的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。

理想情况下，对散列表进行查找的时间复杂度为 $O(1)$，即与表中元素的个数无关。下面分别介绍常用的散列函数和处理冲突的方法。

散列函数的构造方法

在构造散列函数时，必须注意以下几点：

1. 散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。
2. 散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生。
3. 散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址。

下面介绍常用的散列函数：

直接定址法

直接取关键字的某个线性函数值为散列地址，散列函数为$H(\mathrm{key} )=\mathrm{key} $ 或 $H(\mathrm{key})=a\times \mathrm{key} +b$ 式中，$a$ 和 $b$ 是常数。

这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

除留余数法

这是一种最简单、最常用的方法，假定散列表表长为 $m$，取一个不大于 $m$ 但最接近或等于 $m$ 的质数 $p$ ，利用以下公式把关键字转换成散列地址。散列函数为 $H(\mathrm{key})=\mathrm{key} % p$

除留余数法的关键是选好 $p$ ，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性。

数字分析法

设关键字是 $r$ 进制数（如十进制数），而 $r$ 个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些， 每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

平方取中法

顾名思义，这种方法取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。
在不同的情况下，不同的散列函数具有不同的性能，因此不能笼统地说哪种散列函数最好。在实际选择中，采用何种构造散列函数的方法取决于关键字集合的情况，但目标是为了尽量降低产生冲突的可能性。

处理冲突的方法

应该注意到，任何设计出来的散列函数都不可能绝对地避免冲突。为此，必须考虑在发生冲突时应该如何处理，即为产生冲突的关键字寻找下一个“空”的 Hash 地址。用 $H_i$ 表示处理冲突中第 $i$ 次探测得到的散列地址，假设得到的另一个散列地址 $H_1$ 仍然发生冲突，只得继续求下一个地址 $H_2$，以此类推，直到 $H_k$ 不发生冲突为止，则 $H_k$ 为关键字在表中的地址。

拉链法（链接法）

显然，对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。假设散列地址为 $i$ 的同义词链表的头指针存放在散列表的第 $i$ 个单元中，因而查找、插入和删除操作主要在同义词链中进行。拉链法适用于经常进行插入和删除的情况。

开放定址法

所谓开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为$$H_i=H(\mathrm{key})+d_i % m$$式中，$H(\mathrm{key})$ 为散列函数；$i=0,1,2,\cdots ,k \ (k \le m-1)$；$m$ 表示散列表长；$d_i$ 为增量序列。取定某一增量序列后，对应的处理方法就是确定的。通常有以下 4 种取法：

1. 线性探测法。当 $d_i=0,1,2,\cdots ,m-1$ 时，称为线性探测法。这种方法的特点是：冲突发生时，顺序查看表中下一个单元（探测到表尾地址 $m-1$ 时，下一个探测地址是表首地址 0 ），直到找出一个空闲单元（当表未填满时一定能找到- 一个空闲单元）或查遍全表。线性探测法可能使第 $i$ 个散列地址的同义词存入第 $i+ 1$ 个散列地址，这样本应存入第 $i+1$ 个散列地址的元素就争夺第 $i+2$ 个散列地址的元素的地址…从而造成大量元素在相邻的散列地址上，“聚集”(或堆积）起来，大大降低了查找效率。
2. 平方探测法。当 $d_{i} = {0^2} ,{1^2}, {-1^2} ,{2^2} ,{-2^2}, \cdots ,{k^2} ,{-k^2}$ 时，称为平方探测法，其中 $k \le \frac{m}{2}$ ，散列表长度 $m$ 必须是一个可以表示成 $4k+3$ 的素数，又称二次探测法。平方探测法是一种较好的处理冲突的方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。
3. 伪随机序列法。当 $d_i=$ 伪随机数序列时，称为伪随机序列法。
4. 再散列法。除了原始的散列函数 $H(\mathrm{key})$ 之外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止。

注意：在开放定址的情形下，不能随便物理删除表中的已有元素，因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址。因此，要删除-一个元素时，可给它做一个删除标记，进行逻辑删除。但这样做的副作用是:执行多次删除后，表面，上看起来散列表很满，实际上有许多位置未利用，因此需要定期维护散列表，要把删除标记的元素物理删除。

散列查找及性能分析

散列表的查找过程与构造散列表的过程基本一致。对于一个给定的关键字 key ，根据散列函数可以计算出其散列地址，执行步骤如下：

初始化： Addr=Hash(key);

1. 检测查找表中地址为 Addr 的位置上是否有记录，若无记录，返回查找失败；若有记录，比较它与 key 的值，若相等，则返回查找成功标志，否则执行步骤 2 。
2. 用给定的处理冲突方法计算“下一个散列地址”，并把 Addr 置为此地址，转入步骤 1 。

对同一组关键字，设定相同的散列函数，则不同的处理冲突的方法得到的散列表不同，它们的平均查找长度也不同。

从散列表的查找过程可见：

1. 虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需要以平均查找长度作为衡量散列表的查找效率的度量。
2. 散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子。

装填因子。散列表的装填因子一般记为 $\alpha $，定义为一个表的装满程度，即：$\alpha =\frac{n}{m}$ 式中 $n$ 表示表中记录数，$m$ 表示散列表长度。

散列表的平均查找长度依赖于散列表的装填因子 $\alpha $，而不直接依赖于 $n$ 或 $m$ 。直观地看，$\alpha $ 越大，表示装填的记录越“满”，发生冲突的可能性越大，反之发生冲突的可能性越小。