Python实现哈希表：链地址法详解（小白也能看懂的哈希冲突解决方案）

Python 实现步骤

下面我们一步步用 Python 实现一个基于链地址法的哈希表。

1. 定义哈希表类

首先，我们创建一个 HashTable 类，并初始化一个固定大小的桶数组，每个桶初始为空列表。

class HashTable:    def __init__(self, size=10):        self.size = size        # 每个桶是一个列表，用于存储 (key, value) 元组        self.table = [[] for _ in range(self.size)]

2. 实现哈希函数

哈希函数将键转换为索引。这里我们使用 Python 内置的 hash() 函数，并对表大小取模。

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

3. 插入键值对（put 方法）

插入时，先计算哈希值，找到对应桶。然后遍历该桶的链表：如果键已存在，则更新值；否则，追加新键值对。

    def put(self, key, value):        index = self._hash(key)        bucket = self.table[index]                # 检查键是否已存在        for i, (k, v) in enumerate(bucket):            if k == key:                bucket[i] = (key, value)  # 更新值                return                # 键不存在，添加新键值对        bucket.append((key, value))

4. 获取值（get 方法）

获取时同样先定位桶，然后在链表中查找键。

    def get(self, key):        index = self._hash(key)        bucket = self.table[index]                for k, v in bucket:            if k == key:                return v                raise KeyError(f"Key '{key}' not found")

5. 删除键值对（delete 方法）

    def delete(self, key):        index = self._hash(key)        bucket = self.table[index]                for i, (k, v) in enumerate(bucket):            if k == key:                del bucket[i]                return                raise KeyError(f"Key '{key}' not found")

完整代码与测试

class HashTable:    def __init__(self, size=10):        self.size = size        self.table = [[] for _ in range(self.size)]        def _hash(self, key):        return hash(key) % self.size        def put(self, key, value):        index = self._hash(key)        bucket = self.table[index]        for i, (k, v) in enumerate(bucket):            if k == key:                bucket[i] = (key, value)                return        bucket.append((key, value))        def get(self, key):        index = self._hash(key)        bucket = self.table[index]        for k, v in bucket:            if k == key:                return v        raise KeyError(f"Key '{key}' not found")        def delete(self, key):        index = self._hash(key)        bucket = self.table[index]        for i, (k, v) in enumerate(bucket):            if k == key:                del bucket[i]                return        raise KeyError(f"Key '{key}' not found")# 测试示例ht = HashTable()ht.put("apple", 5)ht.put("banana", 3)ht.put("cherry", 8)print(ht.get("apple"))   # 输出: 5print(ht.get("banana"))  # 输出: 3ht.put("apple", 10)      # 更新 apple 的值print(ht.get("apple"))   # 输出: 10ht.delete("banana")# print(ht.get("banana"))  # 抛出 KeyError

总结

通过本教程，你已经学会了如何用链地址法在 Python 中实现一个简单的哈希表。这种方法有效解决了哈希冲突问题，是理解更高级数据结构（如字典底层原理）的重要基础。

记住，Python哈希表的性能取决于哈希函数的质量和负载因子（元素数量 / 表大小）。在实际应用中，可能需要动态扩容以保持效率。

希望这篇关于Python数据结构的教程对你有帮助！动手试试吧，编程最好的老师就是实践。