Hash Map 哈希表完全指南：从 O(1) 查找原理到冲突与扩容机制（Hello 算法）

2026-09-06 19:22:45作者：姚月梅Lane

文章导读

哈希表（Hash Table，又称 Hash Map）是一种以键值对（key-value pair）为存储单位、能在 $O (1)$ 时间内完成查找、插入与删除的高效数据结构。本文是 hello-algo 仓库中 en/docs/chapter_hashing/hash_map.md 一章的系统化解读，将带你理解哈希表为何快、如何在 14 种编程语言中使用标准库操作哈希表、如何仅用数组从零实现一个最小可用哈希表，以及哈希冲突与扩容（resizing）的底层原理。读完本文，你将不仅会用各种语言的 Map/Dictionary API，更能从源码层面讲清"哈希函数 → 桶索引 → 冲突 → 扩容 → 负载因子"这条完整链路。

认识哈希表：用学号换名字的 O(1) 词典

哈希表（hash table / hash map）存储的是从键 key 到值 value 的映射，其核心价值在于：给定一个键 key，可以在 $O (1)$ 时间内取回对应的值 value。

想象一个经典场景：有 $n$ 名学生，每人有"姓名"和"学号"两条信息。若想支持"输入学号、返回姓名"的查询，就可以把学号当作键、姓名当作值存入哈希表，构成下图所示的映射结构。

为什么哈希表比数组和链表更值得关注？让我们先横向对比三种同样能实现"查询"功能的数据结构。数组与链表的增删查改成本如下：

添加元素：直接在数组（链表）末尾追加，耗时 $O (1)$ ；
查询元素：数组（链表）无序，需遍历所有元素，耗时 $O (n)$ ；
删除元素：需先定位目标元素再删除，定位成本就是一次 $O (n)$ 的查找。

三种数据结构的元素查询效率对比如下表：

操作	数组	链表	哈希表
查找元素	$O (n)$	$O (n)$	$O (1)$
添加元素	$O (1)$	$O (1)$	$O (1)$
删除元素	$O (n)$	$O (n)$	$O (1)$

可以清晰看到：哈希表的插入、删除、查找、更新操作时间复杂度全部为 $O (1)$ 。这正是它在数据库索引、缓存系统、编译器符号表等场景中无处不在的根本原因。

哈希表的常见操作：14 种语言的增查删与遍历

哈希表的常用操作包括：初始化、查询、添加键值对、删除键值对。仓库中对应的可运行示例分布在各个语言的 chapter_hashing 目录下，例如 Python 版为 en/codes/python/chapter_hashing/hash_map.py、Java 版为 en/codes/java/chapter_hashing/hash_map.java 等。

初始化、添加、查询与删除

以下示例以学号为键、姓名为值：先向表中添加 5 条记录，再查询学号 15937 对应的姓名，最后删除学号 10583 的记录。

Python（内置 dict，源码见 hash_map.py）：

# Initialize hash table
hmap: dict = {}

# Add operation
# Add key-value pair (key, value) to hash table
hmap[12836] = "XiaoHa"
hmap[15937] = "XiaoLuo"
hmap[16750] = "XiaoSuan"
hmap[13276] = "XiaoFa"
hmap[10583] = "XiaoYa"

# Query operation
# Input key into hash table to get value
name: str = hmap[15937]

# Delete operation
# Delete key-value pair (key, value) from hash table
hmap.pop(10583)

C++（std::unordered_map，注意 C++ 中不存在的内置哈希表由标准库提供）：

/* Initialize hash table */
unordered_map<int, string> map;

/* Add operation */
// Add key-value pair (key, value) to hash table
map[12836] = "XiaoHa";
map[15937] = "XiaoLuo";
map[16750] = "XiaoSuan";
map[13276] = "XiaoFa";
map[10583] = "XiaoYa";

/* Query operation */
// Input key into hash table to get value
string name = map[15937];

/* Delete operation */
// Delete key-value pair (key, value) from hash table
map.erase(10583);

