【LeetCode刷题日记】哈希表：从0基础到实战全解析

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言我们已经完成了对链表章节算法的学习关于这些方法思路的总结我准备找一个专门的时间总结出来以思维导图为发散将知识点串联起来接下来我们继续学习哈希表及其相关的算法题目覆盖基础知识到实战演练。哈希表英文名字为Hash table国内也有一些算法书籍翻译为散列表大家看到这两个名称知道都是指hash table就可以了。我学习的是java这里分享的就是在java中的哈希表跟c语言或者其他的语言差别挺大的java的哈希表是已经封装好了的不需要自己去实现直接拿来用就可以。Java 哈希表Hash Table全基础讲解要刷力扣哈希表题型Java 里哈希表核心就是 2 个类HashMapHashSet我把所有刷题必需的基础知识、用法、区别、技巧一次性讲全。哈希表到底是什么哈希表 数组 哈希函数本质定义类比一下哈希表 快递柜系统数组 快递柜格子哈希函数 按手机号分配格子计算出哈希值Java HashMap 带挂袋和大箱子的快递柜链表 格子放不下挂个袋子串起来红黑树 袋子太长换成有序大箱子​哈希函数又是什么把任意对象算出一个 int 类型的哈希值用来定位数组下标的公式。hashCode()方法public native int hashCode();给每个对象返回一个int数字同一个对象多次调用结果应该一样想让两个对象视为同一个 key必须 equals 为 true 且 hashCode 相同HashMap 自己的哈希函数真正用的HashMap 不会直接用key.hashCode()它会再做一次扰动让分布更均匀减少冲突。JDK 源码里的哈希函数static final int hash(Object key) { int h; // key 为 null 时哈希值固定为 0 return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }h 16把哈希值右移 16 位^异或运算目的把高 16 位和低 16 位混合让哈希值更散列减少冲突。最后一步算出数组下标有了哈希值还要转成数组下标index hash (table.length - 1);等价于取模但位运算更快。补充这里是怎么减少冲突的通过一个例子理解假设我们有两个字符串AaBB我们直接算它们的hashCode和 原始下标字符串hashCode 原始值直接 15无扰动扰动后 hash 值扰动后 15Aa208002080 ^ (2080 16) 20800BB208002080 ^ (2080 16) 20800灾难发生了如果没有扰动Aa和BB这两个完全不同的字符串会被映射到同一个数组下标下标 0它们会发生严重的哈希冲突都挤在一个链表后面。但扰动之后扰动是把高位和低位异或改变了低位信息让它们落在不同位置完美避开冲突。总结无扰动计算就是直接用hashCode (len-1)。核心目的扰动不是为了改这次的结果而是为了保证大量不同的字符串低位信息也不同从而最大限度避免哈希冲突。所以Java 必须加那个hash()扰动函数。完整流程背下来key ↓ key.hashCode() // 原始哈希 ↓ hash() 扰动函数 // 优化哈希 ↓ (数组长度-1) // 转成数组下标这一套就是 Java 里哈希表真正使用的哈希函数。用哈希函数把「键 key」转换成数组下标时间复杂度插入 / 查找 / 删除 平均 O (1)力扣哈希题核心优势解决问题快速判重、快速查找、统计次数​Java 哈希表两大核心类类用途底层重复规则HashMapK,V存键值对统计次数、映射关系数组 链表 红黑树key 不可重复重复会覆盖HashSetE只存值去重、判断存在基于 HashMap元素不可重复HashMap 最全用法HashMap是力扣哈希题使用频率最高的工具专门处理统计字符 / 数字出现次数两数之和这类映射查找记录索引位置1. 导包import java.util.HashMap;2. 创建对象// 常见写法key 和 value 可任意类型 HashMapInteger, Integer map new HashMap(); HashMapString, Integer map new HashMap();3. 核心方法背会这 10 个足够刷所有哈希题// 1. 添加/修改元素key 不存在添加存在覆盖 map.put(key, value); // 2. 获取元素根据 key 拿 value map.get(key); // 3. 判断是否包含某个 key map.containsKey(key); // 4. 判断是否包含某个 value很少用 map.containsValue(value); // 5. 删除元素 map.remove(key); // 6. 获取键值对数量 map.size(); // 7. 清空 map.clear(); // 8. 判断是否为空 map.isEmpty(); // 9. 获取所有 key遍历用 map.keySet(); // 10. 获取所有 value遍历用 map.values();4. 遍历 HashMap刷题必背 2 种方式 1遍历 key最常用for (Integer key : map.keySet()) { int value map.get(key); System.out.println(key : value); }方式 2遍历键值对for (Map.EntryInteger, Integer entry : map.entrySet()) { int key entry.getKey(); int value entry.getValue(); }HashSet 最全用法HashSet用于判断一个元素是否出现过去重找重复元素1. 导包import java.util.HashSet;2. 创建对象HashSetInteger set new HashSet();3. 核心方法6 个足够// 1. 添加元素重复添加会自动失败 set.add(element); // 2. 判断是否包含 set.contains(element); // 3. 删除元素 set.remove(element); // 4. 大小 set.size(); // 5. 清空 set.clear(); // 6. 是否为空 set.isEmpty();4. 遍历for (Integer num : set) { // 遍历所有不重复元素 }HashMap vs HashSet 怎么选要统计次数、存映射关系 → HashMap只要去重、判断是否存在 → HashSetJava 哈希表高频面试 / 刷题知识点1. 哈希冲突是什么两个不同 key 算出同一个数组下标Java 解决链地址法链表 红黑树优化1. 链地址法最核心哈希表底层是一个数组每个数组位置是一个链表头冲突的 key 就挂在这个链表后面结构数组下标 0 → null 下标 1 → node1 → node2 → node3冲突了就往后链 下标 2 → null ...2. JDK 1.8 升级链表太长 → 转红黑树为了防止链表太长导致查询退化成 O (n)Java 做了优化链表长度 ≥ 8 并且 数组长度 ≥ 64→ 自动转换成 红黑树树节点数量 ≤ 6→ 退化成链表为什么这样链表短的时候快红黑树长的时候查询 O (log n)比 O (n) 快很多三、除了链地址法还有哪些解决冲突方式面试常问对比Java 只用链地址法但你要知道别的方法开放寻址法冲突了就往后找空位置线性探测、二次探测→ 比如 ThreadLocalMap 用这个再哈希法冲突就换一个哈希函数再算一次建立公共溢出区冲突的统一放另一个数组四、HashMap 减少冲突的其他手段高频1. 哈希扰动让 hash 更散列Java 不会直接用key.hashCode()而是做了高低位异或扰动static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }目的让哈希值分布更均匀减少冲突。2. 负载因子 loadFactor默认0.75意思数组满 75% 就扩容太大 → 冲突变多太小 → 空间浪费3. 扩容机制默认容量 16扩容×2扩容后重新计算所有位置打散冲突。两者核心区别对比哈希扰动扩容机制作用对象hash 值数组容量发生时间每次 put 时满负载时结果让 hash 更散数组变大 ×2是否迁移数据不迁移必须迁移所有数据目的减少冲突整体降低冲突频率层级前端优化后端扩容五、一句话总结Java 中 HashMap 解决哈希冲突采用链地址法链表过长转为红黑树配合哈希扰动、负载因子、扩容来减少冲突。2. 为什么哈希表操作是 O (1)哈希函数直接定位下标不遍历全表最坏 O (n)但力扣题目全部按平均 O (1) 算3. 允许 null 吗HashMapkey 允许 1 个 nullvalue 允许多个 nullHashSet允许 1 个 null4. 有序吗无序不保证插入顺序要有序用LinkedHashMap极少用为什么要重写 hashCode () 和 equals ()面试必考如果两个对象equals为 truehashCode 必须相同否则它们会被当成不同 key存到不同位置HashMap 就错乱了所以用自定义对象当 HashMap 的 key必须同时重写 equals 和 hashCode。为什么不重写 equals 和 hashCodeHashMap 就会 “错乱”。先记住一个铁律HashMap 的灵魂规则HashMap 判断两个 key 是否相等分两步先比hashCode不一样 → 直接判定不是同一个 key再比equals不一样 → 也判定不是同一个 key只有 hashCode 相同且 equals 为 trueHashMap 才认为这是同一个 key。场景你自己写了个类没重写 hashCode 和 equalsclass Student { String id; String name; public Student(String id, String name) { this.id id; this.name name; } }现在你做一件事往 HashMap 里 put 一个学生再想 get 出来。Student s1 new Student(001, 张三); map.put(s1, 高三一班); Student s2 new Student(001, 张三); map.get(s2); // 你以为能取到结果是 null为什么会 null核心原因1. 默认的 hashCode ()Object 里的 hashCode 是根据对象内存地址算的。s1 是 new 出来的一个对象s2 是另一个 new 出来的对象地址不一样 →hashCode 不一样HashMap 第一步就判定hashCode 不同 → 不是同一个 key直接去别的位置找找不到返回 null。2. 默认的 equals ()默认 equals 也是比地址return this obj;s1 和 s2 是两个对象 肯定是 false。所以hashCode 不同 equals 不同HashMap 认为这是两个完全不同的 key。结果就 “错乱” 了在你的逻辑里学号一样就是同一个学生但在 HashMap 眼里地址不一样就是两个人于是put 进去的是 s1get 用 s2 找不到你甚至可以 put 两次HashMap 会存两条这就叫错乱、不符合预期易混点一张表看懂区别面试必背实现类底层结构是否有序线程安全null 允许时间复杂度HashMap数组 链表 红黑树无序❌1 个 null keyO(1)Hashtable数组 链表无序✅不允许O(1)LinkedHashMapHashMap 双向链表插入有序❌允许O(1)TreeMap红黑树按键排序❌key 不能为 nullO(log n)关于HashMap和HashSetTreeMap在 Java 里HashSet 底层就是 HashMapTreeSet 底层就是 TreeMap哈希表本质是key-value 结构Set 只是 “只存 key、忽略 value” 的马甲所以大家聊哈希表底层原理、哈希冲突、数组 链表时默认都是在说HashMap因为 HashSet 根本没有自己的底层它就是套了层壳的 HashMap。一句话说清它们的真实关系HashSet 只存 key 的 HashMapTreeSet 只存 key 的 TreeMapLinkedHashSet 只存 key 的 LinkedHashMap看一眼源码你就彻底懂了public class HashSetE { private transient HashMapE,Object map; // 所有 value 都塞一个固定的空对象 private static final Object PRESENT new Object(); public boolean add(E e) { return map.put(e, PRESENT) null; } }所以你往 HashSet 里 add 元素底层其实是往 HashMap 里 put (key, 固定小对象)HashSet 本身没有任何 “哈希表实现”它完全依赖 HashMap。TreeSet / TreeMap 算不算哈希表不算严格来说它们不是哈希表。TreeMap / TreeSet 底层是红黑树没有哈希函数、没有数组、没有哈希冲突时间复杂度是 O (log n)不是 O (1)所以叫哈希表→ 只有HashMap、HashSet、LinkedHashMap、LinkedHashSetTreeMap / TreeSet 是有序树结构不属于哈希表总结HashSet 不是独立实现就是 HashMap所以聊哈希表底层、哈希冲突时默认讲 HashMap 没问题TreeSet/TreeMap 跟哈希表没关系是树真正的哈希表家族HashMapLinkedHashMapHashSet基于 HashMapLinkedHashSet基于 LinkedHashMap结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励