【数据结构】考研408 | 散列查找探秘：从数学基石到冲突世界的高效查找入门

导读

大家好，很高兴又和大家见面啦！！！ 在前面的内容中我们学习了两类查找算法：

• 线性查找：顺序查找、折半查找、分块查找
• 树形查找：BST、AVL、RBT、B树、B+树

这些算法各有其特点和适用场景，但也存在一些固有的局限性。

• 线性查找算法（如顺序查找）实现简单，适用于小规模或无序数据集，但当数据量增大时，其 O(N) 的时间复杂度会导致效率显著下降。 虽然 折半查找 将效率提升至 O(\log N)，但它要求数据必须有序，这在数据频繁变动的场景中会因维护有序性而带来额外开销。 分块查找在块与块之间需要保持有序，块内查找仍是线性操作，其效率提升相对有限。
• 树形查找结构（如二叉搜索树BST）在动态操作上表现较好，但若插入顺序不佳，树结构可能退化成链状，导致查找效率也退化为 O(N)。 平衡二叉树（如AVL树、红黑树）通过自平衡操作避免了退化，但维持平衡的旋转操作会增加插入和删除的复杂性。 对于大规模数据，B树 和 B+树 通过多路分支降低树的高度，减少了磁盘I/O次数，但节点结构和管理也更为复杂。

更重要的是，无论是 线性查找 还是 树形查找，在查找过程中都不可避免地要进行一系列关键字的比较操作，比较次数决定了查找效率的上限。 那么，是否存在一种查找方式，能够尽可能地减少比较次数，甚至通过关键字直接定位到存储地址呢？ 答案是肯定的，这就是我们接下来要重点探讨的散列查找（Hash Search）。 散列查找 通过 哈希函数 建立关键字与存储地址的直接映射，理想情况下可以实现 O(1) 的时间复杂度，为我们突破传统比较查找的效率瓶颈提供了全新的思路。 下面，就让我们一起深入探究散列查找的奥秘。

一、定义

散列表（又称 哈希表（Hash Table））：是一种根据关键字而直接进行访问的数据结构。特点是：数据元素的关键字与其存储地址直接相关。 散列函数（也称哈希函数）：一个把查找表中的关键字映射成该关键字对应的地址的函数； 同义词：不同的关键字通过散列函数映射到了同一个值 冲突：通过散列函数确定的位置已经存放了其他元素

二、三要素

散列表 也就是我们所说的 哈希表 ，是一个能够将查找效率降至到 O(1) 的 高效查找表。 我们可以通过 散列函数：H(key)=Addr 来建立关键字与存储地址的联系，从而达到通过关键字直接进行访问的目的；

flowchart LR
	subgraph Key[关键字]
	end
	Hash[散列函数]
	subgraph Addr[地址]
	end
	Key --->Hash--->Addr

可能有朋友不太理解 散列函数 中将 关键字映射到存储地址 这一概念，这里就需要我们从数学函数的角度来进行说明： 在函数中，通常包含三要素：

• 定义域：自变量所有可能取值的集合
  • 自变量：主动变化、自主取值的变量
• 对应法则：表示自变量与因变量之间依赖关系的规则，是函数的灵魂
• 值域：所有可能的函数值（即因变量取值）构成的集合​
  • 因变量：通过对应法则依赖于自变量而确定自身值的变量

在 散列表 中，同样存在三要素：

• 关键字集合：所有 关键字 组成的集合
• 存储地址集合：所有 存储地址 组成的集合
• 散列函数：关键字 与 存储地址 之间依赖关系的规则

从这里我们就不难看出 散列表 的三要素与 函数 的三要素之间的关系：

• 关键字 就是一个 自变量 ，由关键字组成的集合对应的就是 定义域；
• 存储地址 就是一个 因变量，由 存储地址 组成的集合对应的就是 值域；
• 散列函数 就是 关键字 与 存储地址 之间依赖关系的规则，对应的就是 对应法则；

PS: 在实际的应用中，我们常使用 哈希表 ，哈希函数 的说法，因此这里我们直接统一其称呼，在后续的内容中，我们都会使用 哈希；

三、映射关系

理解了 哈希表 的三要素后，下面我们就来说明一下什么是 映射关系； 简单的理解就是 关键字 与 存储地址 之间存在的某种联系，这里我们以我们熟悉的 数组 为例进行说明； 在 数组 中，我们可以通过 数组下标 直接访问对应的 数组元素；

flowchart LR
a[数组下标] ---> b[数组元素]

但是实际的访问过程应该是：

• 通过 数组下标 找到该下标的 存储地址
• 通过 存储地址 找到该地址中存储的 数组元素

flowchart LR
a[数组下标] ---> add[存储地址] ---> b[数组元素]

