哈希表 (HashMap)

Published: Mon Feb 16 2026 | Modified: Sat Feb 07 2026 , 2 minutes reading.

哈希表：光速查找

算法背后的故事：会瞬间移动的图书馆员

想象一个拥有 1000 万本书的图书馆。在普通的图书馆（比如数组或列表）中，你必须走过每一个书架才能找到一本书。即使是在有序的图书馆（二分查找）中，你仍需检查 24 个书架。

1953 年，H.P. Luhn（同样是哈希函数的鼻祖）提出了一种不同的图书馆方案。在这个图书馆里，书名就是秘密地址。你报出书名《了不起的盖茨比》，套用一个魔术公式，它就会告诉你：“在 429 号书架。”你不需要走路，你直接“瞬间移动”到了 429 号书架。

这就是 哈希表 (Hash Map)。它是现代软件中最重要的基础数据结构，因为它让搜索在实践中变成了瞬时完成（ $O(1)$ 时间）。

为什么需要它？

如果你用过 Python 的 dict、JavaScript 的 Object 或 Java 的 Map，你就是在用哈希表。

数据库索引： 数据库如何在数十亿记录中找到你？它使用哈希索引。
缓存： 当你想保存一个结果（如用户资料）以便下次不用重新获取时，你会把它存入哈希表。
计数： 统计一本书中每个单词出现的频率。

算法是如何“思考”的

这个算法像是一个在键（Key）与内存之间牵线搭桥的媒人。

公式 (哈希)： 它拿到你的键（比如 “Luke”），通过哈希函数将其转化为一个巨大的数字。
地址 (压缩)： 它将那个大数字缩小（通常使用取模 % 运算），以适配其内部存储空间（数组）的大小。
存储： 它将值（Value）放在那个特定的索引位置。
化解冲突： 如果两个不同的键（比如 “Luke” 和 “Sun”）算出了同一个索引怎么办？
- 拉链法 (Chaining)： 在那个位置挂一个小列表，把两人都放进去。
- 开放寻址法： 在附近找下一个空位坐。

工程决策：负载因子

哈希表很快，但它是贪婪的内存消费者。

空间换时间： 为了保持高速，哈希表必须保持大部分空间是空的。如果表太满（即“负载因子”过高），碰撞就会剧增， $O(1)$ 的速度会退化为 $O(N)$ （也就是慢速列表的速度）。
扩容 (Resizing)： 当表装到约 75% 时，它会触发“扩容”——创建一个巨大的新仓库，并重新计算每一个老住户的地址。这是一个沉重的操作，所以如果我们预知数据规模，通常会提前分配足够的空间。

实现参考 (Python)

class SimpleHashMap:
    def __init__(self, size=100):
        self.size = size
        # 使用列表的列表来处理碰撞 (拉链法)
        self.table = [[] for _ in range(self.size)]

    def _hash(self, key):
        # Python 内置的 hash() 函数处理了底层的复杂工作
        return hash(key) % self.size

    def put(self, key, value):
        index = self._hash(key)
        # 如果键已存在，更新它；否则添加新项
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value))

    def get(self, key):
        index = self._hash(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None # 未找到

小结

哈希表教会我们：知识即位置。通过将问题的內容直接转化为答案的地址，我们绕过了“搜索”的必要。它提醒我们，在工程实践中，有时候加速一个流程最简单的方法就是多花一点钱在空间上。

Luke Sun