Hello 算法：哈希表从 O(1) 查询到冲突与扩容的完整解析

2026-09-06 15:02:52作者：沈韬淼Beryl

本文基于《Hello 算法》（hello-algo）仓库的哈希表文档展开，系统讲解哈希表的核心概念、14 种语言的常用操作 API、基于数组的简单实现原理，以及哈希冲突与扩容机制。读完后，你将掌握用 Python、Java、C++、Go 等语言使用内置哈希表的全部基本操作，理解 index = hash(key) % capacity 这行核心公式背后的原理，并能读懂仓库中从 Python 到 C 的完整 ArrayHashMap 源码实现。

什么是哈希表

哈希表（hash table），又称散列表，通过建立键 key 与值 value 之间的映射，实现高效的元素查询：向哈希表中输入一个键 key，即可在 $O (1)$ 时间内获取对应的值 value。

文档用一个贴近生活的例子说明其动机：给定 $n$ 个学生，每个学生有“姓名”和“学号”两项数据。若希望实现“输入学号，返回姓名”的查询，数组和链表都需要遍历所有元素，而哈希表可以把学号直接映射到存储位置，一步命中。

三种结构的查询效率对比如下（原文档表：元素查询效率对比）：

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

添加元素：数组（链表）只需把元素加到尾部， $O (1)$ ；
查询元素：数组（链表）是乱序的，需要遍历所有元素， $O (n)$ ；
删除元素：需先查询到元素再删除， $O (n)$ 。

结论很直接：在哈希表中进行增删查改的时间复杂度都是 $O (1)$ ，这就是它成为最常用数据结构之一的根本原因。

常用操作：初始化、添加、查询、删除

哈希表的常见操作包括初始化、添加键值对、查询键对应的值、删除键值对。以文档中“学号 → 姓名”的数据为例，各语言的标准写法如下（与 codes/java/chapter_hashing/hash_map.java、codes/cpp/chapter_hashing/hash_map.cpp 等示例源码一致）。

Python：

# 初始化哈希表
hmap: dict = {}

# 添加操作：在哈希表中添加键值对 (key, value)
hmap[12836] = "小哈"
hmap[15937] = "小啰"
hmap[16750] = "小算"
hmap[13276] = "小法"
hmap[10583] = "小鸭"

# 查询操作：向哈希表中输入键 key，得到值 value
name: str = hmap[15937]

# 删除操作：在哈希表中删除键值对 (key, value)
hmap.pop(10583)

Java：

/* 初始化哈希表 */
Map<Integer, String> map = new HashMap<>();

/* 添加操作 */
map.put(12836, "小哈");
map.put(15937, "小啰");
map.put(16750, "小算");
map.put(13276, "小法");
map.put(10583, "小鸭");

/* 查询操作 */
String name = map.get(15937);

/* 删除操作 */
map.remove(10583);

C++：

/* 初始化哈希表 */
unordered_map<int, string> map;

/* 添加操作 */
map[12836] = "小哈";
map[15937] = "小啰";
map[16750] = "小算";
map[13276] = "小法";
map[10583] = "小鸭";

/* 查询操作 */
string name = map[15937];

/* 删除操作 */
map.erase(10583);

Go：

/* 初始化哈希表 */
hmap := make(map[int]string)

/* 添加操作 */
hmap[12836] = "小哈"
hmap[15937] = "小啰"
hmap[16750] = "小算"
hmap[13276] = "小法"
hmap[10583] = "小鸭"

/* 查询操作 */
name := hmap[15937]

/* 删除操作 */
delete(hmap, 10583)

JavaScript：

/* 初始化哈希表 */
const map = new Map();

/* 添加操作 */
map.set(12836, '小哈');
map.set(15937, '小啰');
map.set(16750, '小算');
map.set(13276, '小法');
map.set(10583, '小鸭');

/* 查询操作 */
let name = map.get(15937);

/* 删除操作 */
map.delete(10583);

Rust（注意其 get/remove 返回 Option 来表达“键可能不存在”）：

use std::collections::HashMap;

/* 初始化哈希表 */
let mut map: HashMap<i32, String> = HashMap::new();

/* 添加操作 */
map.insert(12836, "小哈".to_string());
map.insert(15937, "小啰".to_string());
map.insert(16750, "小算".to_string());
map.insert(13279, "小法".to_string());
map.insert(10583, "小鸭".to_string());

/* 查询操作 */
let _name: Option<&String> = map.get(&15937);

/* 删除操作 */
let _removed_value: Option<String> = map.remove(&10583);

其余语言在仓库 codes 目录下均有对应示例文件，四种基本操作可按下表速查：

语言	初始化	添加	查询	删除
C#	`Dictionary<int, string> map = new();`	`map[12836] = "小哈";`	`map[15937]`	`map.Remove(10583);`
Swift	`var map: [Int: String] = [:]`	`map[12836] = "小哈"`	`map[15937]!`	`map.removeValue(forKey: 10583)`
Dart	`Map<int, String> map = {};`	`map[12836] = "小哈";`	`map[15937]`	`map.remove(10583);`
TypeScript	`new Map<number, string>()`	`map.set(12836, '小哈')`	`map.get(15937)`	`map.delete(10583)`
Kotlin	`HashMap<Int, String>()`	`map[12836] = "小哈"`	`map[15937]`	`map.remove(10583)`
Ruby	`hmap = {}`	`hmap[12836] = "小哈"`	`hmap[15937]`	`hmap.delete(10583)`
C	无内置哈希表，需自行实现	—	—	—