Java（HashMap<K, V>）：

/* Initialize hash table */
Map<Integer, String> map = new HashMap<>();

/* Add operation */
map.put(12836, "XiaoHa");
map.put(15937, "XiaoLuo");
map.put(16750, "XiaoSuan");
map.put(13276, "XiaoFa");
map.put(10583, "XiaoYa");

/* Query operation */
String name = map.get(15937);

/* Delete operation */
map.remove(10583);

C#（Dictionary<K, V>）：可通过集合初始化器一次性写入 5 条记录，查询用索引器 map[15937]，删除用 map.Remove(10583)：

/* Initialize hash table */
Dictionary<int, string> map = new() {
    { 12836, "XiaoHa" }, { 15937, "XiaoLuo" },
    { 16750, "XiaoSuan" }, { 13276, "XiaoFa" },
    { 10583, "XiaoYa" }
};

/* Query operation */
string name = map[15937];

/* Delete operation */
map.Remove(10583);

Go（内置 map，仓库中以 hash_map_test.go 呈现）：

/* Initialize hash table */
hmap := make(map[int]string)

/* Add operation */
hmap[12836] = "XiaoHa"
hmap[15937] = "XiaoLuo"
hmap[16750] = "XiaoSuan"
hmap[13276] = "XiaoFa"
hmap[10583] = "XiaoYa"

/* Query operation */
name := hmap[15937]

/* Delete operation */
delete(hmap, 10583)

其余语言的核心 API 归纳如下，均可直接对照运行仓库内对应文件：

Swift [Int: String]：赋值 map[12836] = "XiaoHa"，查询 let name = map[15937]!（可选解包），删除 map.removeValue(forKey: 10583)；
JavaScript / TypeScript Map：map.set(12836, 'XiaoHa')、map.get(15937)、map.delete(10583)；
Dart Map<int, String>：map[12836] = "XiaoHa"、String name = map[15937]、map.remove(10583)；
Rust std::collections::HashMap：map.insert(12836, "XiaoHa".to_string())、map.get(&15937)（返回 Option<&String>）、map.remove(&10583)（返回 Option<String>）；
Kotlin HashMap<Int,String>：map[12836] = "XiaoHa"、val name = map[15937]、map.remove(10583)；
Ruby：hmap[12836] = "XiaoHa"、name = hmap[15937]、hmap.delete(10583)。

需要注意的语言差异：

C 语言标准库不提供内置哈希表。仓库在 hash_map.c 中以注释明示 "C does not provide a built-in hash table"，C 语言读者请直接参考后续"基于数组的简单实现"，或学习仓库中基于 uthash 的工程级做法（见 codes/c/utils/uthash.h）与开放寻址/链式实现的完整源码。
Python、C++、Java、Go、C#、JS/TS、Dart、Kotlin、Ruby、Swift、Rust 等语言，数据结构底层实现（如是否有序、是否允许空键、扩容阈值）各不相同，但"键→值"的对外语义一致。

三种遍历方式

哈希表常见的遍历方式有三种：遍历键值对、仅遍历键、仅遍历值。以 Python 与 Go 为例：

Python：

# Traverse hash table
# Traverse key-value pairs key->value
for key, value in hmap.items():
    print(key, "->", value)
# Traverse keys only
for key in hmap.keys():
    print(key)
# Traverse values only
for value in hmap.values():
    print(value)

Go：

/* Traverse hash table */
for key, value := range hmap {
    fmt.Println(key, "->", value)
}
for key := range hmap {
    fmt.Println(key)
}
for _, value := range hmap {
    fmt.Println(value)
}

各语言对应写法速查：

