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

什么是开放地址法？

开放地址法是一种处理哈希冲突的策略。当发生冲突时（即两个键映射到同一个索引），它不会像链地址法那样使用链表存储多个元素，而是继续在哈希表中寻找下一个“空闲”的槽位来存放新元素。

常见的探测方式包括：

• 线性探测：依次检查下一个位置（i+1, i+2, ...）
• 二次探测：使用二次函数跳转（i+1², i+2², ...）
• 双重哈希：使用第二个哈希函数计算步长

Python实现步骤

我们将实现一个支持插入、查找和删除操作的哈希表，使用线性探测作为开放地址策略。

1. 定义哈希表类

首先，我们创建一个类，并初始化必要的属性：

class OpenAddressingHashTable:    def __init__(self, size=10):        self.size = size        # 使用 None 表示空槽，用特殊标记 DELETED 表示已删除        self.keys = [None] * size        self.values = [None] * size        self.DELETED = object()  # 用于标记已删除的位置

2. 实现哈希函数

使用简单的取模运算作为哈希函数：

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

3. 插入操作（put）

当发生冲突时，线性探测下一个位置：

    def put(self, key, value):        index = self._hash(key)        original_index = index        while self.keys[index] is not None:            if self.keys[index] == key:                # 键已存在，更新值                self.values[index] = value                return            if self.keys[index] is self.DELETED:                break            # 线性探测：移动到下一个位置            index = (index + 1) % self.size            if index == original_index:                raise Exception("哈希表已满")        # 找到空位或已删除位置，插入新键值对        self.keys[index] = key        self.values[index] = value

4. 查找操作（get）

    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}' 不存在")

5. 删除操作（delete）

注意：不能简单设为 None，否则会破坏查找路径。应使用 DELETED 标记：

    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}' 不存在")

完整代码与测试

# 完整类定义（略，见上文各部分组合）# 测试代码ht = OpenAddressingHashTable(7)ht.put("apple", 5)ht.put("banana", 3)ht.put("cherry", 8)print(ht.get("apple"))   # 输出: 5print(ht.get("banana"))  # 输出: 3ht.delete("banana")try:    print(ht.get("banana"))except KeyError as e:    print(e)  # 输出: "键 'banana' 不存在"

总结

通过本教程，你已经学会了如何用Python哈希表结合开放地址法来高效管理键值对。这种方法避免了指针开销，适合内存紧凑的场景。同时，我们也深入理解了哈希冲突解决的核心思想。

掌握这个数据结构教程中的内容，不仅能提升你的编程能力，还能为面试和实际项目打下坚实基础。快动手试试吧！