hot100——哈希表

哈希表哈希表Hash Table是一种非常重要的数据结构它通过哈希函数将键Key映射到存储位置从而实现平均 O(1) 时间复杂度的插入、删除和查找。与列表List或向量Vector相比哈希表不关心元素的顺序而是通过键直接访问值因此特别适合需要快速查找、去重或关联映射的场景。一、哈希表的核心概念键Key唯一标识用于查找。值Value与键关联的数据。哈希函数Hash Function将键转换为数组索引决定存储位置。哈希冲突Collision不同键映射到同一索引解决方法有链地址法拉链法、开放地址法等。特点查找、插入、删除平均时间复杂度 O(1)。元素无序C 的unordered_map和 Python 3.7 的dict实际上保留了插入顺序但这不是哈希表的固有特性而是实现细节逻辑上不应依赖顺序。内存占用通常比数组大因为需要存储额外的桶和指针。二、Python 中的哈希表dictPython 的dict是内置的哈希表实现键可以是任何可哈希的类型不可变对象如字符串、数字、元组等值可以是任意对象。# 创建 d {} # 空字典 d {a: 1, b: 2} # 插入/更新 d[c] 3 # 插入 d[a] 10 # 更新 # 查找 value d.get(b, 0) # 不存在返回默认值 if c in d: # 判断键是否存在 print(d[c]) # 删除 del d[a] # 删除键 value d.pop(b) # 删除并返回值 d.clear() # 清空 # 遍历 for key, val in d.items(): print(key, val)注意事项键必须可哈希不可变。列表、字典不能作为键。Python 3.7 的dict会保留插入顺序但这并非哈希表本质不要依赖顺序做逻辑判断。三、C 中的哈希表std::unordered_mapC 标准库提供unordered_map头文件unordered_map基于哈希表实现。键可以是任何支持哈希的类型基本类型、std::string等对于自定义类型需要提供哈希函数和相等比较函数。#include unordered_map #include string using namespace std; // 创建 unordered_mapstring, int mp; mp[a] 1; // 插入/更新 mp.insert({b, 2}); // 查找 if (mp.find(c) ! mp.end()) { int val mp[c]; } // 或者 auto it mp.find(b); if (it ! mp.end()) { cout it-second; } // 删除 mp.erase(a); mp.clear(); // 遍历 for (auto p : mp) { cout p.first : p.second endl; }注意事项C 的unordered_map默认无序但你可以使用std::map红黑树保持有序但查找 O(log n)。键类型需要提供std::hash特化和operator基本类型和std::string已内置。可以预先分配桶数以减少哈希冲突mp.reserve(100)。四、哈希表 vs. 列表/向量list/vector举例说明场景一统计数组中每个数字出现的次数哈希表dict或unordered_map一次遍历O(n) 时间。列表无法直接做到需要额外排序或嵌套循环O(n²) 或 O(n log n)。场景二存储一个待处理的顺序队列列表vector或deque更合适因为需要保持顺序和随机访问。哈希表不适合因为无法高效地保持顺序或按位置访问。五、如何选择需要快速查找、去重、关联映射→ 用哈希表dict/unordered_map。需要保持顺序、随机访问、频繁尾部插入→ 用vectorC或listPython。需要频繁在任意位置插入/删除但不要求随机访问→ 用listC 双向链表或deque双端队列。六、常见误区哈希表就是字典对Python 的dict就是哈希表C 的unordered_map是哈希表而map是红黑树有序。哈希表总是 O(1)平均是 O(1)但最坏情况哈希冲突严重可能退化到 O(n)。好的哈希函数和负载因子控制可避免。哈希表可以当列表用不可以哈希表通过键访问不是整数索引。如果需要通过位置访问请用列表。七、桶数组一、什么是桶数组哈希表内部实际上是一个数组这个数组的每个元素被称为一个“桶”bucket。桶的作用是存储实际的数据键值对。当你向哈希表插入一个键值对时哈希函数会计算键的哈希值然后通过某种方式比如取模运算得到该键应该放入的桶的索引即数组的下标然后将键值对放入那个桶中。形象比喻桶数组就像一个公寓楼有编号为 0、1、2、…、N-1 的房间桶。哈希函数就是门牌号分配规则根据住户的身份证号键计算出他应该住在哪个房间。当你要找某个住户时只需根据他的身份证号计算出房间号然后直接去那个房间找而不需要挨家挨户敲门。二、桶数组的结构桶数组Bucket Array 索引 0 1 2 3 4 5 ... 内容 [桶0] [桶1] [桶2] [桶3] [桶4] [桶5] ...每个桶可以存储一个键值对如果采用开放地址法解决冲突每个桶只存一个元素冲突时找下一个空桶。一个链表的头节点如果采用链地址法每个桶指向一个链表链表节点存储哈希值相同的多个键值对。一个红黑树的根节点当链表过长时Java 8 以后会转为树提高性能。、三、桶数组与哈希冲突由于哈希函数可能把不同的键映射到同一个桶索引这就产生了“哈希冲突”。桶数组的设计就是为了解决冲突链地址法每个桶是一个链表或红黑树。插入时如果桶为空创建链表头如果桶已有节点就添加到链表末尾或树中。查找时先定位到桶然后在桶的链表/树中顺序查找。开放地址法每个桶只存一个元素。如果目标桶已被占用就按照某种规则如线性探测、二次探测寻找下一个空桶。四、桶数组的大小和扩容初始时桶数组有一定的大小比如 16 个桶。随着插入的元素越来越多每个桶中的元素链表长度也会增加导致查找效率下降从 O(1) 退化为 O(n)。为了维持性能哈希表会监控一个指标叫“负载因子”load factor 元素个数 / 桶数组长度。当负载因子超过阈值如 0.75时哈希表就会进行扩容创建一个新的更大的桶数组通常长度翻倍然后重新计算每个已有元素的哈希值将它们放入新桶数组的合适位置这个过程称为“rehash”。五、Python 和 C 中的桶数组Python 的dict使用开放地址法桶数组是一个PyDictEntry数组每个条目存储哈希值、键指针、值指针。Python 会确保桶数组长度是 2 的幂次负载因子约为 2/3。C 的std::unordered_map使用链地址法桶数组是一个__bucket_type数组每个桶指向一个链表节点。你可以通过bucket_count()获取桶的数量max_load_factor()查看负载因子。六、桶数组与普通数组的区别桶数组就是哈希表内部用来存储数据的数组每个桶可以是一个元素开放地址法或一个链表的头节点链地址法。它决定了哈希表的容量和性能。当两个不同的键经过哈希函数计算后得到相同的哈希值更准确地说是经过取模运算后得到相同的桶索引时就会发生哈希冲突。冲突发生后这两个键值对会被存储在同一个桶中。具体存储方式取决于哈希表的冲突解决策略链地址法桶中维护一个链表或红黑树所有哈希到该桶的元素都放在这个链表里。开放地址法桶中只能放一个元素冲突时会按照探测序列如线性探测找到下一个空桶存放另一个元素。但无论哪种策略冲突的键值对都会存在于同一个桶或与之相邻的桶中这是哈希表处理冲突的基本事实。七、哈希桶哈希桶Hash Bucket是哈希表内部桶数组中的每一个槽位slot。它是在哈希函数计算后用来实际存储数据的基本单元。桶数组Bucket Array是哈希表底层的一个连续数组它的每个元素就是一个哈希桶。所以“桶数组”指的是整个数组结构而“哈希桶”指的是数组中的单个条目。例如一个长度为 8 的桶数组索引: 0 1 2 3 4 5 6 7 内容: [桶0] [桶1] [桶2] [桶3] [桶4] [桶5] [桶6] [桶7]每个桶[i]就是一个哈希桶。1.两数之和解题思路对于这种求2个变量的情况可以遍历其中一个变量把它当作常量看待然后只需要处理另一个变量就行。代码pythonclass Solution(object): def twoSum(self, nums, target): :type nums: List[int] :type target: int :rtype: List[int] dict {} # 创建哈希表键是数组值值是数组值对应的索引 for j, x in enumerate(nums): if target - x in dict: return [dict[target - x], j] dict[x] jC注意C返回的是{it-second, j}为什么是{}呢题目中不是说返回值是[1,2]这种么你看到代码中的return {it-second, j};可能会觉得像 Python 的字典{}在 Python 中表示字典但在C 中这完全是两回事。在 C 中{it-second, j}是列表初始化list initialization它用于构造一个vectorint对象其中包含两个整数元素it-second和j。这里的大括号{}不是字典而是用来表示一个初始化列表std::initializer_list专门用于快速初始化容器。具体来说vectorint有一个构造函数接受std::initializer_listint因此你可以直接写return {a, b};来返回一个包含a和b两个整数的vector。这个语法是 C11 引入的目的是简化代码避免显式写出vectorint{a, b}。所以return {it-second, j};的含义是创建一个临时的vectorint对象其第一个元素是it-second即另一个数的索引第二个元素是j当前数的索引然后将这个vector作为函数返回值。这正是题目要求返回的下标数组[0, 1]的形式。你之前可能把 C 的{}和 Python 的字典{}混淆了但两者在语法和语义上完全不同Python 中{key: value}是字典。C 中{value1, value2}是初始化列表通常用于初始化数组或容器。因此代码没有问题它正确返回了vectorint类型的结果。你之前遇到的报错只是因为缺少了函数末尾的return {};语句与这里的列表初始化无关。class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, int idx; for(int j0;jnums.size();j) { int x nums[j]; auto it idx.find(target - x); if(it ! idx.end()) return {it-second, j}; idx[x] j; } return {}; } };49、字母异位词分组解题思路因为所有的字母异位词其实都是一个词的排列组合追根溯源其实都是一个词那么如何找到这个根呢排序把每个字符串都进行排序排序后是同样的词那么这些字符串就是一组字母异位词。注意1sorted_s .join(sorted(s))这行代码的作用是将字符串s中的字符按字母顺序字典序重新排列生成一个新的字符串。具体分两步sorted(s)Python 内置函数sorted()会接收一个可迭代对象这里是一个字符串将其中的每个字符作为单独元素按字符的 Unicode 码点通常与 ASCII/字母顺序一致从小到大排序然后返回一个字符列表。例如s cbasorted(s)得到[a, b, c]。.join(...)将上一步得到的字符列表用空字符串连接起来形成一个字符串。例如.join([a, b, c])得到abc。所以整体效果无论s原来是abc、bca还是cab经过排序后都会变成相同的abc。这样所有字母异位词即字符相同但顺序不同的单词就会拥有相同的键从而被分到同一组。注意2为什么要使用引用呢// 使用引用避免拷贝 for(auto it:sort_s) { ans.push_back(it.second); }在 C 的范围for循环中如果不使用引用即for (auto p : mp)则每次迭代都会拷贝哈希表中的一个键值对pairconst string, vectorstring。拷贝过程包括拷贝字符串p.first深拷贝。拷贝vectorstring其中每个字符串也会被拷贝。这会产生大量不必要的内存分配和数据复制尤其是当字符串很长、每组单词很多时性能损耗严重。使用引用auto p的好处避免拷贝直接引用原对象零开销。如果你需要修改p.second例如清空或修改 vector引用也是必须的本题虽然只读取但引用仍能提高效率。另外由于哈希表的键是constp.first不可修改但p.second可以修改。使用const auto p可以同时避免拷贝且保证不修改但一般用auto即可。总结使用引用是为了高效避免不必要的拷贝。C 的sort和 Python 的sorted有什么不同Cvectorint v {3, 1, 4}; sort(v.begin(), v.end()); // v 变为 {1, 3, 4}pythonlst [3, 1, 4] new_lst sorted(lst) # new_lst [1, 3, 4]; lst 不变 # 原地排序用 lst.sort()关键区别总结Csort是原地修改不返回新容器Pythonsorted返回新列表原数据不变。C 的sort需要传入迭代器范围Python 的sorted直接接收可迭代对象。Python 的sorted可以排序任何可迭代对象包括字符串、元组等而 C 的sort只能用于支持随机访问迭代器的容器如vector、deque、array等。代码pythonclass Solution(object): def groupAnagrams(self, strs): :type strs: List[str] :rtype: List[List[str]] # 构建哈希表 sorted_dict {} for str in strs: # 对字符串组中的每个字符串进行排序 sorted_str .join(sorted(str)) # 如果排序后的字符串不在原有哈希表的键中则初始化该键值为空列表 if sorted_str not in sorted_dict: sorted_dict[sorted_str] [] sorted_dict[sorted_str].append(str) # 返回字典中的所有值按列表形式返回 return list(sorted_dict.values())cclass Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring, vectorstring sort_s; vectorvectorstring ans; for (string s:strs) { // 对key进行排序,用sort()函数没有返回值 string key s; sort(key.begin(),key.end()); sort_s[key].push_back(s); // 自动创建空 vector 并添加 } // 使用引用避免拷贝 for(auto it:sort_s) { ans.push_back(it.second); } return ans; } };128.最长连续序列解题思路本题要求求最长连续序列其中整数数组是未排序的对于nums中的x我们要判断x1,x2,x3……xm是否存在nums中并统计该序列的长度。1.我们把所有数都放到哈希表当中哈希表当中每个数都不相同这样查询一个数所需要的时间复杂度就是o(1);2.我们遍历哈希表起点为x但是如果x-1也在哈希表当中那么就是说明x不是最长序列的起点需要继续往后遍历。因为以x-1为起点的序列长度一定是大于以x为序列起点的长度。这样我们查询一个元素是否在哈希表当中时间复杂度是O(1)而后遍历x1,x2,x3,……是否在哈希表当中时间复杂度是o(n)远小于遍历原数组nums的时间复杂度O(n^2);适当优化而后当得到序列的长度ans的时候如果ans*2len(哈希表)那么就说明此时的序列长度是大于一半的哈希表那么没有余下的序列是可以大于len(哈希表)/2如果有这两条链表长度之和便大于len(哈希表)这不合理此时可以直接返回结果。代码pythonclass Solution(object): def longestConsecutive(self, nums): :type nums: List[int] :rtype: int st set(nums) m len(st) ans 0 for x in st: # 如果num-1也在哈希表中说明num不是起点 if x - 1 in st: continue y x 1 while y in st: y 1 # 此时y-1是连续序列的最后一位,那么序列的长度是y-1 - x 1 y - x ans max(ans , y - x) # 当ans的长度大于哈希表的一半以上那么余下的就没有超过一半的此时ans就是最大最长的 if ans * 2 m: break return ansCclass Solution { public: int longestConsecutive(vectorint nums) { unordered_setint s(nums.begin(),nums.end()); int m s.size(); int ans 0; for(int x:s) { //if(s.count(x-1)) if(s.contains(x-1)) continue; int y x1; //while(s.count(y)) while(s.contains(y)) y; ans max(ans, y-x); if(ans * 2m) break; } return ans; } };参考哈希表 O(n) 做法Python/Java/C/C/Go/JS/Rust347.前K个高频元素解题思路桶排序题目中要统计数组中前K个高频元素我们想到了哈希表先遍历整个数组得到每个数字的出现频次然后再构建桶数组每个下标代表数字出现的频次然后值就是对应出现频次的数字可以有一个或者多个也可以没有。而后倒序遍历桶数组取出前K个高频元素。注意桶数组的大小是len(nums)1因为对于nums而言出现的频次可能是[0, n]在nums中0不可能出现但是在桶数组当中0是必须要的数组下标所以桶数组的大小是len(nums)1。例如nums [1,1,1,2,2,3] ,k2桶数组大小为7从bucket[0] - bucket[6]1存入bucket[3]中2存入bucket[2]中3存入bucket[1]中索引 0 1 2 3 4 5 6桶数组 [] [3] [2] [1] [] [] []而后从后向前遍历桶数组取出前K个高频元素i6桶数组为空跳过i5跳过i4跳过i3取出1i2取出2结果[1,2]得到前k个高频结果返回结果。代码pythonclass Solution(object): def topKFrequent(self, nums, k): :type nums: List[int] :type k: int :rtype: List[int] # 统计频率 freq {} for num in nums: freq[num] freq.get(num,0) 1 # 构建桶数组 bucket [[] for _ in range(len(nums)1)] # 在桶数组中存入对应的值 for num, fre in freq.items(): bucket[fre].append(num) # 从后往前遍历bucket取出前k个元素 ans [] for i in range(len(nums), 0,-1): for nums in bucket[i]: ans.append(nums) if len(ans) k: return ans return ansCclass Solution { public: vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int mp; // 统计原数组当中每个数出现的频次 for(int num:nums) { mp[num] 1; } // 创建桶数组,将对应频次的数据存入桶数组当中 vectorvectorint bucket(nums.size()1); for(auto [num, freq] : mp) bucket[freq].push_back(num); // 从后往前遍历取出前K个高频元素 vectorint ans; for(int i nums.size(); i 0;i--) { for(int num :bucket[i]) ans.push_back(num); if(ans.size()k) // break; return ans; } return ans; } };438.找到字符串中所有字母异位词解题思路本题要在S中找到所有p的异位词的子串我们想到滑动窗口在s中以p长度的窗口遍历s每次移动比较窗口中的子串和p是否相等不过这里的比较采取的是比较字母出现的次数和p当中是否一致因此我们使用哈比表来统计p中的字母出现次数以及s窗口中字母的出现次数如果次数相同则将窗口的左下标存入结果当中。代码注意C 的std::arrayint, 26固定大小为 26所有位置初始为 0。即使某个字符计数减到 0该位置仍然是 0不会消失。比较两个数组时所有位置包括 0都会参与比较所以结果正确。Python 的dict动态变化值为 0 的键仍然存在导致比较时多出p中没有的字符计数 0从而不相等。pythonclass Solution(object): def findAnagrams(self, s, p): :type s: str :type p: str :rtype: List[int] # 统计p中字母的出现次数 cnt_p {} cnt_s {} for c in p: cnt_p[c] cnt_p.get(c, 0) 1 # 遍历S查找所有满足条件的子串 ans [] for right, c in enumerate(s): # 注意不能直接使用cnt_s[c]1因为cnt_S开始是空字典c这个键不存在该字典中会报错 cnt_s[c] cnt_s.get(c, 0) 1 left right - len(p) 1 if left 0: continue if cnt_p cnt_s: ans.append(left) cnt_s[s[left]] - 1 # 这个地方要注意窗口移动的时候左边这个元素如果次数变为0但是不会从字典中删除的在字典中还是会保留下来的 # 但是cnt_p中是有可能没有这个键的一比较就会返回false无法得到正确结果 if cnt_s[s[left]] 0: del cnt_s[s[left]] return ansC疑问1arrayint, 26 cnt_p{};std::array是 C11 引入的固定大小数组容器定义在array头文件中。它的语法是array类型, 大小 数组名;arrayint, 26表示一个包含 26 个int元素的数组。后面的{}是值初始化value-initialization对于int类型会将所有元素初始化为0。所以arrayint, 26 cnt_p{};等价于int cnt_p[26] {0};但std::array提供了更丰富的功能如可作为函数参数、支持迭代器、可拷贝等。注意使用std::array需要包含头文件array。你的代码如果没有包含可能编译不过但力扣的环境可能默认包含了。为了可移植性最好加上#include array。疑问2两个Array可以直接比较是否相等么if(cnt_p cnt_s) ans.push_back(left);可以因为std::array重载了运算符其行为是逐元素比较只有当两个数组的每个对应元素都相等时才返回true。这非常方便免去了手动写循环比较。注意普通 C 风格数组如int cnt_p[26]不能直接用比较因为数组名会退化为指针比较的是地址。而std::array是类对象支持成员比较。因此你的代码中cnt_p cnt_s是完全正确的它会在 O(26) 时间内比较两个频率数组是否相等。class Solution { public: vectorint findAnagrams(string s, string p) { arrayint, 26 cnt_p{}; // 统计p中字母的出现次数 for(char c : p) { cnt_p[c-a]; } // 在s中以定长的窗口移动和p进行比较 vectorint ans; arrayint, 26 cnt_s{}; for(int right0;rights.size();right) { // 统计s窗口中字母出现次数 cnt_s[s[right]-a]; int left right - p.size() 1; if(left 0) continue;// 窗口大小不足p.size()继续往后遍历 if(cnt_p cnt_s) ans.push_back(left); cnt_s[s[left]-a]--;// 左边数字离开窗口对应在字典中的次数需要减1 } return ans; } };560.和为K的子数组解题思路对于一个数组而言任意子数组的和都可以表示为2个前缀和的差(pre[0] 0)如果 sum[0] 0 sum[1] array[0] sum[2] array[0] array[1] sum[3] array[0] array[1] array[2] ; 数组array [1,2,3,4,5,6,7] 下标 [0,1,2,3,4,5,6] 45 array[3]array[4]sum[5]-sum[3] 任意的 ij ; sum[i] - sum[j] ( array[0] array[1] ... array[j] array[j1] ...array[i-1] ) - (array[0] array[1] array[j-1] array[1] sum[2] - sum[1]; array[0] sum[1] - sum[0]; 也可以表示成 两个前缀和的差 array[k] sum[k1] - sum[k] sum[k] sum[k1] - array[k] 也就是 sum[k] k的数值 所对应求和数组的最后一位的下标1sum[3] array[0] array[1] array[2] ; 3 21 因此任意区间的和都可以用两个前缀和之差表示 如果 sum[0] array[0] sum[1] array[0] array[1] sum[2] array[0] array[1] array[2] sum[3] array[0] array[1] array[2] array[3] array[1] sum[1]-sum[0] array[0] sum[0] 无法表示成两个前缀和的差题目中要求的是和为K的子数组我们假定有俩个前缀和s[j]以及s[i]其中s[j] - s[i] ks[j] nums[0] nums[1] nums[2] …… nums[j-1]s[i] nums[0] nums[1] nums[2] …… nums[i - 1]其中我们用哈希表存储每个前缀和出现的次数而后s[j] - s[i] k s[i] s[j] - k因此我们只需要遍历nums而后查找哈希表当中是否存在s[j] - k的前缀和即可得到结果。但是这里要注意一点我们是要先将前缀和存入哈希表再将前缀和更新为加上当前时刻的值的前缀和这是为什么呢因为我们得到子数组的结果s[i] s[j] - k子数组是从i下标开始到当前的索引下标这个区间内的值是等于K的。代码pythonclass Solution(object): def subarraySum(self, nums, k): :type nums: List[int] :type k: int :rtype: int cnt defaultdict(int) ans, s 0, 0 for x in nums: cnt[s] 1 s x ans cnt[s - k] return ansCclass Solution { public: int subarraySum(vectorint nums, int k) { unordered_mapint, int mp; int ans 0; int s 0; for(int x :nums) { mp[s]; sx; ans mp[s - k]; } return ans; } };参考前缀和哈希表从两次遍历到一次遍历附变形题Python/Java/C/Go/JS/Rust