值得注意的细节：C 语言未提供内置哈希表，因此仓库 codes/c/chapter_hashing 目录下的示例（如 array_hash_map.c）全部基于数组手工实现。C# 的 Dictionary 还允许在初始化时直接写字面量 { 12836, "小哈" }, ...；TS/JS 示例中还会用 console.info 打印添加、删除前后的表内容以便观察。

三种遍历方式：键值对、键、值

哈希表有三种常用的遍历方式：遍历键值对、单独遍历键、单独遍历值。以 Java 为例（与 hash_map.java 中的“遍历哈希表”段一致）：

/* 遍历键值对 key->value */
for (Map.Entry<Integer, String> kv : map.entrySet()) {
    System.out.println(kv.getKey() + " -> " + kv.getValue());
}
/* 单独遍历键 key */
for (int key : map.keySet()) {
    System.out.println(key);
}
/* 单独遍历值 value */
for (String val : map.values()) {
    System.out.println(val);
}

其他语言的等价写法：

# Python：items() / keys() / values()
for key, value in hmap.items():
    print(key, "->", value)
for key in hmap.keys():
    print(key)
for value in hmap.values():
    print(value)

// Go：range 直接解包键值对
for key, value := range hmap {
    fmt.Println(key, "->", value)
}
for key := range hmap {
    fmt.Println(key)
}
for _, value := range hmap {
    fmt.Println(value)
}

// JS / TypeScript：entries() / keys() / values()
for (const [k, v] of map.entries()) {
    console.info(k + ' -> ' + v);
}
for (const k of map.keys()) {
    console.info(k);
}
for (const v of map.values()) {
    console.info(v);
}

// Rust：对 &map 迭代得到 (键引用, 值引用)
for (key, value) in &map {
    println!("{key} -> {value}");
}
for key in map.keys() {
    println!("{key}");
}
for value in map.values() {
    println!("{value}");
}

C++ 支持范围 for 与迭代器两种写法（kv.first/kv.second 分别取键和值），Dart 用 map.forEach((key, value) {...}) 及 map.keys/map.values，Ruby 用 hmap.entries.each/hmap.keys.each/hmap.values.each。完整多语言版本见原文档 hash_map.md 中的代码选项卡。

基于数组的简单实现：桶与哈希函数

理解哈希表最快的方式，是看它最简单的形态：仅用一个数组来实现。在哈希表中，数组中的每个空位称为桶（bucket），每个桶可存储一个键值对。查询操作就是找到 key 对应的桶，并在桶中获取 value。

那么如何基于 key 定位对应的桶？这由**哈希函数（hash function）**完成。哈希函数的作用是把一个较大的输入空间映射到一个较小的输出空间：输入空间是所有 key，输出空间是所有桶（数组索引）。也就是说，输入一个 key，通过哈希函数就能得到该键值对在数组中的存储位置。其计算分两步：

通过某种哈希算法 hash() 计算得到哈希值；
将哈希值对桶数量（数组长度）capacity 取模，得到对应的桶索引 index。

index = hash(key) % capacity

设 capacity = 100、hash(key) = key（恒等哈希），则哈希函数就是 key % 100。以学号为 key、姓名为 value，12836 % 100 = 36，即存入第 36 号桶。

仓库中给出了 Python、Java、C、C++ 等多语言实现。Python 版 array_hash_map.py 是理解原理的最佳入口，其核心代码将 key 和 value 封装成 Pair 类，哈希表本体 ArrayHashMap 只持有一个 100 长度的桶数组：

class Pair:
    """键值对"""

    def __init__(self, key: int, val: str):
        self.key = key
        self.val = val


class ArrayHashMap:
    """基于数组实现的哈希表"""

    def __init__(self):
        # 初始化数组，包含 100 个桶
        self.buckets: list[Pair | None] = [None] * 100

    def hash_func(self, key: int) -> int:
        """哈希函数"""
        index = key % 100
        return index

    def get(self, key: int) -> str | None:
        """查询操作"""
        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):
        """添加和更新操作"""
        pair = Pair(key, val)
        index: int = self.hash_func(key)
        self.buckets[index] = pair

    def remove(self, key: int):
        """删除操作"""
        index: int = self.hash_func(key)
        # 置为 None，代表删除
        self.buckets[index] = None

    def entry_set(self) -> list[Pair]:
        """获取所有键值对"""
        result: list[Pair] = []
        for pair in self.buckets:
            if pair is not None:
                result.append(pair)
        return result

几个值得注意的实现细节（对应源码 array_hash_map.py）：

hash_func 就是文档公式的直接落地：key % 100；
get 与 put 的开销只是“算一次取模 + 一次数组下标访问”，这正是 $O (1)$ 查询的来源；
remove 是把桶置空（None）而非“擦除数组元素”——数组长度不可变，桶位只是被标记为可用；
entry_set/key_set/value_set 需要线性扫描 100 个桶，遍历复杂度为 $O (n)$ ，与单次 $O (1)$ 查询并不矛盾。

同样的设计在 C 语言中体现为显式内存管理：array_hash_map.c 中 hashFunc(key) 同样返回 key % MAX_SIZE（MAX_SIZE 为 100），put 用 malloc 为新 Pair 及其字符串值分配内存，removeItem 与析构函数 delArrayHashMap 负责逐桶 free。Java 版 array_hash_map.java 则用 List<Pair> 初始化 100 个 null 桶，接口与 Python 版一一对应（hashFunc/get/put/remove/pairSet/keySet/valueSet）。对比这几份源码可以清楚看到：各语言 API 形态不同，但“桶数组 + 取模定位”的内核完全一致。