🧮 哈希表 (Hash Table)

难度 / Difficulty: 中等 (Medium)
分类 / Category: 数据结构 (Data Structure)
时间复杂度 / Time Complexity: 平均 O(1)，最坏 O(n)
空间复杂度 / Space Complexity: O(n)

📖 算法简介 / Introduction

哈希表是一种通过哈希函数将键（Key）映射到数组索引位置的数据结构。在理想情况下，查找、插入和删除操作的时间复杂度都是 O(1)。

A hash table is a data structure that maps keys to array indices via a hash function. In the ideal case, lookup, insert, and delete operations all run in O(1) time.

核心思想：用空间换时间 — 通过哈希函数直接计算出元素存储位置，实现常数时间访问。

💡 算法原理 / Principle

哈希函数

将任意大小的键转换为数组索引的函数。一个好的哈希函数应该：

• 计算速度快
• 使键均匀分布在数组中
• 尽量避免冲突

def hash(key, table_size):
    return hash(key) % table_size

冲突处理

当两个不同的键映射到相同位置时，称为冲突（Collision）。常用处理方法：

1. 链地址法（Separate Chaining）：每个位置存储一个链表
2. 开放地址法（Open Addressing）：探测下一个空位
   • 线性探测：逐个向后找
   • 二次探测：使用二次方程确定步长
   • 双重哈希：使用第二个哈希函数确定步长

📝 代码实现 / Implementation

链地址法实现

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        index = self._hash(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value))
    
    def get(self, key):
        index = self._hash(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None
    
    def delete(self, key):
        index = self._hash(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                del self.table[index][i]
                return True
        return False

✨ 示例 / Example

哈希表大小: 10
插入: ("name", "Alice"), ("age", 25), ("city", "Beijing")

Step 1: hash("name") = hash("name") % 10 = 3
Step 2: hash("age") = hash("age") % 10 = 5
Step 3: hash("city") = hash("city") % 10 = 7

结果:
Index 3: [("name", "Alice")]
Index 5: [("age", 25)]
Index 7: [("city", "Beijing")]

🎯 适用场景 / Scenarios

• 快速查找 — 数据库索引、缓存系统
• 去重 — 记录已处理的数据
• 键值对存储 — 字典、映射、配置管理
• 集合运算 — 求交集、并集等

Fast lookups (database indexing, caching), Deduplication, Key-value storage (dictionaries, configs), Set operations.

⚠️ 优缺点 / Pros & Cons

🔄 与其他数据结构对比 / Comparison