编辑“︁哈希表原理”︁

{{DISPLAYTITLE:哈希表原理}}

'''哈希表'''（Hash Table）是一种通过键（Key）直接访问值（Value）的高效数据结构，其核心思想是将键通过哈希函数映射到存储位置，从而实现平均时间复杂度为 O(1) 的查找、插入和删除操作。本文将详细介绍其原理、实现、冲突解决策略及实际应用。

== 基本概念 ==
哈希表由以下两部分组成：
* '''哈希函数'''：将任意大小的数据（键）转换为固定大小的整数（哈希值），用于确定存储位置。
* '''存储结构'''：通常是数组或链表，用于存储键值对。

数学表示为：给定键 <math>k</math> 和哈希函数 <math>h</math>，存储位置为 <math>h(k)</math>。

== 哈希函数 ==
哈希函数的设计需满足：
* '''确定性'''：相同键始终产生相同哈希值。
* '''均匀性'''：哈希值应均匀分布，减少冲突。
* '''高效性'''：计算速度快。

常见哈希函数示例（以字符串键为例）：
<syntaxhighlight lang="python">
def hash_function(key, size):
    hash_value = 0
    for char in key:
        hash_value = (hash_value * 31 + ord(char)) % size
    return hash_value
</syntaxhighlight>

== 冲突处理 ==
当不同键映射到同一位置时（即 <math>h(k_1) = h(k_2)</math>），需解决冲突。主要方法有：

=== 链地址法 ===
每个数组位置存储一个链表，冲突的键值对追加到链表中。
<mermaid>
graph LR
    A[数组索引0] --> B[键值对1]
    A --> C[键值对2]
    D[数组索引1] --> E[键值对3]
</mermaid>

=== 开放寻址法 ===
冲突时按规则（如线性探测、二次探测）寻找下一个空闲位置。
<syntaxhighlight lang="python">
def insert(hash_table, key, value):
    index = hash_function(key, len(hash_table))
    while hash_table[index] is not None:
        index = (index + 1) % len(hash_table)  # 线性探测
    hash_table[index] = (key, value)
</syntaxhighlight>

== 性能分析 ==
* '''理想情况'''：O(1) 时间复杂度。
* '''最坏情况'''（所有键冲突）：O(n)。
* '''负载因子'''（<math>\alpha = \frac{\text{元素数}}{\text{表大小}}</math>）影响性能，通常需保持 <math>\alpha < 0.7</math>。

== 代码示例 ==
以下是用Python实现的简单哈希表（链地址法）：
<syntaxhighlight lang="python">
class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def insert(self, key, value):
        index = hash_function(key, self.size)
        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 = hash_function(key, self.size)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

# 示例用法
ht = HashTable(10)
ht.insert("apple", 5)
ht.insert("banana", 7)
print(ht.get("apple"))  # 输出: 5
</syntaxhighlight>

== 实际应用 ==
1. '''数据库索引'''：加速记录查找。
2. '''缓存系统'''（如Redis）：快速键值存取。
3. '''语言解释器'''：变量名到内存地址的映射。
4. '''密码学'''：文件校验（如MD5、SHA-1）。

== 进阶话题 ==
* '''动态扩容'''：当负载因子过高时，重新哈希（Rehashing）以扩大表大小。
* '''完美哈希'''：无冲突的静态哈希表构造方法。
* '''一致性哈希'''：分布式系统中均衡负载的哈希策略。

== 总结 ==
哈希表通过空间换时间的策略实现高效操作，其性能依赖于哈希函数质量和冲突处理策略。理解其原理有助于在需要快速查找的场景中选择合适的数据结构。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:非线性数据结构]]