编辑“︁哈希表”︁

{{DISPLAYTITLE:哈希表}}

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

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

=== 数学表示 ===
哈希函数可表示为：
<math>h: K \rightarrow \{0, 1, \dots, m-1\}</math>
其中<math>K</math>是键的集合，<math>m</math>是哈希表的大小。

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

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

<mermaid>
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
</mermaid>

== 冲突处理策略 ==
=== 链地址法（Separate Chaining） ===
每个哈希桶维护一个链表，冲突元素追加到链表末尾。

<syntaxhighlight lang="python">
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  # 未找到
</syntaxhighlight>

'''输入输出示例：'''
<syntaxhighlight lang="python">
ht = HashTable(10)
ht.insert("apple", 5)
ht.insert("banana", 7)
print(ht.get("apple"))  # 输出: 5
print(ht.get("orange")) # 输出: None
</syntaxhighlight>

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

<syntaxhighlight lang="python">
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
</syntaxhighlight>

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

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

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

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

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:数据结构基础]]