哈希表 Hash

数据结构 · 用散列函数把键直接算成下标

什么是哈希表

前面找一个元素，要么靠下标、要么顺着指针走。哈希表换了个思路——靠算：把键丢进一个散列函数，算出一个桶下标，直接跳过去存或取，平均只要 O(1)，不用比较、不用遍历。

这里用最简单的散列 hash(key) = key % 7（7 个桶）。但麻烦来了：两个不同的键可能算出同一个桶——这叫哈希冲突。拉链法的办法是：每个桶挂一条链，冲突的键就追加到链尾。输入一个数试试插入或查找。

看见了吗——插入 11：11 % 7 = 4，跳到 4 号桶；如果桶里已经有元素，就挂到链尾（冲突）。查找也一样：先算出桶号直达，再沿那条链比较。只要散列均匀、链都很短，存取就接近 O(1)；但如果都挤进一个桶、链很长，就退化成 O(n)——所以好的散列函数和合适的桶数很关键。

另一种解冲突：开放寻址

拉链法把冲突的键挂到桶外的链上。还有一条完全不同的路——开放寻址：不挂链，所有键都住在同一张扁平数组里。冲突了怎么办？就在表内往后探一格，找到第一个空位坐下。这种「撞了就顺位往后找」的探测方式叫线性探测。

还是 hash(key) = key % 7、还是那 4 个键 [15, 8, 23, 4]，这次散进 7 格扁平表：15 去 1 号；8 也想去 1 号但被占了 → 探到 2 号；23 想去 2 号又被占 → 探到 3 号；4 去 4 号。冲突的键在表里挤成一簇（这叫聚集）——这正是开放寻址要付的代价。试试插入、查找。

查找也顺着同样的路探：从 hash 算出的「家」开始往后比，命中就停，探到空位就说明不在表中。右下角的装载因子（已用格数 ÷ 总格数）是开放寻址的命脉：它越接近 1，聚集越严重、探测链越长；一旦满了就再也插不进，必须扩容——开一张更大的表、把所有键重新散列（rehash）搬过去。所以实战里通常装载因子超过约 0.7 就提前扩容。

两种解冲突各有所长：拉链法实现简单、还能装下超过表长的元素；开放寻址数据都在一张表里、对 CPU 缓存友好。Java 的 HashMap 用拉链法，Python 的 dict、Go 的 map 则用开放寻址——没有银弹，看取舍。

哈希表在哪里用

只剩最后一种、也是最一般的结构了——图：顶点和边的任意连接。