哈希表的基本概念

什么是哈希表（Hash Table）？

哈希表是一种 根据“键（Key）”快速查找“值（Value）” 的数据结构。它内部通常使用 数组 + 哈希函数 实现：

键（key）：用来唯一标识一个值，比如身份证号、用户名等；
值（value）：对应于键的存储内容；
哈希函数：将键映射为数组索引（通常是整数）；
冲突解决：如果两个键映射到了同一个位置，需要处理冲突，Python中的字典使用了链地址法（开链法）解决。

Python 中的哈希结构

Python 中内置了两种最常用的哈希结构：

dict（字典）：键值对的存储
set（集合）：只存储键（不重复）

例如：

# 字典
d = {'apple': 3, 'banana': 5}
print(d['apple'])  # 输出 3

# 集合
s = set([1, 2, 3])
print(2 in s)  # 输出 True

它们的**查找、插入、删除的平均时间复杂度都是 O(1)**，这就是哈希表非常高效的原因。

哈希表的常见用途

在 LeetCode 中，哈希结构主要应用于以下场景：

查找是否存在某个元素（集合 set）

seen = set()
if x in seen:
    print("存在")
else:
    seen.add(x)

计数统计（字典 dict）

count = {}
for num in nums:
    count[num] = count.get(num, 0) + 1

或者用 collections.Counter 更简洁：

from collections import Counter
count = Counter(nums)

去重（集合 set）

unique_nums = list(set(nums))

构造映射关系（字典 dict）

index_map = {}
for i, val in enumerate(nums):
    index_map[val] = i

优化暴力搜索为 O(1) 查找（Two Sum 典型写法）

def twoSum(nums, target):
    hashmap = {}
    for i, num in enumerate(nums):
        if target - num in hashmap:
            return [hashmap[target - num], i]
        hashmap[num] = i

基础练习题

题目 1：数组中是否存在重复元素（简单）

给定一个整数数组 nums，判断是否存在重复元素。如果存在，返回 True；否则，返回 False。

提示：

使用集合检查元素是否已经出现过；
注意时间复杂度的要求。

使用什么哈希结构？为什么使用这个？

使用的哈希结构：set（集合），理由如下：

集合是一个无序且不重复的数据结构
集合的插入和查找操作平均时间复杂度为O(1)
集合用来检测“是否已出现某个数”，效率非常高，远优于线性查找或两重循环

def containsDuplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

复杂度类型	分析
时间复杂度	O(n)，最多遍历一遍数组，每次操作集合是 O(1)
空间复杂度	O(n)，最坏情况所有元素都加入集合

题目 2：统计字符串中字母出现的次数（简单）

输入一个字符串 s，统计其中每个字符出现的次数，并返回一个字典。

例如输入：

s = "hello"

输出可能是：

{'h': 1, 'e': 1, 'l': 2, 'o': 1}

提示：

用字典（或 collections.Counter）来统计频率；
注意大小写敏感性问题。

使用什么哈希结构？为什么使用这个？

使用的哈希结构：dict（字典），理由如下：

字典适合用来构建键值映射：字符 -> 出现次数
字典可以高效统计每个字符的频率
字典插入和查找的平均时间复杂度都是 O(1)

法一：手动统计

def count_characters(s):
    count = {}
    for char in s:
        if char in count:
        	count[char] += 1
        else:
            count[char] = 1
    return count

法二：使用 collections.Counter

from collections import Counter

def count_characters(s):
    return dict(Counter(s))

复杂度类型	分析
时间复杂度	O(n)，需要遍历整个字符串
空间复杂度	O(1)（固定大小字符集，如英文小写字母），否则为 O(k)，k 是不同字符数

题目 3：判断两个字符串是否为字母异位词（简单）

输入两个字符串 s 和 t，判断它们是否是由相同字符组成的（顺序不同的也算）。

例如：

输入：s = "anagram", t = "nagaram" → 输出：True
输入：s = "rat", t = "car" → 输出：False

提示：

使用字典统计每个字符出现的次数；
或者用 Python 中的 collections.Counter 比较两个字符串。

使用什么哈希结构？为什么使用这个？

使用的哈希结构：dict（字典），理由如下：

需要统计两个字符串中每个字符的出现次数
如果两个字符串的“字符频率”完全一致，就是异位词
字典适合用来做“频率统计”的操作
可以使用 collections.Counter 简化实现

法一：手动统计频率并比较两个字典

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    
    count_s = {}
    count_t = {}
    
    for ch in s:
        count_s[ch] = count_s.get(ch, 0) + 1
        
    for ch in t:
        count_t[ch] = count_t.get(ch, 0) + 1
    
    return count_s == count_t

