哈希表与哈希

哈希表基础

哈希表是一种将键映射到值的数据结构，提供了一种高效的数据存储和检索方式。它结合了数组的直接寻址能力和更动态结构的灵活性。哈希表能够实现基本操作的 O(1) 平均时间复杂度。

哈希表的核心思想是使用**哈希函数**将键转换为数组索引（或“桶”），并在该索引处存储或检索相应的值。

哈希表的基本操作包括

搜索：根据键查找值
插入：添加键值对
删除：移除键值对
遍历：遍历所有键值对

来源

哈希函数

哈希函数以键作为输入，并产生数组索引作为输出。一个有效的哈希函数应该

确定性：相同的输入应始终产生相同的输出
高效性：计算应快速
均匀分布：键应均匀分布在数组中，以最大程度地减少冲突

编程语言为不同数据类型提供了内置的哈希函数。例如

数据类型	哈希值特性
整型	通常是整数本身
布尔值	通常为 0 或 1
浮点数	基于二进制表示
字符串	使用字符计算
对象	通常基于内存地址（可自定义）

来源

哈希冲突

当两个不同的键产生相同的哈希值（数组索引）时，会发生哈希冲突。冲突是不可避免的，因为

输入空间（所有可能的键）通常远大于输出空间（数组大小）
鸽巢原理指出，如果物品数量多于容器数量，那么至少有一个容器必须容纳多个物品

处理冲突的两种主要方法是

改进哈希表结构，使其在存在冲突的情况下也能工作
调整哈希表大小，当冲突变得过于频繁时

来源

冲突解决策略

链式寻址（分离链接法）

在此方法中，每个桶包含一个链表，其中存储了所有哈希到相同索引的键值对。当发生冲突时，新的键值对只需添加到该链表中。

链式寻址的操作

搜索：对键进行哈希，访问桶，然后在链表中搜索
插入：对键进行哈希，访问桶，将键值对添加到链表
删除：对键进行哈希，访问桶，在链表中查找并移除

当链表过长时，可以将其转换为平衡二叉搜索树（例如 AVL 树或红黑树），以保持 O(log n) 的查找时间，而非 O(n)。

来源

开放寻址法（Open Addressing）

开放寻址通过在发生冲突时在哈希表中找到另一个可用槽来处理冲突。各种“探测”方法决定了如何找到下一个可用槽。

线性探测

线性探测通过以固定步长（通常为 1）检查连续位置来查找下一个可用槽。

线性探测的挑战是“聚簇”——连续的已占用槽位趋于变得更长，从而增加冲突的可能性。

二次探测

二次探测使用二次函数来确定要检查的下一个位置，这有助于减少聚簇。

双重哈希

双重哈希使用第二个哈希函数来确定步长，从而提供更随机的探测序列。

在开放寻址中，当元素被删除时，它们必须被标记为“墓碑”而不是简单地移除，因为这确保了探测序列在查找时保持完整。

来源

40-73
89-101

负载因子与扩容

哈希表的负载因子定义为

Load Factor = Number of Elements / Number of Buckets

当负载因子超过某个阈值（通常约为 0.7）时，哈希表会进行扩容以减少冲突频率

创建一个容量更大的新数组（通常是原大小的两倍）
将所有现有元素重新哈希到新数组中
用新数组替换旧数组

此操作开销较大（O(n) 时间），但发生频率不高，因此插入操作的均摊成本仍为 O(1)。

来源

哈希算法

常见的哈希算法包括

简单哈希函数:
- 加法哈希
- 乘法哈希
- 异或哈希
- 旋转哈希
密码学哈希函数:
- MD5（128 位输出，现已被认为不安全）
- SHA-1（160 位输出，现已被认为不安全）
- SHA-256（SHA-2 家族的一部分，广泛使用）
- SHA-3（SHA-2 的较新替代方案）

对于哈希表，我们通常在计算桶索引时使用大素数作为模数，以确保键的更好分布。

来源

42-53
82-101

编程语言中的哈希表实现

不同的编程语言使用不同的策略实现哈希表

语言	实现	冲突策略	备注
Python	Dict	开放寻址	使用伪随机探测
Java	HashMap	链式操作	当列表长度 ≥ 8 且数组长度 ≥ 64 时转换为红黑树
Go	Map	链式操作	每个桶限制 8 个键值对，使用溢出桶

来源

性能特征

最佳情况与最坏情况

在最佳情况下，使用完美的哈希函数且没有冲突时，哈希表操作具有 O(1) 的时间复杂度。

在最坏情况下，当所有键哈希到同一个桶时

链式寻址：查找为 O(n)（必须遍历整个链表/树）
开放寻址：查找为 O(n)（必须检查每个位置）

来源

5-7
18-25

哈希表在效率和灵活性之间提供了出色的平衡，使其成为计算机科学中最有用的数据结构之一。由于在正常情况下其操作接近常数时间，它们构成了许多实际应用（从数据库索引到缓存系统）的基础。