企业官网建设流程全解析

Hello 算法图解：基于数组实现哈希表 ArrayHashMap——桶、哈希函数与增删查操作的完整实现

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本篇基于 hello-algo 仓库中codes/pythontutor/chapter_hashing/array_hash_map.md内嵌的 Python 实现，系统讲解“仅用一个数组就能实现哈希表”的完整方案：桶（bucket）与键值对（Pair）的组织方式、key % capacity哈希函数的工作原理，以及get / put / remove和遍历操作的源码级细节。读完你既能看懂这版ArrayHashMap的每行代码，也能理解它的局限——哈希冲突与扩容（负载因子）——并知道下一步该如何演进。

一、为什么可以先用一个数组实现哈希表

哈希表（hash table，又称散列表）通过建立键key与值value的映射，在 $O(1)$ 时间内完成查询。这是它相对数组、链表的决定性优势，三者的效率对比如下（见 docs/chapter_hashing/hash_map.md）：

最简单的哈希表实现思路是：只用一个数组充当存储容器，把数组中的每个空位称为“桶（bucket）”，每个桶恰好存放一个键值对。查询操作因此退化为两步：

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

index = hash(key) % capacity

随后即可用index直接访问数组，取出value。整个过程没有任何搜索或遍历，这就是 $O(1)$ 查询的来源。

二、ArrayHashMap 完整源码解析

关联文档codes/pythontutor/chapter_hashing/array_hash_map.md中内嵌的完整实现如下（仓库可运行的等价版本见 codes/python/chapter_hashing/array_hash_map.py）：

class Pair: """键值对""" def __init__(self, key: int, val: str): self.key = key self.val = val class ArrayHashMap: """基于数组实现的哈希表""" def __init__(self): """构造方法""" # 初始化数组，包含 20 个桶 self.buckets: list[Pair | None] = [None] * 20 def hash_func(self, key: int) -> int: """哈希函数""" index = key % 20 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 def key_set(self) -> list[int]: """获取所有键""" result = [] for pair in self.buckets: if pair is not None: result.append(pair.key) return result def value_set(self) -> list[str]: """获取所有值""" result = [] for pair in self.buckets: if pair is not None: result.append(pair.val) return result def print(self): """打印哈希表""" for pair in self.buckets: if pair is not None: print(pair.key, "->", pair.val)

逐部分来看：

1. Pair：键值对的封装

key和value被封装成类Pair，以表示一个不可拆分的键值对。之所以需要这个中间类型，是因为数组的每个桶只能存“一个对象”，而键和值必须同时被保留（否则遍历时无法同时拿到Key -> Value）。

2. 构造方法与桶数组

self.buckets = [None] * 20初始化了一个长度为 20 的数组，即capacity = 20，每个元素要么是None（空桶），要么是一个Pair。注意内嵌在 pythontutor 文档中的这一版取 20 个桶；而仓库中可运行的 array_hash_map.py 以及同目录下的 Java 实现、C 实现 均按文档正文的示例取capacity = 100（如 C 版中的#define MAX_SIZE 100）。这个差异直接影响后文的索引计算，分析示例时需注意。

3. 哈希函数：取模就是最简 hash

hash_func采用hash(key) = key的恒等哈希算法，再对容量取模，即index = key % 20。这正是正文公式index = hash(key) % capacity的直接落地。取模保证了输出必然落在[0, capacity)区间内，与数组索引一一对应。

4. get / put / remove：$O(1)$ 的增删查

三个核心操作的结构完全对称，都是“算索引 → 直接访问桶”：

• get(key)：先算index = hash_func(key)，取self.buckets[index]；若桶为空（None）返回None，否则返回pair.val。没有命中任何桶时不会抛错，而是返回空值，由调用方判断。
• put(key, val)：构造Pair后写入self.buckets[index]。从源码结构看，这里不做“键是否已存在”的判断，同一桶的新pair会直接覆盖旧值——所以put兼具“添加和更新”语义，但更新的前提是两个key恰好映射到同一桶。
• remove(key)：同样只按索引定位，把该桶置为None即视为删除。它不会检查桶中存的key是否就是要删的那个，这一点在冲突场景下会引出问题（见第四节）。

5. entry_set / key_set / value_set：三种遍历视图

这三个方法都是线性扫描整个桶数组、跳过None后收集结果，时间复杂度为 $O(n)$（$n$ 为桶数）：

• entry_set()：返回所有Pair对象，对应内置dict的items()；
• key_set()：只收集pair.key，对应keys()；
• value_set()：只收集pair.val，对应values()。

print()方法则是entry_set逻辑的内联版本，逐桶打印key -> value。

三、运行驱动代码：从示例键值对看哈希定位过程

文档内嵌代码的驱动部分（if __name__ == "__main__":）演示了“添加 → 查询 → 删除 → 遍历”的完整流程：