在前面的学习中我们有介绍过，数组 中，每个下标都会对应一个存储地址，而下标则是当前地址相对于数组起始地址的偏移量：

$$ P_i = Add_i - Add_ 0$$

那也就是说，下标 与 存储地址 之间的关系为：P_i + Add_0 = Add_i。这个关系就是 下标 与 存储地址 之间的 映射关系；

四、冲突

在 哈希表 中，哈希函数 的作用就是在 关键字 与 存储地址 之间构建这么一个 映射关系 ； 这里我们举一个例子，假设我们所使用的 哈希函数 为：

这里的 L 指的是 哈希表 的总长度； 当 key 的取值均不大于 L 时，我们通过 哈希函数 得到的结果都是唯一的，即 关键字与存储地址一一对应。 这就好比当我们取 L = 7 时，从 1 \leq key \leq 7 这个 关键字 的范围中获取的 关键字 的值通过 哈希函数 得到的 存储地址 的值分别为：

$$ \begin{align*} Hash(1) &= 1 \bmod 7 = 1 \ Hash(2) &= 2 \bmod 7 = 2 \ Hash(3) &= 3 \bmod 7 = 3 \ Hash(4) &= 4 \bmod 7 = 4 \ Hash(5) &= 5 \bmod 7 = 5 \ Hash(6) &= 6 \bmod 7 = 6 \ Hash(7) &= 7 \bmod 7 = 0 \ \end{align*} $$

若我们将这些 关键字 通过 哈希函数 获得的值作为 数组下标 存储到一个长度为 7 的 数组 中时，我们就得到了一个 关键字与存储地址一一对应 的 哈希表：

在这个哈希表中，我们进行查找时的效率可以达到 O(1) ； 当我们需要在该表中存储 key = 8 这个 关键字 时，通过 哈希函数 我们所得到的 数组下标 为：Hash(8) = 8 \bmod 7 = 1 ； 可以看到 key = 8 与 key = 1 通过 哈希函数 得到的值相同，这时我们就可以称其为 同义词； 当我们将该 关键字 存储到该 哈希表 中时，我们会发现下标为 1 的位置已经存储了一个 关键字 ，我们将这种情况称为 冲突；

五、局限性

装填因子\alpha ：是评估 哈希表 性能的一个关键参数 其值我们可以通过下面的公式进行获取：

一个 哈希表 性能的好坏我们可以通过 装填因子 进行评估：

• 当 \alpha 的值越大时，发生 冲突 的概率越高
• 当 \alpha 的值越小时，发生 冲突 的概率越低

哈希表 是一种非常高效的数据结构，但它并非完美，确实存在一些固有的局限性；

5.1 哈希冲突

理想情况下，哈希表 的查找时间复杂度为 O(1) ，即 关键字与存储地址之间一一对应； 但是在实际的使用中，冲突无法避免，当频繁的发生 冲突 时，这就会导致 哈希表 的性能下降，最坏的情况就是其查找的时间复杂度退化为 O(N)；

就比如上面这个 哈希表 ，其中每个 关键字 均为 同义词，当我们将其依次存储到 哈希表 中后，我们在后续的查找过程中就已经无法直接通过 哈希函数 直接查找到 目标关键字。 这时的查找过程就从 哈希查找 退化为了 顺序查找 ，其查找的时间复杂度也从 O(1) 退化到了 O(N)；

5.2 哈希函数

除了 哈希表 中存在 哈希冲突 外， 哈希函数 也是直接影响 哈希表 性能的关键； 一个好的 哈希函数 应该尽可能的 减少冲突，这里我们还是以长度为 L = 7 的哈希表为例；

• 哈希函数：Hash(key) = key \bmod L

• 哈希函数：Hash(key) = key \bmod 3

可以看到，在不同的 哈希函数 下，同样的 关键字集合 所得到的 哈希表 也是不同的：

• 在 Hash(key) = key \bmod L 下，不存在 同义词，每个关键字都有 唯一确定 的 存储地址
• 在 Hash(key) = key \bmod 3 下，存在大量的 同义词，因此通过该 哈希函数 得到的 存储地址 会对应多个 关键字 这样就导致了大量的 冲突 ，从而降低了该 哈希表 的性能

因此我们在设计一个 哈希函数 时，应该尽量减少冲突，同时还要设计好 处理冲突的方法；

5.3 空间效率

哈希查找 实际上是一个典型的 空间换时间 的查找算法。为了尽可能的减少冲突，我们希望 每一个关键字有且仅有唯一与之关联的存储地址。 就比如我要存储 0 \leq n \leq 100 这个范围内的任意个 关键字，最简便的方法就是创建一个长度 L \geq 100 的 哈希表 ，这样我们就可以通过 哈希函数 ：Hash(key) = key 使得 关键字 与 存储地址 达到不存在冲突的 映射关系； 那也就是说，当 哈希表 的长度足够大时，我们可以通过 完美哈希函数：Hash(key) = key 来实现高效查找； 但此时就会导致一个问题：当预分配的 哈希表 长度为 100 ，但是我们只存储了 10 个关键字时，这就出现了大量的 空间浪费；

