Python链式哈希表详解（从零开始实现链地址法哈希表）

什么是链式哈希表？

链式哈希表使用一个数组（称为“桶”或“buckets”）来存储数据。每个桶实际上是一个链表（或其他容器），用于存放所有哈希到该索引的键值对。当发生冲突时，新元素会被添加到对应桶的链表末尾。

步骤一：定义节点类

首先，我们需要一个简单的节点类来表示链表中的每个元素：

class ListNode:    def __init__(self, key, value):        self.key = key        self.value = value        self.next = None

步骤二：实现链式哈希表类

接下来，我们创建主类 ChainedHashTable，并实现核心方法：put（插入）、get（查找）、remove（删除）以及哈希函数。

class ChainedHashTable:    def __init__(self, initial_capacity=16):        self.capacity = initial_capacity        self.size = 0        self.buckets = [None] * self.capacity    def _hash(self, key):        """简单的哈希函数：使用内置 hash() 并取模"""        return hash(key) % self.capacity    def put(self, key, value):        """插入或更新键值对"""        index = self._hash(key)        head = self.buckets[index]        # 检查是否已存在该 key        current = head        while current:            if current.key == key:                current.value = value  # 更新值                return            current = current.next        # 不存在则插入新节点到头部        new_node = ListNode(key, value)        new_node.next = head        self.buckets[index] = new_node        self.size += 1    def get(self, key):        """根据 key 获取 value，若不存在返回 None"""        index = self._hash(key)        current = self.buckets[index]        while current:            if current.key == key:                return current.value            current = current.next        return None    def remove(self, key):        """删除指定 key 的键值对"""        index = self._hash(key)        current = self.buckets[index]        prev = None        while current:            if current.key == key:                if prev:                    prev.next = current.next                else:                    self.buckets[index] = current.next                self.size -= 1                return True            prev = current            current = current.next        return False

步骤三：测试你的哈希表

现在，让我们写一段测试代码，验证我们的实现是否正确：

# 创建哈希表实例ht = ChainedHashTable()# 插入数据ht.put("apple", 5)ht.put("banana", 3)ht.put("cherry", 7)# 查找数据print(ht.get("apple"))   # 输出: 5print(ht.get("grape"))   # 输出: None# 更新数据ht.put("apple", 10)print(ht.get("apple"))   # 输出: 10# 删除数据ht.remove("banana")print(ht.get("banana"))  # 输出: None

进阶优化：动态扩容

为了保持高效性能，当负载因子（load factor = size / capacity）过高时（例如 > 0.75），我们可以自动扩容并重新哈希所有元素。这属于高级话题，但值得了解。你可以在此基础上扩展 put 方法，在插入后检查负载因子并触发 _resize() 函数。

总结

通过本教程，你已经掌握了如何用 Python 实现一个基础但功能完整的链式哈希表。这种数据结构在实际开发中应用广泛，例如 Python 内置的 dict 就采用了类似的原理（虽然更复杂）。理解 链地址法哈希 不仅有助于面试，还能加深你对底层数据结构的认识。

记住，学习 Python数据结构 是提升编程能力的关键一步。动手实践这个哈希表实现，你会对哈希冲突、时间复杂度和内存管理有更直观的理解！

关键词回顾：Python链式哈希表、哈希表实现、Python数据结构、链地址法哈希。