哈希表

哈希表的核心价值不是“会背 API”，而是能把很多原本需要 O(n log n) 排序或 O(n^2) 枚举的问题，直接降到接近 O(n)。

先记住它解决什么问题

• 判断某个值是否出现过
• 统计某个值出现了多少次
• 快速找到某个 key 对应的 value
• 把对象映射到位置、前驱、最近一次出现位置等辅助信息

最常见的三种形态

1. HashSet

   • 只关心是否存在
   • 常用于去重、visited、判环

2. HashMap<K, V>

   • 关心 key 到 value 的映射
   • 常用于 Two Sum、索引映射、计数、状态缓存

3. frequency map

   • 本质是 HashMap<K, Integer>
   • 常用于 Top K、字符统计、分组计数

典型题型

• Two Sum
• 字符出现次数统计
• Group Anagrams
• LRU / RandomizedSet 这类数据结构设计题
• 图搜索里的 visited

什么时候该第一时间想到哈希表

• 题目问“是否重复”“是否访问过”“是否出现过”
• 需要在遍历过程中随时查一个值
• 排序并不是题目真正要求，只是你为了查找方便才想排序

常见坑

• 明明只需要存在性判断，却用了排序
• 需要次数，却只开了 HashSet
• 需要索引，却只记了值
• 图搜索时标记 visited 太晚，导致重复入队

延伸

• 如果值域和下标能建立映射关系，可以继续看主树里的 Hash
• 如果题目同时要求顺序和快速查找，通常要和链表或堆一起配合使用，参考 21. 哈希表和堆