哈希表
哈希表（Hash Table，也叫散列表）是一种通过哈希函数把键（key）映射到桶数组下标、从而实现平均 O(1) 查找/插入/删除的数据结构。它本质上是一个键值对（key-value）映射的容器：用一个 hash(key) % capacity 把任意 key 算成一个数组下标，把 value 存进对应的「桶（bucket）」里。几乎所有现代语言都把它作为一等内建类型（Python 的 dict、Java 的 HashMap/Hashtable、JavaScript 的 Object/Map、C++ 的 unordered_map、Go 的 map），地位相当于数据结构里的「字典」——它也是面试里把暴力 O(n²) 优化到 O(n) 最常用的工具（用空间换时间）。
哈希表的全部考点都源于一个核心矛盾：用哈希函数压缩 key 空间 ⇒ 必然产生冲突（collision）。由鸽巢原理，把多于桶数的 key 散列到有限的桶里，必有至少两个 key 落到同一桶——这就是「冲突必然性」。由此衍生出三大主题：①冲突解决策略（链地址法 separate chaining、开放寻址法 open addressing 的线性/二次/双重哈希探测）；②负载因子（load factor）与扩容（rehash）（负载因子 = 元素数 / 桶数，超阈值就翻倍桶数组并重新哈希，保证平均 O(1)）；③哈希函数设计与工程应用（好哈希要均匀分布 + 雪崩效应，应用涵盖去重、计数、缓存、数据库索引、LRU、一致性哈希、两数之和）。其中两数之和是哈希表最经典的入门题，把 O(n²) 暴力双循环降到 O(n)。
评价
优点
- 平均 O(1) 的查找/插入/删除：哈希函数把 key 直接映射到桶下标，平均情况下不依赖元素数——这是哈希表区别于数组/链表的核⼼优势，也是「用空间换时间」的典范
- 键值映射直观：天然适合「由 key 快速找 value」的场景（字典、计数、去重、缓存），比线性扫描或二分查找都快
- 动态扩容：负载因子超阈值自动 rehash（翻倍桶 + 重新散列），用户无感地保持 O(1) 均摊性能
- 应用面极广：去重（Set）、计数（key→次数）、两数之和、LRU 缓存、数据库索引、一致性哈希（分布式）都以它为核心
缺点
- 最坏 O(n)：当所有 key 都冲突到同一桶时，退化为链表/线性扫描，查找/插入变 O(n)（恶意构造的 key 攻击）
- 无序：哈希表不维护 key 的顺序，无法按 key 大小遍历或范围查询（要有序用红黑树/跳表）；JS
Object的字符串键虽有序但是实现细节，Map才保证插入序 - 空间换时间：为保持低负载因子，桶数组常有大量空槽，内存利用率低于数组
- 不支持范围/最值查询：只能精确等值查询
key == x，不能做key in [a,b]或取最大 key（有序表才能）
本叶地图
- 入门 —— 键值映射模型、哈希函数与桶数组、平均 O(1) 与最坏 O(n)、负载因子与 rehash、冲突必然性（鸽巢）、与数组/链表怎么选
- 冲突解决：链地址法与开放寻址法 —— 链地址法（链表/红黑树）、开放寻址法（线性/二次/双重哈希探测）、聚集问题、各语言实现与 rehash 时机
- 哈希函数设计与工程应用 —— 好哈希标准、除留余数/乘法/字符串哈希、一致性哈希、雪崩效应、去重/计数/缓存/两数之和应用
- 参考 —— 哈希表 API 速查、复杂度表、冲突解决对比、负载因子与 rehash、易错点
交互演示
- 哈希表可视化演示 —— 哈希函数映射、冲突与扩容过程