简介
哈希表(hash table),又称散列表,它通过建立键 key 与值 value 之间的映射,实现高
效的元素查询。具体而言,我们向哈希表中输入一个键 key ,可以在 O(1)
时间内获取对
应的值 value 。
比如下图中我们建立了学号(key)到姓名(value)的映射,得到一个哈希表:
理论上在哈希表上进行增删查改的时间复杂度都是 O(1)
,非常高效:
数组 | 链表 | 哈希表 | |
---|---|---|---|
查找元素 | O(n) | O(n) | O(1) |
添加元素 | O(1) | O(1) | O(1) |
删除元素 | O(n) | O(n) | O(1) |
实现
我们先考虑最简单的情况,仅用一个数组来实现哈希表。在哈希表中,我们将数组中的每个 空位称为桶(bucket),每个桶可存储一个键值对。因此,查询操作就是找到 key 对应的 桶,并在桶中获取 value 。
那么,如何基于 key 定位对应的桶呢?这是通过哈希函数(hash function,又称散列函数) 实现的。 哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。 在哈希表 中,输入空间是所有 key ,输出空间是所有桶(数组索引)。换句话说,输入一个 key , 我们可以通过哈希函数得到该 key 对应的键值对在数组中的存储位置。
哈希函数有多种实现方式,我们以简单的实现为例:
- 通过某种哈希算法
hash()
计算得到哈希值; - 将哈希值对桶数量(数组长度)capacity 取模,从而获取该 key 对应的数组索引 index 。
![](/ox-hugo/_20240718_093017screenshot.png” caption=“<span class=“figure-number”>Figure 1: 通过哈希函数计算索引的过程)
TODO 哈希冲突
从本质上看,哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输 出空间,而输入空间往往远大于输出空间。因此, 理论上一定存在“多个输入对应相同输出”的 情况。
比如下图中的两个不同的 key,经过哈希函数计算后得到相同的索引 36,即出现哈希冲突:
解决哈希冲突最直接的方法就是对哈希表扩容,输出空间的容量越大,不同输入被分配到同 一个输出的概率就越小。
![](/ox-hugo/_20240718_224648screenshot.png” caption=“<span class=“figure-number”>Figure 2: 通过扩容哈希表解决哈希冲突)
哈希表的底层结构也是基于数组实现,要扩容哈希表就和扩容数组一样,需要迁移原来的数 据,而且哈希表需要通过哈希函数重新计算数据的存储位置,所以要避免频繁扩容来增加计 算开销。
哈希表中有一个重要概念叫负载因子(load factor), 其定义为哈希表的元素数量除以桶 数量 ,用于衡量哈希冲突的严重程度,也常作为哈希表扩容的触发条件。例如在 Java 中, 当负载因子超过 0.75 时,会将哈希表扩容至原先的 2 倍。
直接扩容哈希表的效率很低,为了避免哈希冲突,通常会使用“链式地址”和“开放寻址”两种 方法来改良哈希表的结构,降低哈希冲突的发生概率。
链式地址
链式地址(separate chaining)将单个元素转换为链表,将键值对作为链表节点,将所有 发生冲突的键值对都存储在同一链表中。
值得注意的是,当链表很长时查询效率为 O(n)
,此时可以将链表转换为“AVL 树”或“红黑
树”,从而将查询操作的时间复杂度优化至 O(log_n)
。
开放寻址
开放寻址(open addressing)不引入额外的数据结构,而是通过“多次探测”来处理哈希冲 突,探测方式主要包括线性探测、平方探测和多次哈希等。
线性探测
平方探测
多次哈希
TODO 哈希算法
为了实现“既快又稳”的哈希表数据结构,哈希算法应具备以下特点。
- 确定性:对于相同的输入,哈希算法应始终产生相同的输出。这样才能确保哈希表是可靠 的。
- 效率高:计算哈希值的过程应该足够快。计算开销越小,哈希表的实用性越高。
- 均匀分布:哈希算法应使得键值对均匀分布在哈希表中。分布越均匀,哈希冲突的概率就 越低。
实际上,哈希算法除了可以用于实现哈希表,还广泛应用于其他领域中。
- 密码存储:为了保护用户密码的安全,系统通常不会直接存储用户的明文密码,而是存储 密码的哈希值。当用户输入密码时,系统会对输入的密码计算哈希值,然后与存储的哈希 值进行比较。如果两者匹配,那么密码就被视为正确。
- 数据完整性检查:数据发送方可以计算数据的哈希值并将其一同发送;接收方可以重新计 算接收到的数据的哈希值,并与接收到的哈希值进行比较。如果两者匹配,那么数据就被 视为完整。
对于密码学的相关应用,为了防止从哈希值推导出原始密码等逆向工程,哈希算法需要具备 更高等级的安全特性。
- 单向性:无法通过哈希值反推出关于输入数据的任何信息。
- 抗碰撞性:应当极难找到两个不同的输入,使得它们的哈希值相同。
- 雪崩效应:输入的微小变化应当导致输出的显著且不可预测的变化。
MD5 | SHA-1 | SHA-2 | SHA-3 | |
---|---|---|---|---|
推出时间 | 1992 | 1995 | 2002 | 2008 |
输出长度 | 128 bit | 160 bit | 256/512 bit | 224/256/384/512 bit |
哈希冲突 | 较多 | 较多 | 很少 | 很少 |
安全等级 | 低,已被成功攻击 | 低,已被成功攻击 | 高 | 高 |
应用 | 已被弃用,仍用于数据完整性检查 | 已被弃用 | 加密货币交易验证、数字签名等 | 可用于替代 SHA-2 |
Python 在不同控制台中运行程序时,输出的哈希值是不同的。这是因为 Python 解释器在 每次启动时,都会为字符串哈希函数加入一个随机的盐(salt)值。这种做法可以有效防止 HashDoS 攻击,提升哈希算法的安全性。