哈希表

哈希表的本质

哈希表（Hash Table）在平均情况下实现 O(1) 的查找、插入和删除。其核心思路是：通过一个散列函数，将键（Key）映射到数组的某个下标，然后直接访问该位置——本质上是"把搜索问题转化为数组访问问题"。

• 散列函数（Hash Function） 将任意键映射到固定范围整数下标的函数。好的散列函数应做到：确定性（相同输入总返回相同结果）、均匀分布（减少碰撞）、高效计算（不能比O(1)慢太多）。
• 哈希碰撞（Hash Collision） 两个不同的键映射到同一个数组下标的情况。碰撞不可完全避免（鸽巢原理），但可以通过好的散列函数减少频率，并通过冲突解决策略安全处理。
• 负载因子（Load Factor） 已存元素数 / 桶总数。负载因子越高，碰撞越频繁，性能退化越严重。Python dict 的阈值约 2/3，超过时触发 rehash（重新散列）。
• 链地址法（Separate Chaining） 每个桶维护一个链表（或其他容器），碰撞的元素都挂在同一桶的链表上。实现简单，负载因子可超过 1，但链表访问缓存不友好。Java HashMap 采用此策略（链表 + 红黑树）。
• 开放地址法（Open Addressing） 碰撞时在数组中按规则探测下一个空位（线性探测/二次探测/双重哈希）。内存紧凑、缓存友好，但负载因子不能太高，删除操作需要 tombstone 标记。Python dict（3.6+）和 Swift 采用此策略。

散列函数

一个好的散列函数需要满足：

• 确定性：相同的键始终映射到相同的位置
• 均匀分布：尽量将键均匀散布到所有桶，减少碰撞
• 高效计算：散列函数本身不能太慢

# 取模法（最简单的散列函数）
def hash_int(key: int, size: int) -> int:
    return key % size

# 字符串散列（多项式滚动哈希）
def hash_str(s: str, size: int) -> int:
    h = 0
    BASE = 31      # 选一个质数作为基数
    MOD = 10**9 + 7
    for ch in s:
        h = (h * BASE + ord(ch)) % MOD
    return h % size

# Python 内置 hash() 函数使用 SipHash 算法（带随机种子，防止哈希攻击）
print(hash("hello"))   # 每次运行结果不同（随机种子）

冲突解决

当两个不同的键散列到同一个位置时，称为哈希冲突。有两种主要解决方案：

链地址法（拉链法）

每个桶维护一个链表（或其他容器），冲突的元素都挂在同一桶的链表上。

class HashMapChaining:
    def __init__(self, size=16):
        self.size = size
        self.buckets = [[] for _ in range(size)]  # 每个桶是一个列表

    def _hash(self, key):
        return hash(key) % self.size

    def put(self, key, val):
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[idx]):
            if k == key:
                self.buckets[idx][i] = (key, val)  # 更新
                return
        self.buckets[idx].append((key, val))  # 追加到链表

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        return None

开放地址法（线性探测）

发生冲突时，在数组中按某种规则寻找下一个空位。

class HashMapLinearProbe:
    def __init__(self, size=16):
        self.size = size
        self.keys = [None] * size
        self.vals = [None] * size

    def _hash(self, key):
        return hash(key) % self.size

    def put(self, key, val):
        idx = self._hash(key)
        while self.keys[idx] is not None:
            if self.keys[idx] == key:
                self.vals[idx] = val   # 更新
                return
            idx = (idx + 1) % self.size   # 线性探测：找下一个位置
        self.keys[idx] = key
        self.vals[idx] = val

负载因子与扩容

负载因子（Load Factor）= 已存元素数 / 桶总数。负载因子过高会导致冲突增多，性能退化。

# Python dict 的负载因子阈值约为 2/3（0.667）
# 超过阈值时触发 rehash：申请约 2 倍空间，重新散列所有元素

# 验证 Python dict 扩容时机
import sys
d = {}
prev_size = sys.getsizeof(d)
for i in range(100):
    d[i] = i
    curr = sys.getsizeof(d)
    if curr != prev_size:
        print(f"扩容于第 {i+1} 个元素，内存: {prev_size} → {curr}")
        prev_size = curr

常见应用模式

频率统计

from collections import Counter

# 统计字符频率
s = "hello world"
freq = Counter(s)
print(freq.most_common(3))  # [('l', 3), ('o', 2), ('h', 1)]

# 手动实现
def count_freq(nums):
    freq = {}
    for x in nums:
        freq[x] = freq.get(x, 0) + 1
    return freq

字母异位词分组

from collections import defaultdict

def group_anagrams(strs: list) -> list:
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))   # 排序后作为哈希键
        groups[key].append(s)
    return list(groups.values())

# 示例
print(group_anagrams(["eat","tea","tan","ate","nat","bat"]))
# [["eat","tea","ate"], ["tan","nat"], ["bat"]]

最长连续序列（O(n) 解法）

def longest_consecutive(nums: list) -> int:
    num_set = set(nums)   # O(n) 建集合
    max_len = 0

    for x in num_set:
        # 只从序列起点开始计数（x-1 不在集合中）
        if x - 1 not in num_set:
            length = 1
            while x + length in num_set:
                length += 1
            max_len = max(max_len, length)

    return max_len
# 时间 O(n)：虽有双层循环，但每个数最多被访问两次

HashSet vs HashMap

s = {1, 2, 3}
2 in s       # O(1)
s.add(4)     # O(1)
s.remove(1)  # O(1)

d = {'a': 1}
d['b'] = 2    # O(1)
d.get('a')   # O(1)
del d['a']  # O(1)

Two Sum 模式：哈希表的核心应用

两数之和是最典型的哈希表应用：把"已见过的值"存入哈希表，将 O(n²) 的暴力查找降为 O(n)。

def two_sum(nums: list, target: int) -> list:
    seen = {}   # {值: 下标}
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]  # 找到配对
        seen[x] = i   # 记录当前值的下标
    return []
# 时间 O(n)，空间 O(n)  — 对比暴力 O(n²)

哈希表的高级应用

滑动窗口 + 哈希：最长不重复子串

def length_of_longest_substring(s: str) -> int:
    # 哈希表记录每个字符最后出现的下标
    char_index = {}
    max_len = 0
    left = 0   # 窗口左边界

    for right, ch in enumerate(s):
        if ch in char_index and char_index[ch] >= left:
            # 字符重复，将左边界移到重复字符右侧
            left = char_index[ch] + 1
        char_index[ch] = right   # 更新字符最新位置
        max_len = max(max_len, right - left + 1)

    return max_len
# 时间 O(n)，空间 O(字符集大小)

子数组和等于 K（前缀和 + 哈希）

def subarray_sum(nums: list, k: int) -> int:
    # prefix_sum[i..j] = prefix[j+1] - prefix[i]
    # 求 prefix[j+1] - k = prefix[i] 的对数 → 哈希记录前缀和频率
    count = 0
    prefix = 0
    freq = {0: 1}   # 空子数组的前缀和为 0，出现 1 次

    for x in nums:
        prefix += x
        # 查找有多少个前缀 prefix[i] 使得 prefix - prefix[i] = k
        count += freq.get(prefix - k, 0)
        freq[prefix] = freq.get(prefix, 0) + 1

    return count
# 时间 O(n)，空间 O(n)  — 关键洞察：把"找连续子数组和"转化为"找两个前缀和之差"