哈希

哈希类问题的核心是把“线性查找”降维成“常数时间查找”。在面试里，凡是出现去重、计数、映射、前缀状态匹配，都应该优先想一遍哈希表。它通常与数组、字符串、前缀和一起出现，是最常见的“空间换时间”模型。

识别信号

• 需要 判断元素是否存在、去重、计数
• 需要建立”值→下标”或”值→频次”的映射关系
• 出现”前缀状态是否出现过”（前缀和 + 哈希）

反例：如果需要有序遍历或范围查询，用 TreeMap/排序数组更合适。

怎么处理

1. 先问自己：是不是需要快速判断某个状态是否出现过。
2. 再判断 key 存什么，value 存什么，是值、下标、频次还是前缀状态。
3. 如果题目反复查历史信息，优先考虑哈希，而不是每次重扫。
4. 如果是工程问题，再补充冲突处理、负载因子、扩容这些底层点。

哈希表三问（设计题的骨架）

看到哈希类题，三个问题连珠炮问自己，设计就清晰了：

1. Key 存什么？ 最常见是原始值；但字母异位词用"排序后字符串"、分组用"可哈希的唯一标识"（如频率数组编码）、前缀和类题存"前缀和值"
2. Value 存什么？ 下标（两数之和要返回下标）、频次（计数题）、出现位置集合（多位置查询）、或者只存存在性（去重用 HashSet）
3. 什么时机写，什么时机读？ 两数之和是"先查后存"，不能拿自己配自己；前缀和哈希是"查询 + 更新"两步谁先谁后决定是否含当前元素

底层原理一句话版

面试问"哈希表为什么 O(1)"时的最小答案集：

• 平均 O(1)，最坏 O(n)：哈希冲突多了就退化。Java 8 后链表长度达 8 且数组长度 ≥ 64 会转红黑树，最坏优化到 O(log n)
• 冲突解决两大派：链地址法（Java HashMap）、开放地址法（Python dict）
• 负载因子 0.75 + 扩容 2 倍：Java 默认阈值，超过就扩容 + rehash，代价是一次 O(n) 的大拷贝
• 不可变对象作 key：存入后修改 key 的字段会导致哈希错位，再也找不到（String/Integer 天然安全，自定义类必须正确重写 hashCode + equals）

详细原理、与红黑树/跳表的对比、Bloom Filter / Count-Min Sketch 等变体，见 哈希表。

典型实例

专题	关键差异	先看什么
哈希表	覆盖 Key/Value 设计方法论、底层原理、常见陷阱	key/value 设计三问 + HashMap 内部实现
LFU 缓存（工程）	LRU 进阶 — 双哈希 + N 条双向链表手撕	为什么 Redis 4.0+ 上了 allkeys-lfu
O(1) 插删随机（工程）	HashMap + ArrayList 双向映射	抽奖系统 / 连接池随机选择
设计 Twitter（工程）	Feed 流最小可面试版	推/拉/推拉结合三大模型
停车场系统设计（工程）	经典 OOP 设计 + PriorityQueue 找最近空位 + 并发锁	其它“设计 XX 系统”类题的骨架（酒店/共享单车/售货机）

看到什么就先想到这类

• 出现“去重、频次统计、元素配对”。
• 出现“某个状态之前是否出现过”。
• 出现“前缀和 + 某个差值是否存在”。