方法二：使用 collections.Counter 一行解决

from collections import Counter

def isAnagram(s, t):
    return Counter(s) == Counter(t)

复杂度类型	分析
时间复杂度	O(n)，n 是字符串长度
空间复杂度	O(1)，如果字符集是有限的（如小写字母），否则 O(k)，k 为不同字符数

题目 4：找出数组中和为 target 的两个数（中等）

给你一个整数数组 nums 和一个目标值 target，找出和为 target 的两个数，返回它们的下标。

示例：

输入: nums = [2, 7, 11, 15], target = 9
输出: [0, 1]  # 因为 nums[0] + nums[1] = 2 + 7 = 9

提示：

回忆我们讲过的 Two Sum 哈希解法；
使用字典记录数字与其下标的映射。

使用什么哈希结构？为什么使用这个？

使用的哈希结构：dict（字典），理由如下：

暴力方法是使用两重循环，时间复杂度为 O(n²)，太慢
可以使用字典记录已经遍历过的数及其下标，用于后续查找
查找另一个数是否存在可以在 O(1) 内完成

详细思路

遍历数组 nums，对每个 num：

记录它对应的“目标补数”：target - num
如果这个补数出现在字典中，说明之前已经见过它，返回它的下标和当前下标
否则，把当前num加入字典：{num: index}

def twoSum(nums, target):
    hashmap = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hashmap:
            return [hashmap[complement], i]
        hashmap[num] = i

复杂度类型	分析
时间复杂度	O(n)，每个元素最多查找和插入一次
空间复杂度	O(n)，需要一个字典存储 n 个元素的映射关系

题目 5：找出数组中出现次数最多的元素（中等）

给你一个整数数组，返回出现次数最多的那个元素。

示例：

输入: nums = [1,1,1,2,2,3]
输出: 1

提示：

用字典统计每个数出现的次数；
然后遍历字典找最大值。

使用什么哈希结构？为什么使用这个？

使用的哈希结构：dict 或 collections.Counter，理由如下：

需要统计每个元素出现的次数
字典（或 Counter）天然就是键值对结构，非常适合做频率统计
统计完之后，在字典中寻找“出现次数最大”的那个键即可

法一：手动统计频率 + 遍历找最大值

def mostFrequent(nums):
    count = {}
    for num in nums:
        count[num] = count.get(num, 0) + 1
        
    max_val = -1
    max_key = None
    for key, val in count.items():
        if val > max_val:
            max_val = val
            max_key = key
            
    return max_key

法二：使用 collections.Counter

from collections import Counter

def mostFrequent(nums):
    freq = Counter(nums)
    return max(freq, key=freq.get)

Counter(nums) 统计频率，freq.get 获取某个键的值，max(..., key=...) 找出最大频率的元素。

复杂度类型	分析
时间复杂度	O(n)，遍历数组 + 遍历字典
空间复杂度	O(n)，需要哈希表存储每个数字的频率

进阶题目

Group Anagrams（字母异位词分组）

给定一个字符串数组 strs，请将所有是字母异位词的字符串放到同一个组中。返回结果可以是任意顺序。

示例：

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["eat","tea","ate"],["tan","nat"],["bat"]]

什么是异位词？

两个单词是异位词（Anagram），当且仅当它们的字母种类和个数完全相同。

哈希表建模思路

我们希望把具有相同特征的字符串分组，这个特征应该满足：

同一个组内的字符串，这个特征必须相同
不同组之间，这个特征一定不同

法一：将字符串排序后作为哈希表的 key

“eat”、”tea”、”ate” → 排序后都是 “aet”，可作为 key；
利用字典把这些字符串分到同一个组里。

from collection import defaultdict

def groupAnagrams(strs):
    anagrams = defaultdict(list)
    for word in strs:
        key = ''.join(sorted(word))   # 把排序后的字符串作为 key
        anagrams[key].append(word)
    return list(anagrams.values())

复杂度类型	分析
时间复杂度	`O(n * klogk)`，n 是字符串数量，k 是字符串平均长度（排序耗时）
空间复杂度	`O(nk)`，所有字符串存储在哈希表中

法二：用字符频率数组作为哈希表的 key

把每个字符串看成26个字母的频率向量（适用于仅包含小写字母的情况）：

例如 "eat" 中：e、a、t 分别出现 1 次；
我们用元组 (1, 0, ..., 1, ..., 1, ..., 0) 来表示它；
相同频率分布的字符串必定是异位词；
这个元组可以作为哈希表的 key，避免了排序操作。