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

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数组链表哈希表查找元素$O(n)$$O(n)$$O(1)$添加元素$O(1)$$O(1)$$O(1)$删除元素$O(n)$$O(n)$$O(1)$最简单的哈希表实现思路是只用一个数组充当存储容器把数组中的每个空位称为“桶bucket”每个桶恰好存放一个键值对。查询操作因此退化为两步通过某种哈希算法hash()计算得到哈希值将哈希值对桶数量数组长度capacity取模得到该key对应桶数组索引indexindex hash(key) % capacity随后即可用index直接访问数组取出value。整个过程没有任何搜索或遍历这就是 $O(1)$ 查询的来源。二、ArrayHashMap 完整源码解析关联文档codes/pythontutor/chapter_hashing/array_hash_map.md中内嵌的完整实现如下仓库可运行的等价版本见 codes/python/chapter_hashing/array_hash_map.pyclass 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. 哈希函数取模就是最简 hashhash_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的仓库版本为例可以手算每个学号落到的桶键 keykey % 100落桶索引值128363636小哈159373737小啰167505050小算132767676小法105838383小鸭五个键各占一个桶因此hmap.get(15937)直接读取buckets[37]返回小啰hmap.remove(10583)将buckets[83]置为Noneentry_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]删除时置NoneJava 版ListPair充当桶数组空桶为null删除时buckets.set(index, null)且遍历方法命名为pairSet / keySet / valueSetC 版用Pair *buckets[MAX_SIZE]指针数组实现Pair是key(int) val(char*)结构体并提供了显式的newArrayHashMap / delArrayHashMap构造与析构函数管理内存。三种实现共同印证了本文的核心结论哈希表的最小内核就是一个桶数组 一个取模哈希函数其余语言特性引用类型、指针管理都只是表层差异。六、小结围绕codes/pythontutor/chapter_hashing/array_hash_map.md这份实现可以沉淀出以下要点结构ArrayHashMap 桶数组buckets 键值对封装Pair空桶以None表示定位index hash(key) % capacity本文恒等哈希加取模即最简哈希函数操作get / put / remove均为 $O(1)$ 的直接寻址entry_set / key_set / value_set为 $O(n)$ 的线性收集局限该实现对哈希冲突不做处理后写覆盖先写演进方向通过扩容降低冲突概率以负载因子如 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考