哈希表

哈希表（Hash Table）是一种通过键（Key）直接访问值（Value）的高效数据结构，其核心思想是利用哈希函数将键映射到存储位置（称为哈希桶或槽位），从而实现平均时间复杂度为$O(1)$的查找、插入和删除操作。

基本概念

哈希表由以下关键组件构成：

• 键（Key）：用于索引数据的唯一标识符。
• 值（Value）：与键关联的实际数据。
• 哈希函数（Hash Function）：将键转换为整数（哈希值），决定数据存储位置。
• 哈希桶（Bucket）：存储键值对的容器，通常是一个数组。
• 冲突处理（Collision Resolution）：当不同键映射到同一位置时，解决冲突的策略（如链地址法、开放寻址法）。

数学表示

哈希函数可表示为： $h:K\to \{0,1,\dots ,m-1\}$ 其中$K$是键的集合，$m$是哈希表的大小。

工作原理

插入操作

1. 计算键的哈希值：hash = hash_function(key) 2. 确定存储位置：index = hash % table_size 3. 若发生冲突，按策略处理（如链地址法中添加到链表）。 4. 存储键值对。

查找操作

1. 计算键的哈希值。 2. 定位到对应哈希桶。 3. 若存在冲突，遍历冲突元素（如链表）直到匹配键。

graph TD A[输入Key] --> B[计算哈希值h(key)] B --> C[定位到桶h(key) mod m] C --> D{桶是否为空?} D -->|是| E[返回未找到] D -->|否| F[遍历桶内元素] F --> G{匹配Key?} G -->|是| H[返回Value] G -->|否| I[继续遍历] I --> J{遍历结束?} J -->|是| E

冲突处理策略

链地址法（Separate Chaining）

每个哈希桶维护一个链表，冲突元素追加到链表末尾。

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]  # 每个桶初始化为空列表

    def insert(self, key, value):
        hash_key = hash(key) % self.size
        bucket = self.table[hash_key]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # 更新已存在的键
                return
        bucket.append((key, value))  # 添加新键值对

    def get(self, key):
        hash_key = hash(key) % self.size
        bucket = self.table[hash_key]
        for k, v in bucket:
            if k == key:
                return v
        return None  # 未找到

输入输出示例：

ht = HashTable(10)
ht.insert("apple", 5)
ht.insert("banana", 7)
print(ht.get("apple"))  # 输出: 5
print(ht.get("orange")) # 输出: None

开放寻址法（Open Addressing）

所有元素直接存储在数组中，冲突时按探测序列（如线性探测、二次探测）寻找下一个空槽。

class OpenAddressingHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def insert(self, key, value):
        for i in range(self.size):
            hash_key = (hash(key) + i) % self.size  # 线性探测
            if self.table[hash_key] is None:
                self.table[hash_key] = (key, value)
                return
        raise Exception("哈希表已满")

    def get(self, key):
        for i in range(self.size):
            hash_key = (hash(key) + i) % self.size
            if self.table[hash_key] is None:
                return None
            k, v = self.table[hash_key]
            if k == key:
                return v
        return None

实际应用案例

• 字典实现：Python的dict、Java的HashMap均基于哈希表。
• 缓存系统：如Redis使用哈希表存储键值对。
• 数据库索引：加速记录查找。
• 去重：检测重复元素（如统计单词频率）。

性能分析

• 理想情况：哈希函数均匀分布键，操作时间复杂度为$O(1)$。
• 最坏情况：所有键冲突，退化为链表（链地址法），时间复杂度$O(n)$。
• 负载因子（Load Factor）：$\alpha =\frac{n}{m}$（$n$为元素数，$m$为桶数）。通常当$\alpha >0.7$时需扩容。

常见问题

• 哈希函数设计：应尽量减少冲突（如MurmurHash、SHA系列）。
• 动态扩容：重新哈希（Rehashing）时需重新计算所有键的位置。
• 不可变键：Python中列表不可作为键，因其哈希值可变。

进阶话题

• 一致性哈希：用于分布式系统均衡负载。
• 布谷鸟哈希（Cuckoo Hashing）：使用多个哈希函数减少冲突。
• 完美哈希：无冲突的静态哈希表构造方法。