《掰开揉碎讲编程-长篇》一文读懂 哈希表

1. 博主粉丝群介绍： ① 群内初中生、高中生、本科生、研究生、博士生遍布，可互相学习，交流困惑。
2. ② 热榜top10的常客也在群里，也有数不清的万粉大佬，可以交流写作技巧，上榜经验，涨粉秘籍。
3. ③ 群内也有职场精英，大厂大佬，可交流技术、面试、找工作的经验。
4. 进群免费赠送写作秘籍一份，助你由写作小白晋升为创作大佬。
5. 进群赠送CSDN评论防封脚本，送真活跃粉丝，助你提升文章热度。
6. 群公告里还有全网大赛and约稿汇总/博客提效工具集/CSDN自动化运营脚本 有兴趣的加文末联系方式，备注自己的CSDN昵称，拉你进群，互相学习共同进步。

复制代码

• 刷算法题的时候，别人的题解总是："加个哈希表，O(n)秒了"。而你还在纠结：哈希表是什么？为什么能加速？怎么用？ 这篇文章就是来解答这些问题的。
  

前置知识要求

知识点重要程度说明数组基础必需 ⭐需要了解数组的基本操作和时间复杂度时间复杂度必需 ⭐需要理解 O(1)、O(n) 等概念基础编程语法推荐会使用一门编程语言即可链表加分项了解更佳，不了解也不影响

• 必需：没有这个基础很难理解本文
  
• 推荐：有这个基础学习更轻松
  
• 加分项：了解更好，不了解也不影响
  

为什么叫 Hash？

Hash 的英文原意就是"切碎、混杂"。想象你在炖一锅大杂烩（hash）：胡萝卜、土豆、红肉、白肉……很多复杂叫不出名的食材混合在一起煮，最后成了一锅汤。
这个过程就是哈希。
原本各有特点的食材（数据），经过烹煮（哈希函数），变成了一锅融合的汤（Hash 值）。
哈希的本质：把不能当索引的东西（字符串、对象）变成能当索引的数字，但对外呈现为键值对，更符合人类思维。
和数组有什么关系？

数组是怎么组织数据的？

通过序号（索引），像门牌号一样：

1. 数组：[苹果, 芒果, 葡萄, 草莓, 西瓜]
2. 索引：  0    1    2    3    4

复制代码

问题来了：我想找到"葡萄"要怎么找？
方法 1：暴力查找（遍历挨个比对）

1. 第1步：看索引0 → "苹果"  不是
2. 第2步：看索引1 → "芒果"  不是  
3. 第3步：看索引2 → "葡萄"  找到了！

复制代码

时间复杂度：O(n) —— 最坏情况要找 n 次
但如果我知道索引呢？

1. 直接访问：数组[2] → "葡萄"  一次搞定！

复制代码

时间复杂度：O(1) —— 直达，不用挨个找
矛盾点

• 问题：我现在有"葡萄"这个名字，但不知道它在索引几
  
• 理想状态：能不能通过"葡萄"这个名字，直接算出它在索引 2？
  

哈希表就是来解决这个问题的！
哈希表的做法

用哈希函数把"葡萄"变成索引

1. 第一步：设计一个哈希函数（就像炖汤的配方）
2. hash("葡萄") = 2  ← 把"葡萄"这个字符串"煮"成数字2
3. ​
4. 第二步：存储时
5. "葡萄" → hash("葡萄") = 2 → 存到数组[2]的位置
6. ​
7. 第三步：查找时
8. 想找"葡萄"？
9. → hash("葡萄") = 2  
10. → 直接去数组[2]拿  
11. → 时间复杂度：O(1)！

复制代码

对比总结

查找方式普通数组遍历哈希表操作从头到尾挨个比对通过哈希函数直接定位过程苹果 → 芒果 → 葡萄hash("葡萄")=2 → 数组[2]时间复杂度O(n)O(1)特性普通数组哈希表（基于数组）底层结构数组数组索引是什么必须是连续的数字 0,1,2,3...任意类型（通过哈希函数转成数字）存储方式arr[0] = valuehash("key")→ 索引 →arr[索引] = value查找速度O(1)（知道索引）不知道 O（n）O(1) 平均 / O(n) 最坏哈希表在代码中长什么样？（Java）

在 Java 中，哈希表的表现形式为键值对（Key-Value）

1. // Java 中的 HashMap
2. HashMap<String, String> fruitMap = new HashMap<>();
3. ​
4. // 存储：键 → 值
5. fruitMap.put("apple", "苹果");
6. fruitMap.put("grape", "葡萄");
7. fruitMap.put("mango", "芒果");
8. ​
9. // 查找：通过键直接拿到值
10. String result = fruitMap.get("grape");  // 返回 "葡萄"

复制代码

键值对是什么？

就像字典一样：

1. 英文（Key 键）    中文（Value 值）
2. ─────────────────────────────
3. apple       →      苹果
4. grape       →      葡萄  
5. mango       →      芒果

复制代码

• Key（键）：用来查找的"钥匙"，比如 "apple"
  
• Value（值）：存储的实际数据，比如 "苹果"
  

底层怎么存的？

还是用数组！

1. 用户看到的（键值对形式）：
2. "apple" → "苹果"
3. "grape" → "葡萄"
4. ​
5. 底层实际存储（数组）：
6. [  null,  null,  "葡萄",  "苹果",  null  ]
7.    0      1       2        3       4
8.                   ↑        ↑
9.           hash("grape")  hash("apple")
10.               = 2           = 3

复制代码

过程：

• 你存入 "apple" → "苹果"
  
• 哈希函数计算：hash("apple") = 3
  
• 把 "苹果" 存到数组的 [3] 位置
  
• 查找时：hash("apple") = 3，直接去 [3] 拿
  

• 因为封装，我们可以不关注具体实现，实现也不是本文的重点，我们已经明白了哈希，接下来将讲在算法中如何使用哈希
  

哈希表中常用的方法有哪几个？

方法描述示例代码put(K key, V value)向 HashMap 中添加一个键值对，如果键已存在，则覆盖原有值。map.put("key1", "value1");get(Object key)根据给定的键返回对应的值，如果键不存在，则返回 null。String value = map.get("key1");containsKey(Object key)检查 HashMap 中是否包含指定的键。boolean contains = map.containsKey("key1");containsValue(Object value)检查 HashMap 中是否包含指定的值。boolean contains = map.containsValue("value1");remove(Object key)删除指定键的键值对，返回该键的值，如果键不存在则返回 null。map.remove("key1");clear()清空 HashMap 中的所有键值对。map.clear();size()返回 HashMap 中键值对的数量。int size = map.size();isEmpty()判断 HashMap 是否为空。boolean isEmpty = map.isEmpty();keySet()返回 HashMap 中所有键的集合。Set keys = map.keySet();values()返回 HashMap 中所有值的集合。Collection values = map.values();entrySet()返回 HashMap 中所有键值对的集合。Set> entrySet = map.entrySet();getOrDefault根据键 key 获取对应的值，如果键不存在，则将值变为 defaultValue。map.getOrDefault("key1", "defaultValue");实战：刷 LeetCode 时怎么用哈希表得到更好的时间复杂度？

简单题：难度 1

1512. 好数对的数目
[code]给你一个整数数组 nums 。如果一组数字 (i,j) 满足 nums == nums[j] 且 i < j ，就可以认为这是一组 好数对 。返回好数对的数目。示例 1：输入：nums = [1,2,3,1,1,3]输出：4解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始示例 2：输入：nums = [1,1,1,1]输出：6解释：数组中的每组数字都是好数对示例 3：输入：nums = [1,2,3]输出：0提示：1