5.4 功能限制

相比于 顺序表 、链表 这种有序结构，哈希表 中数据的存储结构属于 离散存储 ，因此 哈希表不支持高效的范围查询和顺序遍历； 这时有朋友可能就会问了，这个 离散存储 是什么意思？ 简单的说就是 元素 与 元素 之间不存在 线性存储 中的 逻辑与物理位置均相邻 的关系；也不存在 链式存储 中的 逻辑相邻，物理位置不一定相邻 的关系；更不存在 索引存储 中的 索引表与元素相对应 的关系； 那也就是说，我们无法通过一个 元素 或者 索引值 找到另一个 元素 ，唯一能够确定元素位置的方法只有 哈希函数； 因此在 哈希表 中，若要进行顺序遍历，那么只能够得到关键字的 随机顺序；若要进行范围查找，那么只能够逐个判断关键字是否存在于 范围内；

5.5 扩展成本

哈希表 和 顺序表 一样，都是通过预先分配一个固定长度的空间，随后进行数据的存储； 当数据量增长需要扩容时，通常需要重建整个表（Rehashing），这是一次耗时操作； 这就好比 动态顺序表 的扩容操作，在 动态顺序表 中，若当前表长与最大表长相等时，就表明此时的表中已经存满了数据元素，无法继续插入新元素； 若此时我们需要继续向表中插入新元素，我们就需要对 顺序表 进行 扩容：

• 重新申请一块内存空间
• 将原空间中的元素复制到新的空间中
• 释放原空间的内存

完成 扩容 后，我们就能继续向 顺序表 中插入新的元素； 哈希表 的扩容同样如此，为了确保 哈希表 的性能，我们会根据 装填因子\alpha 来判断是否需要进行 扩容 操作:

• 假设我们将 扩容 阈值设置为 \alpha == 0.75
• 当 装填因子\alpha 到达该阈值时，就需要进行 扩容 操作
• 扩容 时需要先在内存中申请一块新的空间
• 为新的 哈希表 构建新的 哈希函数
• 将原 哈希表 中的 关键字 通过新的 哈希函数 存储到新的 哈希表 中
• 释放原 哈希表 的空间

可以看到，哈希表 的 扩容 相比于 动态顺序表 会更加的复杂，整个扩容过程涉及两步关键过程：

• 新 哈希函数 的构建
• 原 哈希表 到新 哈希表 的移植

由于 哈希表 是一个 离散存储 结构，因此移植的过程只能够将元素依次移植，这一过程非常的耗时；

结语

通过本文的学习，我们系统地掌握了 散列查找 的核心原理与特性。 散列查找通过建立关键字与存储地址之间的直接映射，在理想情况下能够实现 O(1) 时间复杂度的查找效率，有效突破了传统基于比较的查找算法在效率上的瓶颈。 我们认识到，散列表的性能主要依赖于三个关键要素：

• 散列函数的设计
• 冲突解决策略​
• 装填因子的合理控制

其中，冲突是散列查找中不可避免的现象，而优秀的 散列函数 能够有效减少冲突的发生。 同时，装填因子 \bm{\alpha}​ 作为 衡量散列表空间利用率和冲突概率的重要指标，通常需要维持在一个合理的范围内以平衡空间与时间效率。 然而，散列查找也存在一些固有的局限性：

• 这是一种典型的以空间换时间的策略，可能导致一定的空间浪费
• 此外，由于其存储的离散性，不支持高效的范围查询和顺序遍历
• 当数据量增长触发扩容时，重新散列（Rehashing）​ 的过程也较为耗时

尽管如此，通过精心设计的 散列函数 和合适的 冲突处理方法，散列查找在大多数需要快速点查询的场景中，依然展现出卓越的性能优势。 至此，我们已经理解了 散列查找的基本原理。而构建高效散列表的核心在于其 散列函数 的设计。 在下一篇内容中，我们将深入探讨 哈希函数的构造方法，详细分析直接定址法、除留余数法、平方取中法等多种经典 散列函数的设计思路、适用场景及优缺点，帮助大家掌握构建高效散列表的关键技能。 互动与分享

• 点赞👍 - 您的认可是我持续创作的最大动力
• 收藏⭐ - 方便随时回顾这些重要的基础概念
• 转发↗️ - 分享给更多可能需要的朋友
• 评论💬 - 欢迎留下您的宝贵意见或想讨论的话题

感谢您的耐心阅读！ 关注博主，不错过更多技术干货。我们下一篇再见！