编辑“︁碰撞解决策略”︁（章节）

== 碰撞解决策略 ==

'''碰撞解决策略'''是哈希表实现中的核心技术，用于处理当不同键（key）通过哈希函数映射到同一哈希桶（bucket）时产生的冲突。本条目将系统讲解常见的碰撞处理方法、实现细节及实际应用场景。

=== 基本概念 ===
哈希表通过哈希函数将键转换为数组索引以实现快速查找，但哈希函数的输出空间通常小于输入空间，因此碰撞（Collision）不可避免。碰撞解决策略分为两大类：

* '''开放寻址法'''（Open Addressing）：所有元素均存储在哈希表数组内，通过探测（Probing）寻找空桶。
* '''链地址法'''（Separate Chaining）：每个桶维护一个链表或其他数据结构存储冲突元素。

=== 开放寻址法 ===
开放寻址法的核心思想是当碰撞发生时，按预定规则寻找下一个可用桶。常见探测方法包括：

==== 线性探测 ====
公式：<math>h(k, i) = (h'(k) + i) \mod m</math>，其中<math>h'(k)</math>为初始哈希函数，<math>i</math>为探测次数，<math>m</math>为表大小。

'''示例代码（Python）'''：
<syntaxhighlight lang="python">
class LinearProbingHashTable:
    def __init__(self, size):
        self.size = size
        self.keys = [None] * size
        self.values = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        while self.keys[index] is not None:
            if self.keys[index] == key:  # 键已存在则更新值
                self.values[index] = value
                return
            index = (index + 1) % self.size  # 线性探测
        self.keys[index] = key
        self.values[index] = value

# 示例使用
ht = LinearProbingHashTable(10)
ht.insert("apple", 5)
ht.insert("banana", 7)
ht.insert("apple", 10)  # 更新已存在的键
</syntaxhighlight>

==== 二次探测 ====
公式：<math>h(k, i) = (h'(k) + c_1i + c_2i^2) \mod m</math>，减少线性探测的聚集现象。

=== 链地址法 ===
每个桶存储一个链表，冲突元素直接追加到链表末尾。查找时需要遍历链表。

'''时间复杂度对比'''：
* 平均情况：<math>O(1)</math>（负载因子合理时）
* 最坏情况：<math>O(n)</math>（所有键碰撞）

<mermaid>
graph LR
    A[哈希表] --> B[桶0: 链表]
    A --> C[桶1: 链表]
    A --> D[...]
    B --> E[元素A]
    B --> F[元素B]
    C --> G[元素C]
</mermaid>

'''示例代码（Java）'''：
<syntaxhighlight lang="java">
import java.util.LinkedList;

class ChainingHashTable {
    private LinkedList<Entry>[] table;
    private int size;

    class Entry {
        String key;
        int value;
        Entry(String key, int value) { this.key = key; this.value = value; }
    }

    public ChainingHashTable(int size) {
        this.size = size;
        table = new LinkedList[size];
        for (int i = 0; i < size; i++) {
            table[i] = new LinkedList<>();
        }
    }

    private int hashFunction(String key) {
        return key.hashCode() % size;
    }

    public void insert(String key, int value) {
        int index = hashFunction(key);
        for (Entry entry : table[index]) {
            if (entry.key.equals(key)) {
                entry.value = value; // 更新现有键
                return;
            }
        }
        table[index].add(new Entry(key, value));
    }
}
</syntaxhighlight>

=== 实际应用案例 ===
1. '''数据库索引'''：PostgreSQL使用链地址法实现哈希索引。
2. '''缓存系统'''：Memcached采用开放寻址法处理键冲突。
3. '''编译器符号表'''：快速查找变量定义时常用二次探测。

=== 性能优化策略 ===
* '''再哈希（Rehashing）'''：当负载因子超过阈值时，扩大哈希表并重新插入所有元素。
* '''布谷鸟哈希（Cuckoo Hashing）'''：使用多个哈希函数减少探测长度。
* '''罗宾汉哈希（Robin Hood Hashing）'''：平衡探测距离提升查询效率。

=== 数学分析 ===
成功查找的平均探测次数：
* 线性探测：<math>\frac{1}{2}\left(1+\frac{1}{1-\alpha}\right)</math>
* 链地址法：<math>1+\frac{\alpha}{2}</math>
其中<math>\alpha</math>为负载因子（元素数/桶数）。

=== 总结 ===
选择碰撞解决策略需权衡：
* 开放寻址法：内存紧凑但对负载因子敏感
* 链地址法：实现简单但需要额外指针空间

实际系统中常根据数据特征和性能需求混合使用多种策略。

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