哈希表
哈希表（Hash Table）是经典的键值存储（Key-Value）数据结构, 其特点是随机访问时需要先通过哈希函数计算每个键所对应的哈希值, 再通过索引映射函数得到哈希值在哈希表中的真实索引, 最后根据键的真实索引得到其对应的值.
令哈希函数为$hash()$, 索引映射函数为$index()$, 则在给定的哈希表$T$中, 得到键$k$所对应的值$v$的过程可以描述如下:
\begin{equation} k_{hash} = hash(k) \end{equation}
\begin{equation} k_{index} = index(k_{hash}) \end{equation}
\begin{equation} T[k] = T.get(k_{index}) = v \end{equation}
其中, $index()$的实现方式与哈希表的结构和哈希冲突的解决方法有关. 以链地址形式的哈希表为例, $index()$首先会对$k_{hash}$以数组长度取模得到对应链表的首地址, 然后通过遍历该链表得到真实值.
哈希表的设计思路是空间换时间, 令$T$为节点数量为$s$的哈希表, 设其中非空节点的数量为$m$, 则负载因子（Load Factor）可按照如下公式计算:
\begin{equation} F_{load} = m/s \end{equation}
相比于空间利用率接近100%的红黑树来说, 哈希表会在负载因子大于阈值时进行扩容并重新映射所有数据, 这样能保证插入和查找数据的时间复杂度尽不会随着哈希冲突出现的次数而显著增加. 设计良好的哈希表能够以$O(1)$时间复杂度实现对数据的查找, 但如果使用的哈希函数无法有效地让键离散化, 那么严重的哈希冲突会导致哈希表的查找时间复杂度退化为$O(n)$的线性表或$O(logn)$的红黑树.
哈希算法的设计原则
哈希函数是基于哈希算法实现的单向函数, 其特点是输入为无限空间内的任意对象, 但输出却被限定为有限空间内指定长度的整数, 并且很难通过结果推算出原始输入. 哈希算法的这些特点让其在密码学、数据校验、负载均衡等领域得到了广泛的应用. 根据PlanetMath中的定义, 优秀的哈希算法应该满足以下性质:
防碰撞 - 理想情况下的哈希函数应属于单射, 即对$\forall x,y \in $输入空间, 在$x \neq y$的情况下都满足$hash(x) \neq hash(y)$. 然而在实际应用中, 哈希函数的输入空间一般远大于输出空间, 因此根据抽屉原理, 在输入的数据足够多的情况下必然会发生碰撞.
在哈希表中, 可以通过开放地址法或链地址法处理发生冲突的数据; 而在安全性要求较高的密码学领域, 攻击者一旦掌握了构造哈希冲突数据的方法就能够轻易破解加密信息, 因此目前常用的加密哈希算法在设计时都倾向于提升破解所需要的成本, 例如: Google提出的SHA-1破解方法需要在单个GPU上运算100年左右, 而暴力破解比特币所使用的SHA-256算法则需要在单个矿机上运行数十亿年.
但在某些特殊的应用场景下, 例如: 通过”姓名+身份证号”查询考试信息, 如果输入值的范围能够事先能够确定且输入空间小于等于输出空间, 则能够通过GNU提供的gperf工具设计出不会发生冲突的完美哈希函数.
防篡改 - 被用于数据校验的哈希算法需要满足对数据敏感的性质, 即使微小的输入变化也应该让输出的结果显著不同. 例如: 在拥有大量不可信机器的对等网络中下载数据时, 为了防止数据出错导致整个文件被重新下载, 需要将大文件分割为4K大小的数据块. 在下载数据之前需要先从可信数据源获取正确的根哈希, 然后下载由每个块对应的哈希值所构成的哈希表, 对哈希表中所有哈希值按顺序拼接成的字符串再次哈希, 并将其与根哈希对比就可以验证表中数据的正确性, 从而验证整个文件的正确性. 这种通过墨克树校验大文件的方法还被应用于数字货币区块信息的防篡改中.
尽管安全哈希算法（Secure Hash Algorithm, SHA）是不可逆的, 但通过暴力枚举构建彩虹表或其他类似的手段仍然能够实现信息窃取, 例如: 针对SHA-1和MD5的反向查询网站. 目前Git仍在使用SHA-1来计算每次提交的唯一标识和数据校验凭证, 尽管在构造哈希值时使用了元信息混淆, 但由于SHA-1算法的破解成本日趋降低, Git从2.2版本开始考虑逐步向更安全的SHA-256算法迁移, 更多细节请参见Linus对Git安全性的回应.
高效率 - 上面提到的SHA和MD都属于计算过程复杂但安全性非常高的加密哈希算法, 但考虑到在哈希表中一般不需要考虑所存储数据的安全性, 并且每次查找、插入、删除数据时都需要使用键的哈希值作为索引来随机访问, 因此在设计专门用于哈希表的哈希算法时应该侧重于提升计算效率. 位运算是常用的哈希函数计算效率优化方法, 也可以通过结果缓存的方式减少计算的次数.
1
2
3
4
5
6
7
from functools import lru_cache
# 省略类相关代码
@lru_cache
def _hash(self, key):
hashed = self._hash_func(key)
# 等价于 hashed % self._size
return self._size - 1 & hashed
在Redis中最早使用计算简单的DJBX33A作为字符串哈希算法, 并使用32 bit Mix Functions作为整数哈希算法. 后来为了提升代码的可维护性, 这两种算法在3.0版本之后被统一替换为碰撞抗性更好的MurMurHash2算法. 但随着Redis以缓存中间件的身份被大量应用于Web服务中, 对哈希洪水攻击的防范能力也日渐成为了哈希算法的选择标准, 最终在5.0版本之后又将哈希算法替换为了更安全且针对短字符串做了效率优化的SipHash算法. 总之, 哈希算法的选择一定要紧密联系实际的应用场景.
哈希冲突解决方案
在实际应用中, 哈希函数的输入空间一般要远大于输出空间, 因此当输入数据达到一定规模时就不可避免地会发生哈希冲突. 现假设哈希函数$hash()$的输出$h$服从均匀分布, 且输出空间的容量为$s$, 即对每个不相同的输入$k$来说, 其映射到输出空间内每个值的概率$P_k$都可以表示为:
\begin{equation} P_k = \frac{1}{s} \end{equation}
令$n$次输入时不发生冲突的概率为$\hat{P_n}$, 则在$n< s$的情况下:
\begin{equation} \hat{P_n} = \prod^{n}_{i=1}(1-(i-1)P_k) \end{equation}
根据麦克劳林公式, 当$-(i-1)P_k$足够小时:
\begin{equation} 1-(i-1)P_k = e^{-(i-1)P_k} \end{equation}
因此$\hat{P_n}$可进一步化简为:
\begin{equation} \hat{P_n} = \prod^{n}_{i=1}e^{-(i-1)P_k} = e^{-\frac{n(n-1)}{2}P_k} \end{equation}
则$n$次输入时发生冲突的概率$P_n$可以表示为:
\begin{equation} P_n = 1 - \hat{P_n} = 1 - e^{\frac{n(1-n)}{2s}} \end{equation}
假设$hash$的输出空间为$2^{32}$范围内的整数所构成的集合, 则在$n>77162$时, 发生冲突的概率就会大于50%; 当$n>92677$时, 发生冲突的概率就会飙升到99.99%, 因此在实现哈希表时必须要想办法解决哈希冲突. 根据是否需要占用额外空间, 可以将哈希表中常用的哈希冲突解决方案分为以下两类:
- 以开放定址法和再哈希法为代表的, 直接在原始数组上寻找空闲空间的方法.
- 以链地址法和公共溢出区法为代表的, 开辟额外空间存储冲突数据的方法.
开放定址法的核心思想是在冲突节点的周围按照线性探测、二次探测、随机哈希探测等方式寻找空闲的节点, 其优点是不额外构造用于存储冲突数据的数据结构, 因此空间利用率高、序列化较容易、适合构建完美哈希; 但缺点是查找和删除的逻辑十分复杂, 经常需要多次探测才能确定要查询的数据是否在表中, 因此当表中存在大量冲突数据时会导致整体处理效率明显下降.
而与之相对应的链地址法则是在数组的每个节点中, 以链表的形式来记录所有映射到该位置的数据. 其优点是在数据频繁添加与删除的场景下的平均时间复杂度要低于开放地址法, 因此JDK、Redis、Python等项目中提供的哈希结构普遍使用链地址法来实现. 此外, 链地址法也具有很强的灵活性, 扩展结构并不局限于单向链表, 例如: JDK中的HashMap会根据每个节点所存储的冲突数据数量, 将扩展结构在链表和红黑树之间切换.
链地址的实现也相对简单, 在建立哈希表时要给每个节点初始化为链表.
1
self._entry = [[] for i in range(self._size)]
插入数据时需要先找到对应的链表, 如果该键已存在则直接更新. 搜索和删除的逻辑与之类似.
1
2
3
4
5
6
7
8
9
10
11
12
13
def _insert(self, key, value):
# 获取key对应的哈希值
index = self._hash(key)
# 根据哈希值获得对应的链表索引
index_list = self._entry[index]
# 如果该key已经存在就更新value
for i, item in enumerate(index_list):
if item[0] == key:
index_list[i] = (key, value)
return
# 如果该key不存在就新增(key, value)元组
index_list.append((key, value))
最后重载运算符, 更多实现细节参见完整代码.
1
2
3
4
5
6
7
8
9
10
11
# value = ht["key"]
def __getitem__(self, key):
return self._search(key)
# ht["key"] = value
def __setitem__(self, key, value):
self._insert(key, value)
# del ht["key"]
def __delitem__(self, key):
self._delete(key)
哈希表扩容
开放定址法的另一个显著问题就是随着输入数据的增加, 初始化时申请的数组空间必然会被用尽, 这时就需要进行哈希表的扩容操作（rehash）. 首先要申请一段连续的地址空间并初始化为新数组, 一般容量为原始数组的两倍, 并且由于数组的长度发生了变化, 全部原始数据都要以重新哈希并取摸的方式映射到新数组上. 不难看出, 如果哈希表中已经存放了大量的数据, 那么扩容操作的成本将是十分昂贵的.
似乎使用链地址法可以避免执行成本如此之高的扩容操作, 但其实不然, 当链表中积累的冲突数据规模显著增加时, 哈希表插入、删除、查找数据的时间复杂度将逐渐从$O(1)$提升到$O(n)$. 并且由于CPU存在分支预测机制, 频繁的哈希冲突会导致大量缓存缺失（Cache Miss）从而显著影响性能. 这就需要我们重新思考如何合理地给出负载因子$F_{load}$的阈值来决定什么时候进行扩容操作.
令事件A为节点$Q$被插入数据, 则在完全随机生成哈希值的情况下, 每次向节点数量为$s$的哈希表$T$中添加数据时事件A发生的概率为:
\begin{equation} P_A=\frac{1}{s} \end{equation}
现在向$T$中添加$n$个数据, 用$X$表示这$n$次独立重复的实验中事件A发生的次数, 显然服从二项分布:
\begin{equation} P_{X=k} = C(n, k)P_A^k(1-P_A)^{n-k} \end{equation}
那么$n$次实验中事件A恰好发生0次的概率为:
\begin{equation} P_{X=0} = (\frac{s-1}{s})^{n} \end{equation}
这个对于节点$Q$成立的结论可以推广到$T$中的所有节点. 为了保证分支预测时缓存的命中率, 需要让$P_{X=0}>0.5$, 两边取自然对数并化简可得$n$的取值范围:
\begin{equation} n < \frac{\ln(2)}{\ln(\frac{s}{s - 1})} \end{equation}
不难看出, 若$T$采用开放定址法处理哈希冲突, 则:
\begin{equation} F_{load} = \frac{n}{s} = \frac{\ln(2)}{\ln(\frac{s}{s - 1}) * s} \end{equation}
当$s\rightarrow+\infty$时, 可以将$F_{load}$展开为如下形式, 详细计算过程与图像参见Wolfram.
\begin{equation} \lim_{s\rightarrow+\infty}{F_{load}} = \frac{\ln(2)}{1+\frac{1}{2s}+\frac{1}{3s^2}+o((\frac{1}{s})^4)} = \ln(2) \end{equation}
结论: 在使用开放定址法处理哈希冲突的哈希表中, 当$F_{load}>0.693$时, 插入新数据发生哈希冲突的概率就会大于50%, 因此哈希扩容的$F_{load}$阈值应设为$0.7$; 而对于使用链地址法的哈希表来说, 插入数据的数量$n$并不能实际代表哈希表中非空节点的数量, 因此阈值可以适当扩大, 例如: JDK中$F_{load}$阈值为$0.75$.
案例1: 实现有序字典
有序字典（Ordered Dict）是指在遍历时能够保持数据插入顺序的字典, 例如:
1
2
3
4
5
6
7
8
9
10
11
# Python 3.6 之前的字典是无序的
>>> dict(a=1,p=3,c=9)
{'c':9, 'a':1, 'p':3}
# 但也存在专门的有序字典类 OrderedDict
>>> OrderedDict(a=1,p=3,c=9)
OrderedDict([('a', 1), ('p', 3), ('c', 9)])
# 在 3.6 版本中修改了字典的实现方式
>>> dict(a=1,p=3,c=9)
{'a':1, 'p':3, 'c':9}
新实现的字典结构不仅操作速度更快, 空间利用率也得到了显著提升, 根据Python-Dev邮件中给出的解释, 其关键在于将插入的数据紧凑地存储在entries中, 并且使用额外的indices用于记录数据在entries中的位置信息. 现假设我们要向字典中插入以下数据:
1
{'timmy': 'red', 'barry': 'green', 'guido': 'blue'}
则首先要使用哈希函数计算出键对应的哈希值, 然后通过索引映射函数得到哈希值在indices中的索引值. 接下来将数据存储到entries中, 并在indices中存储数据在entries中的位置:
1
2
3
4
5
hashed = hash(key)
index = len(indices) - 1 & hashed
self.indices[index] = len(self.entries)
self.entries.append([hashed, key, value])
最终存储结果如下所示:
1
2
3
4
indices = [None, 1, None, None, None, 0, None, 2]
entries = [[-9092791511155847987, 'timmy', 'red'],
[-8522787127447073495, 'barry', 'green'],
[-6480567542315338377, 'guido', 'blue']]
由于哈希值和键值对存储在紧凑的动态数组中, 新的字典在扩容时只需操作存储整数索引的indices结构, 因此数据量特别大的时候效率也不会明显降低. 当然, 在具体实现中同样要考虑如何解决哈希碰撞, 更多实现细节参见源代码.
案例2: 一致性哈希
作为一种分布式缓存协议, 一致性哈希（Consistent Hashing）算法早在1997年就被提出, 最初被用于解决动态网络拓扑结构中的数据转发问题. 相比于普通哈希算法, 一致性哈希的特点是能够有效降低分布式系统中节点变化带来的数据迁移成本. 以分布式图片存储系统的负载均衡问题为例, 假设现在有三千万张图片分散地存储在$N$台缓存服务器上, 如果使用普通哈希算法, 则需要对根据图片文件名$I_{name}$计算出的哈希值取模来获得存储该文件的服务器编号$S_n$:
\begin{equation} S_n = hash(I_{name})\ \%\ N \end{equation}
当服务器的数量$N$发生变化时, 每张图片通过上述公式计算出的$S_n$必然会发生变化, 这就需要对所有数据进行重分配（Reallocation）. 如果数据量很大或者服务器很多, 那么重分配的成本就会变得难以接受, 这时就有必要采用一致性哈希算法来缓解这个问题.
一致性哈希的核心思想就是将哈希函数的输出按顺时针从小到大映射到哈希环上, 为了实现负载均衡, 需要让所有服务器以哈希节点的形式均匀地分布在环上. 这样在寻找每张图片所对应的服务器时, 只需要计算该图片对应的哈希值, 并在哈希环上找到大于该哈希值的最近节点即可, 如果没有大于当前哈希值的节点则应该被哈希值最小的服务器节点处理. 当服务器数量发生改变时, 需要进行数据迁移的只有当前插入或删除的节点及其下一个节点, 重分配的成本得以显著降低.
不难看出, 实现一致性哈希关键在于如何构建哈希环以及如何寻找大于当前哈希值的最近节点, 为此我们需要使用能够对插入的数据自动排序的数据结构, Python标准库bisect中提供的insort_left()函数可以通过二分查找实现数据的有序插入:
1
2
3
4
5
6
7
8
9
10
11
12
13
import bisect
from collections import namedtuple
Sever = namedtuple('Sever', ['hash', 'ip'])
severs = [
Sever(1, '10.41.0.1'),
Sever(6, '10.41.0.6'),
Sever(9, '10.41.0.9')
]
bisect.insort_left(severs, Sever(3, '10.41.0.3'))
print(severs)
接下来实现能够找到大于当前哈希值的最近节点的函数:
1
2
3
4
5
6
7
8
9
10
11
def find_next(nodes: list, img: str) -> str:
assert nodes # 至少包含一个元素
hashed = len(nodes) - 1 & hash(img)
# 寻找第一个大于当前哈希值的节点
for sever in nodes:
if sever.hash > hashed:
return sever.ip
# 没有比当前哈希值大的节点, 就闭环
return nodes[0].ip
为了保证插入或删除节点后每台机器仍能相对均衡地处理请求, 则需要在哈希环中映射额外的虚拟节点, 在实际应用中, 每台服务器所对应的虚拟节点数量会根据机器的性能来分配. 但由于遍历线性表的时间复杂度为$O(n)$, 如果服务器列表中存在大量的虚拟节点, 那么每次查询的时间成本就会显著增加, 这时就应该考虑使用红黑树来替换线性表, 更多实现细节参见完整代码.
案例3: 合理设计哈希键
相比于能够有效执行范围查询的线性表与树形结构, 哈希表的优势在于能够以$O(1)$的平均时间复杂度实现对单个数据的查找、插入、删除操作. 在实际应用中, 通过设计合理的哈希键可以充分发挥哈希表时间复杂度低的优势. 例如在经典题目两数之和中, 为了以$O(n)$的时间复杂度解决问题, 我们使用残差target-num作为哈希表中的查询键:
1
2
3
4
5
6
7
8
9
def twoSum(nums: List[int], target: int) -> List[int]:
hash_table = {}
for i, num in enumerate(nums):
if target-num in hash_table:
return [hash_table[target-num], i]
hash_table[num] = i
return [None, None]
通过这种思路还可以解决与之相似的四数相加II问题. 为了在时间复杂度为$O(n^2)$的前提下解决问题, 首先需要使用哈希表记录a+b的组合种类与数量, 然后以残差0-c-d作为键去查询:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def fourSumCount(A, B, C, D):
# 每个新键初始化为 0
dab = collections.defaultdict(int)
res = 0
# 记录前两个列表的组合
for a in A:
for b in B:
dab[a+b] += 1
# 以残差作为键去哈希表中寻找
for c in C:
for d in D:
if -c-d in dab:
res += dab[-c-d]
return res
合理设计哈希键的关键在于对原始信息的特征提取, 当元素的顺序不重要时, 可以使用排序后的字符串或数组作为键; 在矩阵中, 可以使用列、行、对角线的特征作为键; 在与树形结构联合使用时, 一般采用子树的序列化结构作为键. 在字母异位词分组题目中, 就应该使用排序后的字符串作为哈希键.
1
2
3
4
5
6
7
8
9
def groupAnagrams(strs: List[str]):
# 每个新键初始化为空列表 []
d = collections.defaultdict(list)
# 以排序后的单词作为键
for s in strs:
d[tuple(sorted(s))].append(s)
return list(d.values())
令$n$为字符串的数量, $k$为字符串的最大长度. 则遍历strs的时间复杂度为$O(n)$, 对字符串使用快速排序的时间复杂度为$O(k\log{k})$, 因此总体时间复杂度为$O(nk\log{k})$.
Python提供了基于哈希集合存储非重复量的set类型、基于哈希映射存储键值对的dict字典类型、使用字典加双向链表实现的OrderedDict有序字典以及提供默认初始化接口的defaultdict类型. 熟练使用这些数据结构能够让你快速解决检查存在、计算频率、线性缓存等复杂问题.