哈希表

哈希表（Hash Table，也叫散列表）以「键值对」形式存取数据：通过哈希函数把 key 直接换算成数组下标，使查找、插入、删除的平均时间复杂度都达到 O(1)。字典、缓存、去重与数据库索引都以它为基石，是数据结构面试的高频考点。

核心原理：数组 + 哈希函数

哈希表 = 一段数组 + 一个哈希函数。插入时先对 key 求哈希值，再对数组长度取模得到下标并存入；查找时用同样的计算直接定位，无需逐个比较。

key → 哈希函数 → hash 值 → 对长度取模 → 数组下标 → 槽位

book = {}                    # 空哈希表（Python dict）
book["apple"] = 3            # 插入：内部算 hash("apple") 定位槽位
print(book.get("apple"))     # 输出：3，O(1) 查回
print(len(book))             # 输出：1

理想的哈希函数应计算快、分布均匀，让不同 key 尽量散落到不同槽位。

哈希冲突与解决方案

不同 key 算出同一个下标就叫「哈希冲突」。数组长度有限而 key 无限，冲突无法避免，常见两种解法：

• 链地址法（拉链法）：冲突元素挂在同一槽位的链表上，Java HashMap 采用此法。
• 开放寻址法：冲突后按规则找下一个空位，如线性探测逐个后移。

下标:     0         1         2         3
链地址:   k1 → k8   null      k3 → k9   null

查找时先定位下标，再沿链表比较 key；冲突越少越接近 O(1)。

负载因子与扩容

负载因子 = 已存元素数 ÷ 槽位总数，反映哈希表的拥挤程度。因子过高时冲突剧增、性能退化为 O(n)，此时应扩容：把数组扩大（通常翻倍）并把旧元素重新哈希到新表。Java HashMap 默认负载因子 0.75，容量 16 存到 12 个就扩容；Go map、Python dict 也有各自的装载阈值与渐进式迁移策略。面试常问「为什么扩容后要重新哈希？」——因为数组长度变了，取模结果也随之改变，旧下标不再有效。

常见实现对比

实现	冲突策略	扩容机制	特点
Java HashMap	链地址，链表过长转红黑树	负载因子 0.75 翻倍	线程不安全
Go map	桶 + 溢出桶	装载因子约 6.5 触发	并发写会 panic
Python dict	开放寻址	动态缩容/扩容	保留插入顺序
Redis hash	链地址	渐进式 rehash	扩容不阻塞服务

复杂度与面试要点

• 平均复杂度：查找、插入、删除均为 O(1)；最坏情况（全部冲突成一条链）退化为 O(n)。
• 高频题：两数之和、字母异位词分组、LRU 缓存（哈希表 + 双向链表）。
• 回答模板：先点出「用空间换时间」，再讲哈希函数、冲突解决、负载因子与扩容，最后补一句最坏 O(n) 的边界意识。
• 加分点：哈希表无序，键必须可哈希——Go 中 slice 不能当 map 的 key。

小结：哈希表用数组下标换取 O(1) 存取，核心是哈希函数、冲突解决与扩容三件事；把复杂度与 HashMap/Go map 的工程细节说清，就能稳拿这题。