编辑“︁哈希表”︁（章节）

== 冲突处理策略 ==
=== 链地址法（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>