Python开放地址法详解（手把手教你用Python实现哈希表冲突解决）

什么是开放地址法？

开放地址法 是一种解决哈希冲突的策略。当发生冲突时（即两个不同的键被哈希到同一个位置），它不会使用链表或其他结构来存储多个元素，而是继续在哈希表中寻找下一个“空闲”的槽位来存放新元素。

常见的开放地址法包括：

• 线性探测（Linear Probing）
• 二次探测（Quadratic Probing）
• 双重哈希（Double Hashing）

本文将以最简单的 线性探测 为例进行实现。

Python实现开放地址法哈希表

我们将创建一个 OpenAddressingHashTable 类，支持插入（put）、查找（get）和删除（delete）操作。

class OpenAddressingHashTable:    def __init__(self, size=10):        self.size = size        # 使用 None 表示空槽，用特殊标记 DELETED 表示已删除        self.keys = [None] * size        self.values = [None] * size        self.DELETED = object()  # 用于标记已删除的位置    def _hash(self, key):        """简单的哈希函数：取模"""        return hash(key) % self.size    def _probe(self, key):        """线性探测：从哈希位置开始，逐个检查直到找到空位或匹配键"""        index = self._hash(key)        original_index = index        while self.keys[index] is not None:            if self.keys[index] == key:                return index  # 找到已有键            if self.keys[index] is self.DELETED:                # 虽然被删除，但需继续探测（因为可能后面还有相同键）                pass            index = (index + 1) % self.size            if index == original_index:                raise Exception("Hash table is full")        return index  # 返回第一个可用位置    def put(self, key, value):        """插入键值对"""        index = self._probe(key)        self.keys[index] = key        self.values[index] = value    def get(self, key):        """根据键获取值"""        index = self._hash(key)        original_index = index        while self.keys[index] is not None:            if self.keys[index] == key:                return self.values[index]            index = (index + 1) % self.size            if index == original_index:                break  # 已遍历完整个表        raise KeyError(f"Key '{key}' not found")    def delete(self, key):        """删除键值对（懒删除）"""        index = self._hash(key)        original_index = index        while self.keys[index] is not None:            if self.keys[index] == key:                self.keys[index] = self.DELETED                self.values[index] = None                return            index = (index + 1) % self.size            if index == original_index:                break        raise KeyError(f"Key '{key}' not found")

代码说明

- _hash 方法使用 Python 内置的 hash() 函数，并对表大小取模，得到初始索引。

- _probe 方法实现线性探测逻辑：如果当前位置已被占用且不是目标键，则向后移动一位（循环）。

- 删除操作采用“懒删除”策略：不真正移除元素，而是用 DELETED 标记。这样可以避免破坏探测链，确保后续查找仍能正常工作。

使用示例

# 创建哈希表ht = OpenAddressingHashTable(size=7)# 插入数据ht.put("apple", 5)ht.put("banana", 3)ht.put("cherry", 8)# 获取数据print(ht.get("apple"))   # 输出: 5# 删除数据ht.delete("banana")# 再次获取（会报错）try:    print(ht.get("banana"))except KeyError as e:    print(e)  # 输出: "Key 'banana' not found"

为什么学习开放地址法？

掌握 Python开放地址法 不仅有助于你深入理解哈希表的工作原理，还能提升你在面试或实际项目中处理数据结构问题的能力。相比链地址法，开放地址法在内存局部性上表现更好，适合缓存友好的场景。

此外，像 Python 的内置字典（dict）在 CPython 中就使用了类似开放寻址的优化策略（自 Python 3.6 起），因此学习这一方法也让你更贴近语言底层实现。

总结

通过本教程，你已经学会了如何用 Python 实现基于 开放地址法 的哈希表。我们重点讲解了线性探测、懒删除等核心概念，并提供了完整的可运行代码。

希望这篇 开放寻址法教程 能帮助你打下坚实的数据结构基础。如果你对 Python哈希实现 感兴趣，不妨尝试扩展这个类，加入二次探测或动态扩容功能！

关键词回顾：Python开放地址法、哈希表冲突解决、Python哈希实现、开放寻址法教程。