哈希表

哈希表的本质

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

散列函数

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

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

# 取模法（最简单的散列函数）
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)