哈希表：为什么 Redis、Python 字典都靠它"秒查"

打开 Python 解释器，输入 a = {}; a["name"]="必学必会"，这一句赋值背后是一张哈希表。Redis 的几十种数据结构底层、几乎所有数据库的索引，也都依赖它。它的招牌能力是：无论存了多少数据，查找平均只要一步。

原理并不神秘。哈希表先用一个哈希函数把"键"（如字符串 "name"）变成一个数字，再对桶数组长度取模，定位到某个"桶"。下次查 "name"，走同样的公式，直接跳到那个桶——不需要从头翻，所以平均 O(1)。这正是它与数组（靠下标）不同的地方：键可以是任意对象，而不仅仅是整数序号。

麻烦出在冲突：不同的键可能被算到同一个桶。经典解法有两种——链地址法（同一个桶挂一条链表，放所有冲突键）和开放寻址法（冲突了就按规则找下一个空桶）。只要哈希函数设计得当、负载因子不高，冲突很少，查找依然接近 O(1)。

但哈希表也有软肋：最坏情况会退化到 O(n)（所有键撞进同一桶），而且它不支持"找出比 x 大的所有键"这类有序查询——那是树结构的活。所以工程里常是"哈希表 + 树/B+树"搭配使用。理解这点，你就明白为什么数据库既用哈希做点查、又用 B+ 树做范围扫描。

哈希表是必学必会算法轨道里已覆盖的节点（C4），但它在工程中的威力值得单独一篇文章来讲——因为它最能体现"选对数据结构，算法自然快"。

关联推荐

• GPT-5.6 递归自我改进 — 哈希与递归虽不同路，都是"让计算可行"的基石
• （本批「算法与问题求解入门」KU 发布后回填互链）