 查找原理到冲突与扩容机制（Hello 算法）)
Hash Map 哈希表完全指南从 O(1) 查找原理到冲突与扩容机制Hello 算法【免费下载链接】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文章导读哈希表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)Cstd::unordered_map注意 C 中不存在的内置哈希表由标准库提供/* Initialize hash table */ unordered_mapint, 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);JavaHashMapK, V/* Initialize hash table */ MapInteger, 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#DictionaryK, V可通过集合初始化器一次性写入 5 条记录查询用索引器map[15937]删除用map.Remove(10583)/* Initialize hash table */ Dictionaryint, 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 / TypeScriptMapmap.set(12836, XiaoHa)、map.get(15937)、map.delete(10583)DartMapint, Stringmap[12836] XiaoHa、String name map[15937]、map.remove(10583)Ruststd::collections::HashMapmap.insert(12836, XiaoHa.to_string())、map.get(15937)返回OptionString、map.remove(10583)返回OptionStringKotlinHashMapInt,Stringmap[12836] XiaoHa、val name map[15937]、map.remove(10583)Rubyhmap[12836] XiaoHa、name hmap[15937]、hmap.delete(10583)。需要注意的语言差异C 语言标准库不提供内置哈希表。仓库在 hash_map.c 中以注释明示 C does not provide a built-in hash tableC 语言读者请直接参考后续基于数组的简单实现或学习仓库中基于 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) }各语言对应写法速查Javamap.entrySet()遍历键值对Map.EntryInteger,String、map.keySet()、map.values()C#foreach (var kv in map)遍历键值对、map.Keys、map.ValuesC基于范围的for (auto kv : map)或显式迭代器for (auto iter map.begin(); iter ! map.end(); iter)JS / TSmap.entries()、map.keys()、map.values()Dartmap.forEach((key, value) {...})、map.keys.forEach(...)、map.values.forEach(...)Rustfor (key, value) in map、map.keys()、map.values()Kotlinfor ((key, value) in map)、map.keys、map.valuesRubyhmap.entries.each { |key, value| ... }、hmap.keys.each、hmap.values.eachSwiftfor (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对应的桶数组下标indexindex hash(key) % capacity随后即可用index访问哈希表对应桶并取回value。假设数组长度capacity 100、哈希算法为hash(key) key则哈希函数退化为key % 100。下图以学号为键、姓名为值展示了该哈希函数的工作流程。仓库用Pair类封装键与值、再以数组承载Pair实现了完整的最小哈希表。以 Python 为例完整源码见 en/codes/python/chapter_hashing/array_hash_map.pyclass 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用ListPair模拟桶数组、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 种语言中Pythondict、Cunordered_map、JavaHashMap、Gomap、C#Dictionary、JS/TSMap、RustHashMap等 API 语义一致均可增、查、删、遍历怎么实现仅用数组即可实现核心是桶 哈希函数index hash(key) % capacity仓库 array_hash_map.py 等 14 种语言源码提供了可直接运行的对照实现有什么坑与对策输入空间大于输出空间导致冲突必然存在扩容可降低冲突概率但需全量迁移并重算位置负载因子如 Java 的 0.75 阈值用来平衡时空开销并触发扩容。想动手验证可在仓库对应语言目录中直接运行array_hash_map示例观察增删查全过程继续深入冲突解法与哈希算法设计请沿着上述 hash_collision 与 hash_algorithm 两章推进。【免费下载链接】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），仅供参考
Hash Map 哈希表完全指南：从 O(1) 查找原理到冲突与扩容机制（Hello 算法）
Hash Map 哈希表完全指南从 O(1) 查找原理到冲突与扩容机制Hello 算法【免费下载链接】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文章导读哈希表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)Cstd::unordered_map注意 C 中不存在的内置哈希表由标准库提供/* Initialize hash table */ unordered_mapint, 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);JavaHashMapK, V/* Initialize hash table */ MapInteger, 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#DictionaryK, V可通过集合初始化器一次性写入 5 条记录查询用索引器map[15937]删除用map.Remove(10583)/* Initialize hash table */ Dictionaryint, 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 / TypeScriptMapmap.set(12836, XiaoHa)、map.get(15937)、map.delete(10583)DartMapint, Stringmap[12836] XiaoHa、String name map[15937]、map.remove(10583)Ruststd::collections::HashMapmap.insert(12836, XiaoHa.to_string())、map.get(15937)返回OptionString、map.remove(10583)返回OptionStringKotlinHashMapInt,Stringmap[12836] XiaoHa、val name map[15937]、map.remove(10583)Rubyhmap[12836] XiaoHa、name hmap[15937]、hmap.delete(10583)。需要注意的语言差异C 语言标准库不提供内置哈希表。仓库在 hash_map.c 中以注释明示 C does not provide a built-in hash tableC 语言读者请直接参考后续基于数组的简单实现或学习仓库中基于 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) }各语言对应写法速查Javamap.entrySet()遍历键值对Map.EntryInteger,String、map.keySet()、map.values()C#foreach (var kv in map)遍历键值对、map.Keys、map.ValuesC基于范围的for (auto kv : map)或显式迭代器for (auto iter map.begin(); iter ! map.end(); iter)JS / TSmap.entries()、map.keys()、map.values()Dartmap.forEach((key, value) {...})、map.keys.forEach(...)、map.values.forEach(...)Rustfor (key, value) in map、map.keys()、map.values()Kotlinfor ((key, value) in map)、map.keys、map.valuesRubyhmap.entries.each { |key, value| ... }、hmap.keys.each、hmap.values.eachSwiftfor (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对应的桶数组下标indexindex hash(key) % capacity随后即可用index访问哈希表对应桶并取回value。假设数组长度capacity 100、哈希算法为hash(key) key则哈希函数退化为key % 100。下图以学号为键、姓名为值展示了该哈希函数的工作流程。仓库用Pair类封装键与值、再以数组承载Pair实现了完整的最小哈希表。以 Python 为例完整源码见 en/codes/python/chapter_hashing/array_hash_map.pyclass 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用ListPair模拟桶数组、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 种语言中Pythondict、Cunordered_map、JavaHashMap、Gomap、C#Dictionary、JS/TSMap、RustHashMap等 API 语义一致均可增、查、删、遍历怎么实现仅用数组即可实现核心是桶 哈希函数index hash(key) % capacity仓库 array_hash_map.py 等 14 种语言源码提供了可直接运行的对照实现有什么坑与对策输入空间大于输出空间导致冲突必然存在扩容可降低冲突概率但需全量迁移并重算位置负载因子如 Java 的 0.75 阈值用来平衡时空开销并触发扩容。想动手验证可在仓库对应语言目录中直接运行array_hash_map示例观察增删查全过程继续深入冲突解法与哈希算法设计请沿着上述 hash_collision 与 hash_algorithm 两章推进。【免费下载链接】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），仅供参考