# 初始化哈希表 hmap = ArrayHashMap() # 添加操作 hmap.put(12836, "小哈") hmap.put(15937, "小啰") hmap.put(16750, "小算") hmap.put(13276, "小法") hmap.put(10583, "小鸭") # 查询操作 name = hmap.get(15937) # 删除操作 hmap.remove(10583) # 遍历哈希表 print("\n遍历键值对 Key->Value") for pair in hmap.entry_set(): print(pair.key, "->", pair.val)

以capacity = 100的仓库版本为例，可以手算每个学号落到的桶：

五个键各占一个桶，因此：

• hmap.get(15937)直接读取buckets[37]，返回"小啰"；
• hmap.remove(10583)将buckets[83]置为None；
• entry_set()遍历后只剩 4 个Pair，按桶下标顺序输出。

这套示例数据也解释了为什么文档选择“学号 → 姓名”作为主题：整型学号天然适合取模定位，且数值间差异能直观展示哈希函数的分散效果。

四、简单实现的边界：哈希冲突与扩容

从本质上看，哈希函数是把所有key构成的输入空间映射到数组索引构成的输出空间，而输入空间远大于输出空间，因此一定存在“多个输入对应相同输出”的情况。以取模哈希为例，当输入的key后两位相同时（capacity = 100时），哈希函数的输出结果也相同，例如：

12836 % 100 = 36 20336 % 100 = 36

两个不同的学号指向了同一个桶，这就是哈希冲突（hash collision）。上面的简单实现对冲突没有任何处理手段：put只会让后来的键值对覆盖先前的键值对，remove也可能误删同桶中的其他键值对——这是教学实现刻意保留的“裸奔”形态，用于先把哈希函数本身的机制讲透。

缓解冲突最直接的办法是扩容：哈希表容量 $n$ 越大，多个key落入同一桶的概率越低。类似于数组扩容，哈希表扩容需要把所有键值对从原表迁移到新表，并且由于capacity改变，必须用哈希函数重新计算所有键值对的存储位置（rehash），开销显著。为此，编程语言通常预留足够大的初始容量，防止频繁扩容。

衡量冲突严重程度、并常用作扩容触发条件的指标是负载因子（load factor）：

$$\text{负载因子} = \frac{\text{元素数量}}{\text{桶数量}}$$

例如在 Java 中，当负载因子超过 0.75 时，HashMap会将容量扩容至原先的 2 倍。

而真正解决“同桶多值”的工程手段有两种，均可在同一章节继续阅读：

• 链地址法（chaining）：每个桶挂一条链表，冲突的键值对依次入链，见 codes/python/chapter_hashing/hash_map_chaining.py；
• 开放地址法（open addressing）：冲突时按探测序列寻找下一个空桶，见 codes/python/chapter_hashing/hash_map_open_addressing.py，其中还需处理带删除标记（DELETED）的墓碑问题，见 开放地址法图解 与 docs/chapter_hashing/hash_collision.md。

五、多语言实现对照

同一份ArrayHashMap设计在仓库中还有跨语言版本，核心结构完全一致，便于对照理解：

• Python 版：buckets是list[Pair | None]，删除时置None；
• Java 版：List<Pair>充当桶数组，空桶为null，删除时buckets.set(index, null)，且遍历方法命名为pairSet / keySet / valueSet；
• C 版：用Pair *buckets[MAX_SIZE]指针数组实现，Pair是key(int) + val(char*)结构体，并提供了显式的newArrayHashMap / delArrayHashMap构造与析构函数管理内存。

三种实现共同印证了本文的核心结论：哈希表的最小内核就是一个桶数组 + 一个取模哈希函数，其余语言特性（引用类型、指针管理）都只是表层差异。

六、小结

围绕codes/pythontutor/chapter_hashing/array_hash_map.md这份实现，可以沉淀出以下要点：

1. 结构：ArrayHashMap= 桶数组buckets+ 键值对封装Pair，空桶以None表示；
2. 定位：index = hash(key) % capacity，本文恒等哈希加取模即最简哈希函数；
3. 操作：get / put / remove均为 $O(1)$ 的直接寻址；entry_set / key_set / value_set为 $O(n)$ 的线性收集；
4. 局限：该实现对哈希冲突不做处理，后写覆盖先写；
5. 演进方向：通过扩容降低冲突概率，以负载因子（如 Java 的 0.75 阈值）触发扩容，再以链地址法或开放地址法容纳同桶多值。

如需继续深入哈希表的完整设计（冲突解决、扩容 rehash、内置哈希表使用姿势），建议直接阅读 docs/chapter_hashing/hash_map.md 与 docs/chapter_hashing/hash_collision.md 两篇文档及对应的多语言代码目录 codes/python/chapter_hashing/。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo