企业官网建设流程全解析

• 教程
• 文档

哈希表是算法面试与日常工程中使用频率最高的数据结构之一，其核心价值在于将「查找」操作从线性扫描的 O(n) 降为平均 O(1)。本文以 LogicStack-LeetCode 仓库的 Index/哈希表.md 为骨架，结合仓库内 LeetCode 题解（如 1. 两数之和、146. LRU 缓存机制、560. 和为 K 的子数组 等）提炼出哈希表解题的完整体系。读完本文，你将掌握哈希表的适用场景判断、经典解题模板（计数、查重、索引、映射）、冲突处理与手写实现，以及从简单到困难的完整刷题路径。

为什么哈希表是「刷穿 LeetCode」的基石

从 Index/哈希表.md 中可以看到，这份索引收录了100 余道哈希表相关题目，难度覆盖简单、中等、困难三个梯度，推荐指数从 🤩🤩 到 🤩🤩🤩🤩🤩 不等。哈希表在 LeetCode 中出现频率极高的原因在于：

1. 空间换时间：用 O(n) 的空间开销换取 O(1) 的查询、插入、删除；
2. 几乎可搭配一切算法：与双指针、前缀和、滑动窗口、DFS/BFS、位运算等结合，形成「哈希表 + X」的组合套路；
3. 工程价值直接可迁移：语言内置的HashMap/HashSet（Java）、unordered_map/unordered_set（C++）、dict/set（Python）、Map/Set（TypeScript）正是面试考察的高频考点，理解其底层原理（哈希函数、冲突解决）对写对、写优代码至关重要。

哈希表的五大核心用法

通读索引中推荐指数最高的题目，可以将哈希表的使用方式归纳为以下五类模式。这五类模式覆盖了索引中绝大多数题目，是刷题时的「条件反射」。

模式一：边遍历边建表，查补集（两数之和）

这是哈希表最经典的入门用法。以 1. 两数之和 为例：目标值target已知，遍历数组时，对每个数a，只需在哈希表中查target - a是否存在即可。

朴素解法是两重循环枚举下标 i、j，复杂度 O(n²)；哈希表解法则是在遍历过程中「边查边存」，将第二个数的查找变成 O(1)：

class Solution { public int[] twoSum(int[] nums, int t) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int a = nums[i], b = t - a; if (map.containsKey(b)) return new int[]{map.get(b), i}; map.put(a, i); } return new int[]{}; } }

题解中特别强调了一个细节：如果先一次性把所有数放入哈希表，再遍历敲定第一个数，则在遍历过程中还需要将「自己」从哈希表中删除（map.get(a) == i时map.remove(a)），多了一次插入与一次删除。而「边遍历边存入」的做法天然规避了自我匹配问题，属于常数级优化。题解还给出了一个小技巧：将入参target简写为t，在不影响正确性的前提下提高编码速度，这在周赛中是常用手法。

索引中同模式的题目还包括 653. 两数之和 IV - 输入 BST（哈希表 + 树的遍历）、888. 公平的糖果棒交换、2006. 差的绝对值为 K 的数对数目 等。

模式二：计数统计 + 频率映射

许多题目要求统计元素出现次数，此时哈希表作为「计数器」使用，key 为元素，value 为频次。典型代表：

• 451. 根据字符出现频率排序：先用哈希表统计字符频次，再按频次排序；
• 697. 数组的度：用哈希表记录每个元素首次出现位置、末次出现位置与频次；
• 652. 寻找重复的子树：对子树进行序列化编码后放入哈希表计数；
• 884. 两句话中的不常见单词：合并两句话后统计词频，出现次数恰为 1 的即为答案；
• 1636. 按照频率将数组升序排序、1748. 唯一元素的和、1838. 最高频元素的频数 等。

子数组计数进阶：前缀和 + 哈希表。以 560. 和为 K 的子数组 为例，直接枚举所有子数组是 O(n²)。正确做法是预处理前缀和数组sum（下标从 1 开始），统计以nums[i]结尾的和为 k 的子数组数量，等价于在[0, i]范围内查找sum中值为sum[i+1] - k的个数——用一个哈希表同步记录前缀和出现次数即可：

class Solution { public int subarraySum(int[] nums, int k) { int n = nums.length, ans = 0; int[] sum = new int[n + 10]; for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1]; Map<Integer, Integer> map = new HashMap<>(); map.put(0, 1); // 前缀和为 0 的情况出现 1 次（空子数组） for (int i = 1; i <= n; i++) { int t = sum[i], d = t - k; ans += map.getOrDefault(d, 0); map.put(t, map.getOrDefault(t, 0) + 1); } return ans; } }

该题在仓库中同时给出了 C++、Python、TypeScript 三种语言版本，可见其作为「哈希表 + 前缀和」模板题的地位。同模式题目还有 930. 和相同的二元子数组、1074. 元素和为目标值的子矩阵数量、剑指 Offer II 010. 和为 k 的子数组、剑指 Offer II 011. 0 和 1 个数相同的子数组 等。

模式三：索引定位 + 查重去重

当需要「记住元素出现过、以及它出现的位置」时，哈希表的 key 存元素，value 存下标或布尔标记。代表题目：

• 3. 无重复字符的最长子串：双指针 + 哈希表，滑动窗口内维护字符出现情况（推荐指数 🤩🤩🤩🤩🤩）；
• 219. 存在重复元素 II：滑动窗口 + 哈希表查重，窗口大小限定为 k；
• 268. 丢失的数字、645. 错误的集合：用哈希表标记已出现元素后定位缺失/重复项；
• 187. 重复的DNA序列：哈希表 + 字符串哈希/滑动窗口；
• 1743. 从相邻元素对还原数组：哈希表记录每个元素的相邻元素列表；
• 2661. 找出叠涂元素、2013. 检测正方形 等。

模式四：映射转换（复杂对象 → 规约键）

当原始数据无法直接作为哈希键时，先做一次「编码/规约」再入表。这一模式往往与「模拟」或「字符串处理」组合出现：

• 面试题 10.02. 变位词组 与 49. 字母异位词分组：对单词排序后作为 key，或统计 26 个字母出现次数拼接为 key；
• 535. TinyURL 的加密与解密：长短地址互相映射，两个哈希表或编码算法；
• 13. 罗马数字转整数：罗马字符 → 数值的映射表 + 模拟；
• 1410. HTML 实体解析器：实体字符串 → 替换字符的映射表；
• 1282. 用户分组、1331. 数组序号转换、1583. 统计不开心的朋友、1418. 点菜展示表（哈希表 + 红黑树/有序结构）等。

模式五：手写哈希结构（数据结构设计题）

索引中有一批「设计题」直接考察哈希表底层原理，是面试中区分度极高的题型。仓库中对应的题解实现了从「简单数组」到「链表法」「开放寻址法」「位图分桶」的完整演进。

705. 设计哈希集合（LeetCode/701-710/705. 设计哈希集合（简单）.md）给出了三种实现：

1. 简单 boolean 数组：利用0 <= key <= 10^6的数据范围限制，直接以下标映射，O(1) 查改；
2. 链表法：桶数组 + 单向链表解决冲突，getIndex中先用hash ^= (hash >>> 16)让高位随机性也参与低 16 位计算，再hash % nodes.length取桶下标；
3. 分桶位图（bitmap）：用int数组的每一位记录一个 key，key / 32定位桶、key % 32定位位，空间上极为紧凑（约 40000 个 int 即可覆盖 10^6 数据范围）。

706. 设计哈希映射（LeetCode/701-710/706. 设计哈希映射（简单）.md）在集合基础上额外存储 value，同样给出数组、链表、开放寻址三种实现。其中开放寻址法在冲突时以OFFSET = 1为步长线性探测，删除时用isDeleted标记实现「懒删除」，避免破坏探测链。

146. LRU 缓存机制（LeetCode/141-150/146.%20LRU%20缓存机制（中等）.md）是「哈希表 + 双向链表」的经典组合：哈希表保证键值对的 O(1) 定位，双向链表维护「最近使用」顺序。插入、查询都会触发refresh（把节点移到链表头），容量满时从链表尾部淘汰。题解用两个哨兵节点head/tail消除了左右节点判空操作，代码同时给出 Java 与 C++ 版本。索引中同属「设计类」的还有：

• 380. O(1) 时间插入、删除和获取随机元素%20时间插入、删除和获取随机元素（中等）.md)：哈希表（val → 数组下标）+ 数组，删除时与末尾元素「交换删除」保证严格 O(1)；
• 460. LFU 缓存：哈希表 + 桶排序思想，按频率组织；
• 432. 全 O(1) 的数据结构：困难难度，哈希表 + 双向链表维护频次；
• 895. 最大频率栈：按频率分桶存储；
• 1603. 设计停车系统、2336. 无限集中的最小数字 等。

哈希冲突的三种处理方式（源码级印证）

从 706. 设计哈希映射 的题解中，可以完整看到三种主流冲突处理策略的实现对比：

值得注意的工程细节是getIndex中hash ^= (hash >>> 16)这一步：当桶数组长度较小时（如 10009），取模只用到低 14 位，高位的随机性会丢失，右移异或让高位信息也注入低 16 位，显著降低冲突概率。这一技巧与 JavaHashMap的扰动函数思路一致，是手写哈希时的通用优化。

刷题路径建议（按推荐指数与难度分层）

结合索引中的推荐指数，给出循序渐进的学习顺序：

1. 入门层（简单）：1. 两数之和、705. 设计哈希集合、706. 设计哈希映射、13. 罗马数字转整数、884. 两句话中的不常见单词、1436. 旅行终点站、1700. 无法吃午餐的学生数量——先建立「空间换时间」「边遍历边查」的基本直觉；
2. 进阶层（中等 · 综合）：3. 无重复字符的最长子串（双指针）、560. 和为 K 的子数组（前缀和）、146. LRU 缓存机制（数据结构设计）、380. O(1) 时间插入、删除和获取随机元素%20时间插入、删除和获取随机元素（中等）.md)、447. 回旋镖的数量（距离映射计数）、1218. 最长定差子序列（DP + 哈希）——体会哈希表与主流算法的组合拳；
3. 困难层（压轴）：30. 串联所有单词的子串、460. LFU 缓存、432. 全 O(1) 的数据结构、726. 原子的数量、895. 最大频率栈、1224. 最大相等频率、710. 黑名单中的随机数——训练哈希表在复杂模拟与高级数据结构中的组织能力。

总结

哈希表专题的刷题心法可以浓缩为一句：凡是需要「快速判断存在性」「记录出现位置」「统计频次」「建立映射」的场景，优先考虑哈希表，并将它与其他算法（前缀和、滑动窗口、双指针、DP、DFS）自然衔接。本仓库的 Index/哈希表.md 提供了完整的 100+ 题清单与难度/推荐指数标注，配合 LeetCode 目录下按题号组织的逐题题解（含多种语言代码与复杂度分析），构成了从入门到困难、从 API 使用到底层手写实现的全链路学习材料。建议按上文的分层路径逐题刷穿，并在每题完成后对照题解中的「最后」部分，复盘是否掌握了更优的哈希表组织方式。

• 教程
• 文档