哈希表实现入门：用 Python 手写一个基础版本

哈希表是一种高效的数据结构，广泛应用于编程中，它能实现快速的键值对存储和检索。核心思想是通过哈希函数将键映射到数组索引，从而在常数时间内完成操作。本文将一步步教你用 Python 手写一个基础版本的哈希表，涵盖哈希函数设计、冲突解决和基本操作实现。整个过程简单易懂，适合初学者。

什么是哈希表？

哈希表（Hash Table）基于键值对存储数据。键（key）通过哈希函数转换为索引，指向存储位置（称为桶）。理想情况下，每个键映射到唯一索引，但实际中常出现冲突（多个键映射到同一位置），需要特殊处理。例如，给定键 $k$，哈希函数 $h(k)$ 计算索引： $$h(k) = k \mod m$$ 其中 $m$ 是表的大小。这确保了索引在 $0$ 到 $m-1$ 范围内。

冲突解决：链地址法

当多个键映射到同一索引时，称为哈希冲突。常见解决方法是链地址法（Chaining），即每个桶存储一个链表。插入新元素时，添加到对应链表中；查找时遍历链表。这种方法简单可靠，适合基础实现。

Python 实现基础哈希表

下面我们手写一个 Python 类 HashTable，实现插入、查找和删除操作。使用链地址法处理冲突，表大小设为 10（可调整）。代码中，每个桶是一个链表（用 Python 列表模拟），哈希函数基于键的哈希值取模。

class HashTable:
    def __init__(self, size=10):
        """初始化哈希表，设置表大小和桶列表。"""
        self.size = size
        self.buckets = [[] for _ in range(size)]  # 每个桶初始化为空列表
    
    def hash_function(self, key):
        """计算键的哈希值并取模，返回索引。"""
        return hash(key) % self.size  # 使用Python内置hash函数确保通用性
    
    def insert(self, key, value):
        """插入键值对：计算索引，添加到对应链表中。"""
        index = self.hash_function(key)
        bucket = self.buckets[index]
        # 遍历链表，检查键是否已存在（更新值）
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # 键存在则更新
                return
        bucket.append((key, value))  # 键不存在则添加新元素
    
    def search(self, key):
        """查找键的值：计算索引，遍历链表。"""
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v  # 找到则返回值
        return None  # 未找到返回None
    
    def delete(self, key):
        """删除键值对：计算索引，移除链表中的元素。"""
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]  # 删除元素
                return True  # 成功删除
        return False  # 键不存在

如何使用哈希表

以下示例演示如何创建哈希表、插入数据、查找和删除值。代码简单明了，便于测试和扩展。

# 创建哈希表实例
ht = HashTable()

# 插入键值对
ht.insert("name", "Alice")
ht.insert("age", 30)
ht.insert("city", "Beijing")

# 查找值
print(ht.search("name"))  # 输出: Alice
print(ht.search("age"))   # 输出: 30

# 删除键值对
ht.delete("city")
print(ht.search("city"))  # 输出: None

# 处理冲突示例：插入相同索引的键
ht.insert("a", 1)
ht.insert("k", 2)  # 假设"a"和"k"映射到同一索引，通过链表处理
print(ht.search("k"))     # 输出: 2

总结

通过这个基础实现，你学会了哈希表的核心机制：哈希函数（如 $h(k) = \text{hash}(k) \mod m$）和链地址法冲突处理。代码简洁，易于理解，但实际应用中可扩展（如动态调整表大小）。哈希表在数据存储中表现优秀，是学习数据结构的绝佳起点。动手试试吧，进一步探索优化方法！