Java：map.entrySet() 遍历键值对（Map.Entry<Integer,String>）、map.keySet()、map.values()；
C#：foreach (var kv in map) 遍历键值对、map.Keys、map.Values；
C++：基于范围的 for (auto kv : map) 或显式迭代器 for (auto iter = map.begin(); iter != map.end(); iter++)；
JS / TS：map.entries()、map.keys()、map.values()；
Dart：map.forEach((key, value) {...})、map.keys.forEach(...)、map.values.forEach(...)；
Rust：for (key, value) in &map、map.keys()、map.values()；
Kotlin：for ((key, value) in map)、map.keys、map.values；
Ruby：hmap.entries.each { |key, value| ... }、hmap.keys.each、hmap.values.each；
Swift：for (key, value) in map、map.keys、map.values。

对 Python 读者，仓库还提供了 Python Tutor 可视化执行链接（位于原文档折叠块中），可逐步观察哈希表内存变化，建议配合 Python 版 driver 代码一起阅读。

用数组实现最小哈希表：桶与哈希函数

理解了"怎么用"，下一步是"怎么实现"。

先考虑最简单的情形：仅用数组实现一个哈希表。在哈希表中，数组中每个空槽位称为一个桶（bucket），每个桶可存放一个键值对。一次查找 = 先为 key 找到所属的桶，再读取桶中存放的 value。

那么如何为给定 key 找到正确的桶？答案是哈希函数（hash function）。哈希函数将较大的输入空间映射到较小的输出空间：在哈希表中，输入空间是全部 key 的集合，输出空间是全部桶（即数组下标）的集合。换句话说，给定一个 key，哈希函数决定了该键值对在数组中的存放位置。

给定 key 计算桶下标只需两步：

用哈希算法 hash() 算出哈希值；
将哈希值对桶数量（数组长度）capacity 取模，得到 key 对应的桶（数组下标）index：

index = hash(key) % capacity

随后即可用 index 访问哈希表对应桶并取回 value。

假设数组长度 capacity = 100、哈希算法为 hash(key) = key，则哈希函数退化为 key % 100。下图以学号为键、姓名为值，展示了该哈希函数的工作流程。

仓库用 Pair 类封装键与值、再以数组承载 Pair，实现了完整的最小哈希表。以 Python 为例（完整源码见 en/codes/python/chapter_hashing/array_hash_map.py）：

class Pair:
    """Key-value pair"""
    def __init__(self, key: int, val: str):
        self.key = key
        self.val = val

class ArrayHashMap:
    """Hash table based on array implementation"""

    def __init__(self):
        """Constructor"""
        # Initialize array with 100 buckets
        self.buckets: list[Pair | None] = [None] * 100

    def hash_func(self, key: int) -> int:
        """Hash function"""
        index = key % 100
        return index

    def get(self, key: int) -> str | None:
        """Query operation"""
        index: int = self.hash_func(key)
        pair: Pair = self.buckets[index]
        if pair is None:
            return None
        return pair.val

    def put(self, key: int, val: str):
        """Add and update operation"""
        pair = Pair(key, val)
        index: int = self.hash_func(key)
        self.buckets[index] = pair

    def remove(self, key: int):
        """Remove operation"""
        index: int = self.hash_func(key)
        # Set to None to represent removal
        self.buckets[index] = None
    ...

这段代码的核心设计可以拆成四点理解：

容量与哈希函数：构造时创建 100 个桶，hash_func 采用 key % 100 取模，二者必须保持一致的约定关系；
添加即覆盖：put 中 self.buckets[index] = pair 意味着如果新键与旧键落到同一桶，后者会直接覆盖前者（这正是"若此时发生冲突，数据将被静默覆盖"的隐患，见下一节）；
删除置空：remove 把桶位置置为 None 表示删除，不真正搬动元素，因此删除同样是 $O (1)$ ；
三种遍历视图：entry_set()、key_set()、value_set() 均通过扫描全部桶、跳过 None 空位来收集结果，复杂度为 $O (n)$ ——可见遍历与增删查的性质不同。

