大家好欢迎继续学习《算法面试60讲2026最新版·全真题带解析》专栏上一篇我们系统学习了栈与队列这两个高频基础数据结构掌握了它们的核心特性、底层实现和面试真题今天这一篇我们将学习另一个面试必考的基础数据结构——哈希表Hash Table。哈希表又称散列表是算法面试中“性价比极高”的知识点——它的核心优势是“查找效率极高”平均时间复杂度可达O(1)在实际开发和面试中应用广泛比如缓存、字典、数据去重等场景。无论是校招还是社招哈希表都是高频考点尤其是哈希函数的设计、哈希冲突的解决方法更是面试官重点追问的内容。值得注意的是哈希表的底层实现依然依赖我们前面学过的数组核心容器结合链表或红黑树解决冲突吃透前面的基础学习哈希表会非常轻松。今天这篇内容我们依然聚焦面试考点从定义、核心优势、底层实现哈希函数、冲突解决到面试高频真题一步步讲透让你看完就能应对面试中的相关问题。一、哈希表Hash Table核心定义与优势面试必背1. 哈希表的定义哈希表是一种基于哈希函数实现的“键值对Key-Value”存储数据结构。它的核心思想是通过哈希函数将“键Key”映射到一个固定的索引位置从而实现“快速查找、插入、删除”操作——简单来说就是“给每个键分配一个唯一的‘地址’查找时直接根据地址定位不用遍历整个容器”。举个通俗的例子我们平时用的手机通讯录“联系人姓名”是键Key“电话号码”是值Value我们通过姓名快速查找电话号码本质上就是哈希表的思想——姓名通过“哈希函数”映射到一个存储位置直接定位到对应的电话号码。2. 哈希表的核心优势面试必记哈希表的最大优势的是“查找效率高”这也是它在面试和开发中广泛应用的原因核心优势如下查找效率平均时间复杂度O(1)最坏情况下O(n)哈希冲突严重时但实际开发中几乎不会出现最坏情况。插入、删除效率平均时间复杂度O(1)优于数组插入删除O(n)和链表查找O(n)。灵活性高支持键值对存储键可以是任意类型如整数、字符串无需像数组那样通过下标访问。面试补充哈希表的核心短板是“无序性”——存储的数据没有固定顺序无法像数组那样按顺序遍历另外哈希冲突的处理会影响哈希表的性能这也是面试的重点。二、哈希表的底层实现面试高频追问重中之重哈希表的底层实现核心分为两部分哈希函数Hash Function和哈希冲突解决方法。这两部分是面试必问内容尤其是哈希冲突的解决几乎每个面试官都会追问必须重点掌握。1. 哈希函数Hash Function键映射的核心哈希函数的作用是将任意类型的“键Key”映射到一个固定范围的“索引Index”这个范围通常是哈希表底层数组的长度。简单来说就是“给每个键计算一个唯一的‘地址’”。1哈希函数的设计原则面试必背一个好的哈希函数能最大限度减少哈希冲突面试时被问到“哈希函数怎么设计”直接答这3个原则一致性相同的键经过哈希函数计算后必须得到相同的索引如果同一个键每次计算的索引不一样就无法找到对应的值。均匀性不同的键经过哈希函数计算后应尽量分布在不同的索引位置避免大量键映射到同一个索引导致哈希冲突严重。高效性哈希函数的计算过程要简单、快速时间复杂度为O(1)如果计算太慢会拖累哈希表的整体性能。2常见的哈希函数面试了解即可重点记1-2种实际开发中哈希函数的设计会根据键的类型调整以下是几种常见的哈希函数面试时无需深入实现了解即可取模法最常用对于整数类型的键直接用键值对哈希表底层数组的长度取模Key % 数组长度得到索引。例如数组长度为10键为15索引15%105。折叠法对于长整数或字符串类型的键将其拆分成若干段然后将各段相加再对数组长度取模得到索引。哈希函数优化实际开发中如Java的HashMap会对取模法进行优化先通过位运算减少计算量再取模提升效率。2. 哈希冲突Hash Collision不可避免的问题什么是哈希冲突—— 不同的键Key1 ≠ Key2经过哈希函数计算后得到了相同的索引Index1 Index2这种情况就叫做哈希冲突。面试重点哈希冲突无法完全避免无论哈希函数设计得多好都可能出现不同的键映射到同一个索引的情况我们能做的是通过合理的方法解决冲突降低冲突带来的影响。3. 哈希冲突的解决方法面试必掌握2种核心方法面试中哈希冲突的解决方法重点考察以下2种其中“拉链法”是最常用的必须掌握其原理和实现思路“开放地址法”作为补充了解核心思想即可。1拉链法Chaining最常用面试重点核心思路哈希表底层是一个数组称为“哈希桶”当出现哈希冲突时将冲突的键值对以“链表”或红黑树的形式挂在对应的哈希桶数组索引后面。简单来说就是“同一个索引位置挂一个链表所有冲突的元素都存在这个链表中”。实现细节初始时哈希桶数组为空插入元素时通过哈希函数计算索引若该索引为空直接将键值对存入若该索引已有元素就将新元素插入到链表的头部或尾部。查找元素时通过哈希函数计算索引遍历该索引对应的链表找到对应的键返回对应的值时间复杂度取决于链表的长度理想情况下链表长度为1时间复杂度O(1)。优化当链表长度超过一定阈值如Java HashMap中阈值为8会将链表转为红黑树将时间复杂度从O(n)优化为O(logn)提升查找效率。面试补充拉链法的优点是“简单易实现、冲突处理效率高”缺点是“需要额外存储链表/红黑树的指针占用一定的内存空间”。2开放地址法Open Addressing了解即可核心思路当出现哈希冲突时不使用额外的存储空间而是在哈希桶数组中寻找下一个空闲的索引位置将冲突的元素存入。常见的开放地址法有3种面试时了解名称和核心思想即可无需深入实现线性探测冲突后依次检查下一个索引Index1、Index2...直到找到空闲位置。二次探测冲突后按Index1²、Index-1²、Index2²、Index-2²...的顺序寻找空闲位置。再哈希法冲突后使用另一个哈希函数重新计算索引直到找到空闲位置。面试补充开放地址法的优点是“不占用额外内存”缺点是“容易出现‘聚集效应’多个冲突元素集中在某一片区域导致查找效率下降”实际开发中不如拉链法常用。三、哈希表的面试高频真题必练校招/社招通用哈希表的面试题核心考察“哈希表的应用”和“哈希冲突的理解”以下4道真题是高频考点覆盖基础题和中档题其中前2道是校招必练后2道是社招高频建议动手写代码实现。真题1两数之和LeetCode 1简单校招必练题目给定一个整数数组nums和一个目标值target请你在该数组中找出和为目标值的两个整数并返回它们的数组下标。核心思路哈希表的经典应用利用哈希表“查找效率O(1)”的优势优化暴力法O(n²)为O(n)遍历数组对于每个元素nums[i]计算补数target - nums[i]。判断补数是否在哈希表中若在直接返回补数的下标和当前下标若不在将当前元素和其下标存入哈希表。代码示例Javapublic int[] twoSum(int[] nums, int target) { // 哈希表存储键数组元素值元素下标 Maplt;Integer, Integergt; hashMap new HashMap(); for (int i 0; i nums.length; i) { int complement target - nums[i]; // 检查补数是否在哈希表中 if (hashMap.containsKey(complement)) { // 找到返回两个下标 return new int[]{hashMap.get(complement), i}; } // 未找到将当前元素存入哈希表 hashMap.put(nums[i], i); } // 题目假设存在唯一解此处可忽略异常处理 throw new IllegalArgumentException(No two sum solution); }面试补充这道题是哈希表最基础的应用面试时大概率会被问到不仅要会写代码还要能解释“为什么用哈希表”“哈希表的优势是什么”。真题2有效的字母异位词LeetCode 242简单校招高频题目给定两个字符串s和t判断t是否是s的字母异位词。字母异位词指字母相同但排列顺序不同的字符串。核心思路用哈希表或数组模拟哈希表统计两个字符串中每个字符的出现次数若次数完全一致则是字母异位词。优化思路由于字符串仅包含小写字母共26个可用一个长度为26的数组模拟哈希表效率比HashMap更高数组下标对应字母a对应0b对应1...数组值对应字符出现次数。代码示例Javapublic boolean isAnagram(String s, String t) { // 边界判断长度不同直接返回false if (s.length() ! t.length()) { return false; } // 用数组模拟哈希表存储26个小写字母的出现次数 int[] count new int[26]; // 遍历s统计每个字符出现次数 for (char c : s.toCharArray()) { count[c - a]; // a-a0b-a1对应数组下标 } // 遍历t减去对应字符的出现次数 for (char c : t.toCharArray()) { count[c - a]--; // 若出现负数说明t中有s没有的字符直接返回false if (count[c - a] 0) { return false; } } // 遍历数组若所有元素都为0说明两个字符串字符次数一致 for (int num : count) { if (num ! 0) { return false; } } return true; }真题3三数之和LeetCode 15中等社招高频题目给你一个包含n个整数的数组nums判断nums中是否存在三个元素abc使得a b c 0请你找出所有和为0且不重复的三元组。核心思路排序哈希表或双指针避免重复三元组先将数组排序避免后续出现重复三元组。遍历数组固定第一个元素nums[i]将问题转化为“两数之和”寻找nums[j] nums[k] -nums[i]。用哈希表存储nums[j]判断-nums[i] - nums[j]是否在哈希表中同时注意去重跳过重复的元素。面试补充这道题的重点是“去重”和“哈希表的优化”社招面试中常考需要掌握去重的细节跳过重复的i、j、k。代码示例Java哈希表去重版public ListListInteger threeSum(int[] nums) { ListListIntegergt; result new ArrayList(); // 排序便于去重和后续查找 Arrays.sort(nums); int n nums.length; // 遍历数组固定第一个元素nums[i] for (int i 0; i n; i) { // 去重跳过重复的i避免重复三元组 if (i 0 nums[i] nums[i-1]) { continue; } // 目标值寻找nums[j] nums[k] -nums[i] int target -nums[i]; // 哈希表存储nums[j]key元素值value元素下标用于快速查找 MapInteger, Integer hashMap new HashMap(); for (int j i 1; j n; j) { int complement target - nums[j]; // 检查补数是否在哈希表中且补数下标大于j避免重复 if (hashMap.containsKey(complement)) { // 找到三元组加入结果集 result.add(Arrays.asList(nums[i], nums[j], complement)); // 去重跳过重复的j避免重复三元组 while (j 1 n nums[j] nums[j1]) { j; } } // 将当前元素存入哈希表覆盖重复的下标保证后续查找的是最近的j hashMap.put(nums[j], j); } } return result; }真题4LRU缓存LeetCode 146中等社招必练题目设计一个LRU最近最少使用缓存结构支持get和put操作要求get和put操作的时间复杂度均为O(1)。核心思路哈希表双向链表实现面试重点哈希表存储键值对键缓存key值双向链表的节点实现O(1)查找。双向链表维护缓存的使用顺序最近使用的节点放在链表头部最少使用的节点放在链表尾部。get操作若key存在将该节点移到链表头部返回对应值若不存在返回-1。put操作若key存在更新节点值并移到头部若不存在新增节点到头部若缓存满删除链表尾部节点最少使用并删除哈希表中对应的键。面试补充LRU缓存是哈希表的经典综合应用考察哈希表和双向链表的结合使用社招面试中几乎必考必须掌握实现思路和代码。代码示例Java哈希表双向链表实现// 1. 定义双向链表节点 class DListNode { int key; int value; DListNode prev; // 前驱节点 DListNode next; // 后继节点 // 构造方法 public DListNode() {} public DListNode(int key, int value) { this.key key; this.value value; } } // 2. LRU缓存实现 class LRUCache { private MapInteger, DListNode hashMap; // 哈希表key-节点O(1)查找 private DListNode head; // 双向链表头节点最近使用 private DListNode tail; // 双向链表尾节点最少使用 private int capacity; // 缓存容量 public LRUCache(int capacity) { this.capacity capacity; hashMap new HashMap(capacity); // 初始化虚拟头、尾节点简化边界处理无需判断头/尾为空 head new DListNode(); tail new DListNode(); head.next tail; tail.prev head; } // get操作获取key对应的值不存在返回-1存在则移到头部最近使用 public int get(int key) { if (!hashMap.containsKey(key)) { return -1; } // 找到节点 DListNode node hashMap.get(key); // 移除该节点从原位置删除 removeNode(node); // 将节点移到头部标记为最近使用 addToHead(node); // 返回节点值 return node.value; } // put操作插入/更新key-value超出容量则删除最少使用尾节点前一个 public void put(int key, int value) { if (hashMap.containsKey(key)) { // 存在该key更新值并移到头部 DListNode node hashMap.get(key); node.value value; removeNode(node); addToHead(node); } else { // 不存在该key新增节点 DListNode newNode new DListNode(key, value); hashMap.put(key, newNode); addToHead(newNode); // 检查容量超出则删除最少使用的节点尾节点的前驱 if (hashMap.size() capacity) { DListNode removeNode tail.prev; removeNode(removeNode); hashMap.remove(removeNode.key); // 同步删除哈希表中的key } } } // 辅助方法从双向链表中移除指定节点 private void removeNode(DListNode node) { node.prev.next node.next; node.next.prev node.prev; } // 辅助方法将指定节点添加到双向链表头部头节点之后 private void addToHead(DListNode node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } }四、哈希表面试常见问题必背直接应答除了底层实现和真题以下3个问题是面试中常问的直接背会面试时无需临场思考哈希表的时间复杂度为什么是O(1)—— 理想情况下通过哈希函数可以直接定位到索引无需遍历因此查找、插入、删除的时间复杂度都是O(1)最坏情况下哈希冲突严重链表长度为n时间复杂度为O(n)但实际开发中会通过红黑树优化将复杂度降为O(logn)。哈希冲突的解决方法有哪些—— 核心是拉链法和开放地址法拉链法是将冲突元素以链表/红黑树的形式挂在哈希桶后开放地址法是在哈希桶中寻找空闲位置存储冲突元素。哈希表和数组、链表的区别—— 数组连续存储访问O(1)插入删除O(n)有序链表非连续存储访问O(n)插入删除O(1)有序哈希表基于哈希函数访问、插入删除平均O(1)无序需处理哈希冲突。以上就是哈希表的核心知识点涵盖定义、底层实现哈希函数、冲突解决、面试真题和常见问题都是面试必考点。需要重点注意的是哈希表的底层依赖数组哈希冲突的解决方法尤其是拉链法是面试的重中之重一定要吃透原理结合真题多练习。另外哈希表的应用非常广泛后续学习的很多算法和数据结构都会用到哈希表优化效率因此一定要扎实掌握这部分内容。下一篇我们将学习《字符串常用操作、匹配技巧及面试基础题》继续夯实基础数据结构敬请期待
哈希表：底层实现（哈希函数、冲突解决）+ 真题解析
发布时间：2026/7/24 21:47:54
大家好欢迎继续学习《算法面试60讲2026最新版·全真题带解析》专栏上一篇我们系统学习了栈与队列这两个高频基础数据结构掌握了它们的核心特性、底层实现和面试真题今天这一篇我们将学习另一个面试必考的基础数据结构——哈希表Hash Table。哈希表又称散列表是算法面试中“性价比极高”的知识点——它的核心优势是“查找效率极高”平均时间复杂度可达O(1)在实际开发和面试中应用广泛比如缓存、字典、数据去重等场景。无论是校招还是社招哈希表都是高频考点尤其是哈希函数的设计、哈希冲突的解决方法更是面试官重点追问的内容。值得注意的是哈希表的底层实现依然依赖我们前面学过的数组核心容器结合链表或红黑树解决冲突吃透前面的基础学习哈希表会非常轻松。今天这篇内容我们依然聚焦面试考点从定义、核心优势、底层实现哈希函数、冲突解决到面试高频真题一步步讲透让你看完就能应对面试中的相关问题。一、哈希表Hash Table核心定义与优势面试必背1. 哈希表的定义哈希表是一种基于哈希函数实现的“键值对Key-Value”存储数据结构。它的核心思想是通过哈希函数将“键Key”映射到一个固定的索引位置从而实现“快速查找、插入、删除”操作——简单来说就是“给每个键分配一个唯一的‘地址’查找时直接根据地址定位不用遍历整个容器”。举个通俗的例子我们平时用的手机通讯录“联系人姓名”是键Key“电话号码”是值Value我们通过姓名快速查找电话号码本质上就是哈希表的思想——姓名通过“哈希函数”映射到一个存储位置直接定位到对应的电话号码。2. 哈希表的核心优势面试必记哈希表的最大优势的是“查找效率高”这也是它在面试和开发中广泛应用的原因核心优势如下查找效率平均时间复杂度O(1)最坏情况下O(n)哈希冲突严重时但实际开发中几乎不会出现最坏情况。插入、删除效率平均时间复杂度O(1)优于数组插入删除O(n)和链表查找O(n)。灵活性高支持键值对存储键可以是任意类型如整数、字符串无需像数组那样通过下标访问。面试补充哈希表的核心短板是“无序性”——存储的数据没有固定顺序无法像数组那样按顺序遍历另外哈希冲突的处理会影响哈希表的性能这也是面试的重点。二、哈希表的底层实现面试高频追问重中之重哈希表的底层实现核心分为两部分哈希函数Hash Function和哈希冲突解决方法。这两部分是面试必问内容尤其是哈希冲突的解决几乎每个面试官都会追问必须重点掌握。1. 哈希函数Hash Function键映射的核心哈希函数的作用是将任意类型的“键Key”映射到一个固定范围的“索引Index”这个范围通常是哈希表底层数组的长度。简单来说就是“给每个键计算一个唯一的‘地址’”。1哈希函数的设计原则面试必背一个好的哈希函数能最大限度减少哈希冲突面试时被问到“哈希函数怎么设计”直接答这3个原则一致性相同的键经过哈希函数计算后必须得到相同的索引如果同一个键每次计算的索引不一样就无法找到对应的值。均匀性不同的键经过哈希函数计算后应尽量分布在不同的索引位置避免大量键映射到同一个索引导致哈希冲突严重。高效性哈希函数的计算过程要简单、快速时间复杂度为O(1)如果计算太慢会拖累哈希表的整体性能。2常见的哈希函数面试了解即可重点记1-2种实际开发中哈希函数的设计会根据键的类型调整以下是几种常见的哈希函数面试时无需深入实现了解即可取模法最常用对于整数类型的键直接用键值对哈希表底层数组的长度取模Key % 数组长度得到索引。例如数组长度为10键为15索引15%105。折叠法对于长整数或字符串类型的键将其拆分成若干段然后将各段相加再对数组长度取模得到索引。哈希函数优化实际开发中如Java的HashMap会对取模法进行优化先通过位运算减少计算量再取模提升效率。2. 哈希冲突Hash Collision不可避免的问题什么是哈希冲突—— 不同的键Key1 ≠ Key2经过哈希函数计算后得到了相同的索引Index1 Index2这种情况就叫做哈希冲突。面试重点哈希冲突无法完全避免无论哈希函数设计得多好都可能出现不同的键映射到同一个索引的情况我们能做的是通过合理的方法解决冲突降低冲突带来的影响。3. 哈希冲突的解决方法面试必掌握2种核心方法面试中哈希冲突的解决方法重点考察以下2种其中“拉链法”是最常用的必须掌握其原理和实现思路“开放地址法”作为补充了解核心思想即可。1拉链法Chaining最常用面试重点核心思路哈希表底层是一个数组称为“哈希桶”当出现哈希冲突时将冲突的键值对以“链表”或红黑树的形式挂在对应的哈希桶数组索引后面。简单来说就是“同一个索引位置挂一个链表所有冲突的元素都存在这个链表中”。实现细节初始时哈希桶数组为空插入元素时通过哈希函数计算索引若该索引为空直接将键值对存入若该索引已有元素就将新元素插入到链表的头部或尾部。查找元素时通过哈希函数计算索引遍历该索引对应的链表找到对应的键返回对应的值时间复杂度取决于链表的长度理想情况下链表长度为1时间复杂度O(1)。优化当链表长度超过一定阈值如Java HashMap中阈值为8会将链表转为红黑树将时间复杂度从O(n)优化为O(logn)提升查找效率。面试补充拉链法的优点是“简单易实现、冲突处理效率高”缺点是“需要额外存储链表/红黑树的指针占用一定的内存空间”。2开放地址法Open Addressing了解即可核心思路当出现哈希冲突时不使用额外的存储空间而是在哈希桶数组中寻找下一个空闲的索引位置将冲突的元素存入。常见的开放地址法有3种面试时了解名称和核心思想即可无需深入实现线性探测冲突后依次检查下一个索引Index1、Index2...直到找到空闲位置。二次探测冲突后按Index1²、Index-1²、Index2²、Index-2²...的顺序寻找空闲位置。再哈希法冲突后使用另一个哈希函数重新计算索引直到找到空闲位置。面试补充开放地址法的优点是“不占用额外内存”缺点是“容易出现‘聚集效应’多个冲突元素集中在某一片区域导致查找效率下降”实际开发中不如拉链法常用。三、哈希表的面试高频真题必练校招/社招通用哈希表的面试题核心考察“哈希表的应用”和“哈希冲突的理解”以下4道真题是高频考点覆盖基础题和中档题其中前2道是校招必练后2道是社招高频建议动手写代码实现。真题1两数之和LeetCode 1简单校招必练题目给定一个整数数组nums和一个目标值target请你在该数组中找出和为目标值的两个整数并返回它们的数组下标。核心思路哈希表的经典应用利用哈希表“查找效率O(1)”的优势优化暴力法O(n²)为O(n)遍历数组对于每个元素nums[i]计算补数target - nums[i]。判断补数是否在哈希表中若在直接返回补数的下标和当前下标若不在将当前元素和其下标存入哈希表。代码示例Javapublic int[] twoSum(int[] nums, int target) { // 哈希表存储键数组元素值元素下标 Maplt;Integer, Integergt; hashMap new HashMap(); for (int i 0; i nums.length; i) { int complement target - nums[i]; // 检查补数是否在哈希表中 if (hashMap.containsKey(complement)) { // 找到返回两个下标 return new int[]{hashMap.get(complement), i}; } // 未找到将当前元素存入哈希表 hashMap.put(nums[i], i); } // 题目假设存在唯一解此处可忽略异常处理 throw new IllegalArgumentException(No two sum solution); }面试补充这道题是哈希表最基础的应用面试时大概率会被问到不仅要会写代码还要能解释“为什么用哈希表”“哈希表的优势是什么”。真题2有效的字母异位词LeetCode 242简单校招高频题目给定两个字符串s和t判断t是否是s的字母异位词。字母异位词指字母相同但排列顺序不同的字符串。核心思路用哈希表或数组模拟哈希表统计两个字符串中每个字符的出现次数若次数完全一致则是字母异位词。优化思路由于字符串仅包含小写字母共26个可用一个长度为26的数组模拟哈希表效率比HashMap更高数组下标对应字母a对应0b对应1...数组值对应字符出现次数。代码示例Javapublic boolean isAnagram(String s, String t) { // 边界判断长度不同直接返回false if (s.length() ! t.length()) { return false; } // 用数组模拟哈希表存储26个小写字母的出现次数 int[] count new int[26]; // 遍历s统计每个字符出现次数 for (char c : s.toCharArray()) { count[c - a]; // a-a0b-a1对应数组下标 } // 遍历t减去对应字符的出现次数 for (char c : t.toCharArray()) { count[c - a]--; // 若出现负数说明t中有s没有的字符直接返回false if (count[c - a] 0) { return false; } } // 遍历数组若所有元素都为0说明两个字符串字符次数一致 for (int num : count) { if (num ! 0) { return false; } } return true; }真题3三数之和LeetCode 15中等社招高频题目给你一个包含n个整数的数组nums判断nums中是否存在三个元素abc使得a b c 0请你找出所有和为0且不重复的三元组。核心思路排序哈希表或双指针避免重复三元组先将数组排序避免后续出现重复三元组。遍历数组固定第一个元素nums[i]将问题转化为“两数之和”寻找nums[j] nums[k] -nums[i]。用哈希表存储nums[j]判断-nums[i] - nums[j]是否在哈希表中同时注意去重跳过重复的元素。面试补充这道题的重点是“去重”和“哈希表的优化”社招面试中常考需要掌握去重的细节跳过重复的i、j、k。代码示例Java哈希表去重版public ListListInteger threeSum(int[] nums) { ListListIntegergt; result new ArrayList(); // 排序便于去重和后续查找 Arrays.sort(nums); int n nums.length; // 遍历数组固定第一个元素nums[i] for (int i 0; i n; i) { // 去重跳过重复的i避免重复三元组 if (i 0 nums[i] nums[i-1]) { continue; } // 目标值寻找nums[j] nums[k] -nums[i] int target -nums[i]; // 哈希表存储nums[j]key元素值value元素下标用于快速查找 MapInteger, Integer hashMap new HashMap(); for (int j i 1; j n; j) { int complement target - nums[j]; // 检查补数是否在哈希表中且补数下标大于j避免重复 if (hashMap.containsKey(complement)) { // 找到三元组加入结果集 result.add(Arrays.asList(nums[i], nums[j], complement)); // 去重跳过重复的j避免重复三元组 while (j 1 n nums[j] nums[j1]) { j; } } // 将当前元素存入哈希表覆盖重复的下标保证后续查找的是最近的j hashMap.put(nums[j], j); } } return result; }真题4LRU缓存LeetCode 146中等社招必练题目设计一个LRU最近最少使用缓存结构支持get和put操作要求get和put操作的时间复杂度均为O(1)。核心思路哈希表双向链表实现面试重点哈希表存储键值对键缓存key值双向链表的节点实现O(1)查找。双向链表维护缓存的使用顺序最近使用的节点放在链表头部最少使用的节点放在链表尾部。get操作若key存在将该节点移到链表头部返回对应值若不存在返回-1。put操作若key存在更新节点值并移到头部若不存在新增节点到头部若缓存满删除链表尾部节点最少使用并删除哈希表中对应的键。面试补充LRU缓存是哈希表的经典综合应用考察哈希表和双向链表的结合使用社招面试中几乎必考必须掌握实现思路和代码。代码示例Java哈希表双向链表实现// 1. 定义双向链表节点 class DListNode { int key; int value; DListNode prev; // 前驱节点 DListNode next; // 后继节点 // 构造方法 public DListNode() {} public DListNode(int key, int value) { this.key key; this.value value; } } // 2. LRU缓存实现 class LRUCache { private MapInteger, DListNode hashMap; // 哈希表key-节点O(1)查找 private DListNode head; // 双向链表头节点最近使用 private DListNode tail; // 双向链表尾节点最少使用 private int capacity; // 缓存容量 public LRUCache(int capacity) { this.capacity capacity; hashMap new HashMap(capacity); // 初始化虚拟头、尾节点简化边界处理无需判断头/尾为空 head new DListNode(); tail new DListNode(); head.next tail; tail.prev head; } // get操作获取key对应的值不存在返回-1存在则移到头部最近使用 public int get(int key) { if (!hashMap.containsKey(key)) { return -1; } // 找到节点 DListNode node hashMap.get(key); // 移除该节点从原位置删除 removeNode(node); // 将节点移到头部标记为最近使用 addToHead(node); // 返回节点值 return node.value; } // put操作插入/更新key-value超出容量则删除最少使用尾节点前一个 public void put(int key, int value) { if (hashMap.containsKey(key)) { // 存在该key更新值并移到头部 DListNode node hashMap.get(key); node.value value; removeNode(node); addToHead(node); } else { // 不存在该key新增节点 DListNode newNode new DListNode(key, value); hashMap.put(key, newNode); addToHead(newNode); // 检查容量超出则删除最少使用的节点尾节点的前驱 if (hashMap.size() capacity) { DListNode removeNode tail.prev; removeNode(removeNode); hashMap.remove(removeNode.key); // 同步删除哈希表中的key } } } // 辅助方法从双向链表中移除指定节点 private void removeNode(DListNode node) { node.prev.next node.next; node.next.prev node.prev; } // 辅助方法将指定节点添加到双向链表头部头节点之后 private void addToHead(DListNode node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } }四、哈希表面试常见问题必背直接应答除了底层实现和真题以下3个问题是面试中常问的直接背会面试时无需临场思考哈希表的时间复杂度为什么是O(1)—— 理想情况下通过哈希函数可以直接定位到索引无需遍历因此查找、插入、删除的时间复杂度都是O(1)最坏情况下哈希冲突严重链表长度为n时间复杂度为O(n)但实际开发中会通过红黑树优化将复杂度降为O(logn)。哈希冲突的解决方法有哪些—— 核心是拉链法和开放地址法拉链法是将冲突元素以链表/红黑树的形式挂在哈希桶后开放地址法是在哈希桶中寻找空闲位置存储冲突元素。哈希表和数组、链表的区别—— 数组连续存储访问O(1)插入删除O(n)有序链表非连续存储访问O(n)插入删除O(1)有序哈希表基于哈希函数访问、插入删除平均O(1)无序需处理哈希冲突。以上就是哈希表的核心知识点涵盖定义、底层实现哈希函数、冲突解决、面试真题和常见问题都是面试必考点。需要重点注意的是哈希表的底层依赖数组哈希冲突的解决方法尤其是拉链法是面试的重中之重一定要吃透原理结合真题多练习。另外哈希表的应用非常广泛后续学习的很多算法和数据结构都会用到哈希表优化效率因此一定要扎实掌握这部分内容。下一篇我们将学习《字符串常用操作、匹配技巧及面试基础题》继续夯实基础数据结构敬请期待
)
