简述
哈希表是一种初级数据结构, 但是非常受开发者的重视, 在实际开发中应用极广, 因此也是面试和算法笔试中高频出现的数据结构, 是一种典型的空间换时间的算法。
如果说数组相当于象棋里的卒,适合作为基础算法稳扎稳打, 但需要随时做好为中高阶算法让位的准备。 那么哈希表就相当于象棋里的马,在合适的时候使用,简单的数据结构能够起到的效果不亚于任何高阶算法。
哈希表之所以有如此高的评价,是因为他可以保证O(1)时间的查询,所以一般来说哈希表都是用来快速判断一个元素是否出现集合里。这是链表和数组都无法轻易做到的。
哈希表的理论基础
首先, 官方对哈希表的定义是比较简单粗暴的: "哈希表是根据关键码的值而直接进行访问的数据结构。"
根据这个定义, 我们完全可以说数组也是一种哈希表。不过为了避免出现歧义, 我想有必要明确一下我所说的「数组算法」指的是「数组(数据结构) + 基于数组结构特性而生的算法(e.g. 二分搜索, 前缀和, etc)」
当然, 哈希表如此受欢迎, 背后的原因远比一句轻飘飘的O(1)搜索复杂。毕竟O(1)时间的查询其实数组也完全可以做到, 但是只限于基于索引的搜索, 但如果实际应用中搜索的key无法作为索引, 那只能放弃这个做法。
而哈希表的原理背后就是计算机领域的前辈们不断解决这个问题, 以及一系列历史遗留问题而慢慢总结出来的最优解合集。
相信在还没有发明哈希表的某个时期, 所有常数时间的搜索必须依赖数组。 因此我们的第一个历史遗留问题自然就是「如何将非整数类型的key变成数组可用的int索引」。 因此, 当人们试图解决"如何根据string类型的key完成常数时间的搜索"问题时, 自然就会想到一种最为直接的方案: "干脆将字符串想个办法变成int用来作为索引", 这样就可以基于数组实现O(1)的搜索了。
这个方案从工程的角度其实是非常合理的, 因为我们可以有效利用已经存在的资源(数组), 只要开发一套将字符串转换成int的逻辑就行。 如果只是为了将str转成int, 那这种逻辑有很多, 最简单的方法其实就是将字符串根据ASCII码对应的十进制的表达, 但至今无人采用, 是因为转换的数组会随着字符串长度的增加而无限制地增长, 那么理论上也需要创建更大的数组来容纳对应的索引。 我们甚至不用去探讨索引分布是否稀疏的情况, 单是空间复杂度的upper bound取决于最长字符串的长度就已经注定了这个方案必不可能被开发者接受。
因此, 从性能的角度出发, 理想的转换逻辑最起码需要满足以下的限制, 才有可能构建出理想的哈希表数据结构:
- 「强确定性」 生成的int可以被复现 相同的str必须要能够生成相同的int (否则搜索根本没意义)
- 「抗碰撞性」 生成的int可以不重复 不同的str必须要生成不同的int (否则信息可能会被意外覆盖)
- 「范围可控」 生成的int范围有限 能够确定生成int的范围 (否则可能会导致内存开销过大)
而这种方法很早就已经被数学家们研究出来了, 那就是哈希函数 (Hash Function)
哈希函数
哈希函数是一种源自于密码学的数学方法, 可以通过特定方式(hashCode)将其他数据格式转换为不同的数值, 这样就可以把非整数类型的key映射为数组的索引数字了。
相比于类型转换的特性, 哈希函数真正最彪悍的特征其实是其「运算不可逆」。根据A = hash(B), 只要我知道B可以随时求出A, 但是我知道A却无法确定B是多少。一个简单的例子是:
def hash(val):
return "0" if val % 2 == 0 else "1"
在以上的例子中, 我可以根据手中val=7的奇偶性得到哈希值是"1", 但是根据哈希值我最多可以反向推出val是奇数, 无法确定它到底是哪个奇数。
这也是哈希函数通用的特性, 正因为这个特性, 哈希函数被广泛应用于网络安全和区块链, 因为它能允许用户在将隐私数据/密码/密钥哈希后直接公布, 而不用担心被解码。(这不完全是哈希函数的功劳, 需要遵循一整套非对称加密的流程)
以上关于密码学和网络安全的内容虽然是题外话, 但它其实也其实暴露了哈希函数的一个问题, 那就是不能保证「独一无二」的特性。 还是存在不同的A和B两个字符串, 通过哈希函数后, 使得hash(A) = hash(B), 这种现象被称为「哈希碰撞」, 哪怕这个概率很小, 但是也不足以在应用中可以忽略，这是因为人们需要在内存消耗中取舍。 (补充: 哈希碰撞的概率取决于哈希空间, 可以理解为哈希映射后int的范围, 哈希空间越小, 就越容易发生碰撞)。
区块链中常用的SHA2哈希函数因为哈希空间较大, 在实际中我们认为哈希碰撞的概率小到可以忽略, 但是成本意味着它能生成的哈希值范围是所有的32位整数, 意味着我们需要生成一个对应的长度为2**32的一维数组。这是不现实的, 因此只能做一个tradeoff, 「用更高的碰撞的概率换更小的内存开销」。
因此, 我就就有了第二个历史遗留的问题「哈希碰撞」。如果无法解决哈希碰撞的问题, 那么哈希函数依旧不够实用。
哈希碰撞的解决方案
哈希碰撞本身是个概率问题, 所以如何避免哈希碰撞其实是个无解的问题。 从离散数学的角度, 最多就是通过增加哈希空间的方式来减少碰撞概率, 但是无法在理论上将概率归零。所以既然避免不了, 索性就思考一下碰撞发生了如何解决。
碰撞问题的本质上其实是冲突问题。当出现「哈希碰撞」时, 意味着存在至少两个不同的key指向同一块内存, 而两个被存储的内容都是同等得有意义, 哪个也不能轻易得丢弃, 否则如果用新值覆盖原先的key, 当拿新key搜索时, 就会获取到意料之外的值, 严重的时候可以导致重大事故
由此可得, 唯一合理的解决方案就是思考如何才能「将所有的碰撞结果保存, 等到查询时再做辨别」。
很显然, 「保存碰撞结果」比「避免碰撞」简单太多了。最直接的一个方案就是「改良哈希表数据结构」,使得哈希表可以在出现哈希冲突时正常工作。
事实上, 业界里哈希表的结构改良方法主要包括两种, 分别是 "链式地址" 和 "开放寻址"。
「链式地址」
在原始哈希表中，每个内存区块(也被称为"桶")仅能存储一个键值对, 链式地址(separate chaining)所做的, 就是将单个元素转换为链表, 将键值对作为链表节点, 将所有发生冲突的键值对都存储在同一链表中。
站在学习者的角度, 至此可能会有一个问题(至少我学的时候很久没想通), 那就是既然hash后的key已经重复了, 我们靠着hash后的key如何在链表中找到想要的元素?
如果站在开发者的角度, 这个问题其实非常好解决, 只需要数据结构中保留哈希前的原始key, 就能在哈希碰撞发生时顺着链表找到特定的元素。
至此, 「链式地址」的基本原理已经清晰, 我们就可以设计出如下的数据结构。
链式地址存在以下局限性
- 占用空间增大: 将原本的数组结构加入链表设计后, 需要包含节点指针, 会更加消耗内存空间
- 查询效率降低: 加入了链表后, 引入了线性搜索的时间复杂度, 虽然只会发生在「哈希碰撞」时, 但是worst case就等同于线性搜索链表。
「开放寻址」
「链式地址」虽然解决了「哈希碰撞」的问题, 但因为引入了额外的数据结构, 在性能上其实并不占优。 尤其是很多开发者习惯性地考虑悲观情况时, 也就是在「链式地址」中所有元素都发生碰撞并挤在一个桶里。那么查询的效率也会退化成O(N)的时间复杂度。
这时候很多开发者注意到, 哈希表因为其插入操作不具备连续性, 所以实际上的内存使用是零散的、稀疏的, 明明哈希表里还有那么多内存浪费, 何必通过增加链表的方式来解决碰撞问题?
于是「开放寻址」算法的雏形就诞生了。
除了不借助额外的数据结构,「开放寻址」相比于「链式地址」最大的不同就是「不在原地解决问题」。我个人认为「开放寻址」的思想其实更加符合生活中的逻辑, 毕竟在现实生活中, 人们发现自己的位置被占了的第一反应可能都是既然位置被占了就哪个空的坐哪个, 而不是非要搬一把新椅子来。 (我自己就是靠这个例子理解「开放寻址」的🤦)
那问题来了, 「链式地址」之所以不惜使用额外的数据结构也要在「原地解决问题」的目的就是为了方便查询, 毕竟根据哈希值, 只会找到那一个"桶", 而「开放寻址」直接就近放到别的桶里, 这在查找的时候怎么找得到?
我们也可以多想一层, 当发生碰撞时, 我们就把新的键值对就近放到下一个空桶, 但是如果紧接着这个桶的"正主", 也就是实际上指向这个桶的第一个哈希值, 出现了, 它如何能够知道这个位置因为别的地方的碰撞已经被占据了?
这就需要算法主动去探测来处理哈希碰撞, 会牵扯到另外一个算法「线性探测」
探测的逻辑也非常简单, 如果哈希值指向的桶不为空, 那就意味着已经发生了碰撞。我采用固定的步长从哈希值指向的桶往下探测, 当我找到符合的原始key时, 就能锁定桶的位置。而当探测到空的桶时, 意味着这个key不存在, 因为如果按照约定的插入规则, 这个值如果被插入, 则不应该在找到该值之前出现空桶。
如果足够细心, 会发现这个操作同样有问题: 如果插入发生冲突, 就近插入空桶后, 原始桶和插入桶之间的某个桶的元素被删除了怎么办? 按照现有的「线性探测」逻辑, 当遇到空桶时就会直接结束探测, 从而使得插入后的值也失去意义。
这个问题的解决方案比想象中更简单粗暴: 不直接从桶里移除元素, 而是利用一个特定常量「TOMBSTONE」来标记这个桶, 这样既不会因为空桶而提前中断「线性探测」, 又不妨碍插入新的值。
这种操作被称为 「懒删除」 Lazy Deletion
「线性探测」容易引起"聚集现象"
当哈希碰撞大量出现时, 需要频繁越位插入就近的空桶, 会导致底层数组中连续被占用的位置越来越长, 从而使得哈希冲突的可能性更大, 进一步促使聚集生长, 形成恶性循环。这种情况下, 每一次查询都会有不小的开销。
除了「线性探测」, 还有「平方探测」和「多次哈希」等其他的探测算法, 都是「开放寻址」中常用的策略, 后两种策略都是旨在解决「线性探测」中的聚集问题。
一些额外的优化方式: 红黑树 「会在后面Tree的章节详细写」
原则上来说, 至此哈希表已经足够称为独当一面的数据结构了, 但是一些较为悲观的(非贬义🤐)计算机领域前辈们还是哈希碰撞问题提出了一些新的质疑, 这也就是我们最后的一个历史遗留问题 「当大量发生哈希碰撞的时候, 如何解决长链表的查询性能问题」。
这个问题其实距离我们不算太远, 目前似乎仍存在争议, 大多数编程语言都没有针对这个问题做出修改, 目前只有Java和C++在HashMap的底层实现中, 在某些情况采用了「红黑树」取代原本的链表来将大量碰撞时的查找效率从 O(n) 优化到了 O(log n)。
哈希表性能对比
| 数组 | 链表 | 哈希表 | |
|---|---|---|---|
| 查找元素 | O(1) | O(N) | O(1) |
| 添加元素 | O(N) | O(1) | O(1) |
| 删除元素 | O(N) | O(1) | O(1) |
| 遍历所有元素 | O(N) | O(N) | O(N) |
刷题经验总结
先说结论: 什么时候使用哈希表?
当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
| 编号 | 名称 | 难度 | 哈希解题思路 |
|---|---|---|---|
| 1 | 两数之和 | 简单 | 全LeetCode题库开篇第一题就是很典型的哈希表, 因为我们遍历的同时要寻找符合元素i的另一半是否遍历过。 |
| 202 | 快乐数 | 简单 | 如题, 求和的过程中, sum会重复出现, 所以我们完全可以用哈希表来判断sum是否重复出现。 |
| 242 | 有效的字母异位词 | 简单 | 暴力解法两层for循环, 可以定义哈希表一次for循环记录s中字符出现次数(因为题目元素只包括26个小写字母, 所以直接定义长度为26的数组代替哈希表也行「严格意义上数组也算哈希表」) |
| 349 | 两个数组的交集 | 简单 | 与其反复遍历A数组求交集, 不如将A出现的元素全存到哈希表, 遍历B数组时可以O(1)时间确认元素在A中是否存在 |
| 383 | 赎金信 | 简单 | 题目说只有小写字母, 那可以采用空间换取时间的哈希策略, 用一个长度为26的数组来记录magazine里字母出现的次数即可。 |
| 454 | 四数相加II | 中等 | 相比于两数之和, 这道题牵扯的变量更多, 所以O(N)确实没可能, 但是定义哈希表, key放a和b两数之和, value 放a和b两数之和出现的次数, 再去遍历C+D数组, 完全可以将O(N^4)的时间复杂度降到O(N^2)。 |