同样的实现思路在仓库中以多种语言平行呈现，可作为横向对照学习材料：Java 版 en/codes/java/chapter_hashing/array_hash_map.java（用 List<Pair> 模拟桶数组）、C 版 en/codes/c/chapter_hashing/array_hash_map.c（用 Pair *buckets[MAX_SIZE] 且需手动 malloc/free 管理内存），以及 C++、Go、JS、TS、Swift、Rust、Ruby、Kotlin、Dart、C#、Zig 等对应实现。注意 C 版还需借助 uthash 等第三方库才能在工程中直接使用标准哈希表。

哈希冲突：为什么不同键会落到同一个桶

从根本上看，哈希函数把"全部键的输入空间"映射到"全部数组下标的输出空间"，而输入空间往往远大于输出空间，因此理论上必然存在不同的输入映射到同一输出的情况。

以上一小节的 key % 100 为例：当两个键的后两位相同时，哈希函数输出就会相同。比如查询学号 12836 与 20336 的两位学生：

12836 % 100 = 36
20336 % 100 = 36

如下图所示，两个学号映射到了同一个桶。若按上一节最简单的 put 实现，后写入者会覆盖先写入者，导致查询结果错误。我们把这种"多个输入映射到同一输出"的情况称为哈希冲突（hash collision）。

一个直观的结论是：哈希表容量越大，多个键落入同一桶的概率越低、冲突越少。因此扩容（扩大哈希表容量）是缓解冲突最直接的手段。

扩容（Resizing）：以空间换时间与负载因子

下图展示了扩容前后的对比：扩容前，键值对 (136, A) 与 (236, D) 在 key % 100 下发生冲突；将容量扩为 200、改用 key % 200 后，二者被分到不同桶，冲突随之消失。

但扩容是有代价的，具体体现在两个方面：

迁移成本：与数组扩容类似，哈希表扩容需要把原有键值对全部搬运到新表，这是昂贵的全量操作；
重算位置：由于哈希表容量 capacity 改变，必须用新哈希函数对每个键值对重新计算存储位置，进一步放大了扩容开销。

正因如此，编程语言通常预先申请足够大的容量以避免频繁扩容。例如在 Java 的 HashMap 中，只有当负载因子超过 $0.75$ 时，系统才会把哈希表扩到原容量的两倍。

负载因子（load factor） 是哈希表最重要的指标之一，定义为"表中元素个数 ÷ 桶的个数"，用来衡量冲突的严重程度，也常被用作触发扩容的阈值：

负载因子越小 → 桶越空 → 冲突越少 → 空间浪费越多；
负载因子越大 → 桶越挤 → 冲突越多 → 查找退化风险越高；
工程实现中一般取 $0.75$ 附近的经验值作为扩容触发线，兼顾时间与空间。

上述基于数组的实现到"哈希冲突与扩容"为止，已经暴露出两个关键未解问题：一是冲突后如何正确存储多个键值对（而不是互相覆盖），二是如何设计更优的哈希算法以摊平键分布。这两部分正是仓库中后续章节的主题——解决前者见 hash_collision.md 的链式地址与开放寻址两种解法（对应可运行示例为 hash_map_chaining.py 与 hash_map_open_addressing.py），解决后者见 hash_algorithm.md。本章总结与习题见 summary.md 与 exercises.md。

小结：从 API 到底层的完整知识链

回顾全文，哈希表这条知识线可浓缩为四个递进的层次：

为什么用：与数组、链表的 $O (n)$ 查找相比，哈希表的增、删、查、改都是 $O (1)$ ，适合一切"按键取值的场景"；
怎么用：14 种语言中，Python dict、C++ unordered_map、Java HashMap、Go map、C# Dictionary、JS/TS Map、Rust HashMap 等 API 语义一致，均可增、查、删、遍历；
怎么实现：仅用数组即可实现，核心是"桶 + 哈希函数 index = hash(key) % capacity"，仓库 array_hash_map.py 等 14 种语言源码提供了可直接运行的对照实现；
有什么坑与对策：输入空间大于输出空间导致冲突必然存在，扩容可降低冲突概率但需全量迁移并重算位置，负载因子（如 Java 的 0.75 阈值）用来平衡时空开销并触发扩容。