字典(Dictionary)#

一种抽象数据类型. 其维护某个集合, 集合中的每个元素item都含有键key. 拥有如下操作:

1. 插入: insert(item)
2. 删除: delete(item)
3. 查找: search(key)

python的内置类字典实现了上述功能, 每个元素都为一个键-值对.

我们知道, 平衡BST能在$O(log n)$内解决如上问题.

能不能更快?

直接寻址表(Direct Access Table)#

最简单的想法就是建立一个数组, 由于数组的(指定索引)随机访问的效率是$O(1)$, 可以再设置一个状态保存空元素. 于是:

1. insert(key, value): arr[key] = value
2. delete(key, value): arr[key] = EMPTY
3. search(key): return arr[key]

我们就完成了上述目标. 然而聪明的同学可能已经发现, 我们这个实现有很多问题:

1. 最主要的问题是key只能是非负整数, 而我们往往需要以字符串或者其他类型作为key.
2. 假如key的分布比较稀疏(e.g. key[0] = 1, key[1] = 100000000000), 那么即使我们只需要存两个元素, 也得开100000000000以上的空间!

哈希碰撞/哈希冲突#

我们将一个巨大的整数域映射到了一个小范围里, 由于所有可能的键的数量远大于m, 根据抽屉原理, 必然会有多个不同的键$k_1, k_2, ... k_s$被映射到同一个桶中. 假如说我们的元素恰好被prehash到了$k_1, k_2, ... k_s$的某些键当中, 就必然出现同一个桶里储存了不同的元素. 这就叫做哈希碰撞(或哈希冲突, Collisions).

如何处理冲突，是整个哈希技术的核心和灵魂. 我们课程里会介绍两种主流的冲突解决方式. 这里介绍拉链法, 后续课程中会介绍开放寻址法.

动态哈希表#

上一节我们提到, 哈希表的规模m要与数据规模n成正比.那么随着数据规模的变化(插入, 删除), 我们哈希表的规模也要发生变化.

采用类似std::vector的倍增形式即可, 可以达到均摊$O(1)$. 当$n > m\alpha$时, m倍增, 当$n < m\alpha / 4$(避免在临界点时反复地倍增, 缩小)时, m缩小一半. $\alpha$的取值因需求而定, 一般设定$\alpha < 0.7$.

但是这里需要注意, 每次改变m的时候我们的哈希函数都会随之改变. 也就是说每次扩容或者缩小, 我们都要对原哈希表的所有元素重新进行一次哈希(rehash), 复杂度$O(m)$, 均摊后为$O(1)$.

由于这个均摊复杂度分析非常简单(指的是复杂度分析的过程, 而这个想法本身其实非常天才), 与线性表的扩张如出一辙, 这里不再赘述.

字符串匹配#

字符串匹配问题: 给定一个长文本(text)t, 模式串(pattern)s, 判断s是否是t的一个子串.

朴素算法: 比较t中的每一个与s等长的子串是否等于s. 需要$O(|s|\cdot |t|)$.

我们知道, 比较字符串需要$O(|s|)$, 而比较哈希值只需要$O(1)$. 所以我们只需要比较t中的每一个与s等长的子串的哈希值是否等于s的哈希值即可. 但是这里有一个新的问题. 我们必须要在$O(1)$内计算出单个子串的哈希值, 如果每次重新计算的话, 则每次依然需要$O(|s|)$用于计算哈希值.

容易想到, 相邻两个子串的区别仅在于首字符和末字符, 如果相邻两个子串的哈希值可以只根据首末字符的变化而递推的话即可达到$O(1)$递推, 仅第一个子串需要$O(|s|)$.

Karp-Rabin算法

1. 将字符串视作一个a进制的数. 比如如果是纯小写字母的字符串可以取a = 26, 纯英文(文本, 符号)字符串可以取a = 128并用ascii编码代替每个字符.
2. 这里我们使用除法哈希, 将这个大数对某个大质数p取模.
3. 假如我们已经知道了上一个子串$c_1c_2...c_n$的哈希值$h_n$, 想知道下一个子串$c_2c_3...c_nc_{n+1}$的哈希值$h_{n + 1}$, 容易注意到我们只需要下面几个步骤(以下操作全部省略$\% p$):
   1. 消除$c_1$对哈希值的影响, 即$h_n - c_1 \cdot a^{n - 1}$
   2. 哈希值整体左移一位, 即$h_n \cdot a$
   3. 加入后一位的哈希值, 即$h_{n + 1} = h_n + c_{n + 1}$

我们就根据上一个子串的哈希值$O(1)$地递推出了下一个子串的哈希值.

注意到无冲突的情况下, Karp-Rabin算法的时间复杂度为$O(|s| + |t|)$. 但每次冲突需要$O(|s|)$的验证成本.

开放寻址法(open addressing)#

核心思想: 不再使用链表等外部数据结构, 所有数据储存在哈希表(数组)内部.

这意味着哈希表的每一个桶要么为空, 要么恰好储存一个元素, 也就是说负载因子$\alpha \le 1$.

如果某个键k对应的储存位置已经被占用, 那么就通过某个特定的探查序列(probe sequence), 寻找下一个空位. 下一个空位被占用就再寻找下一个空位… 直到找到空位为止.

我们可以定义一个寻址路线.

开放寻址法的哈希函数的形式化定义: $h: U × \set{0, 1, ..., m-1} → \set{0, 1, ..., m-1}$

对于任意一个键k, 其探查序列为<h(k, 0), h(k, 1), h(k, 2), ...>, 一个好的探查序列必须是m的一个排列, 以保证只要表没满, 我们必然能找到一个空位.

开放寻址法的哈希操作流程

1. 插入insert(item):
   1. i = 0
   2. 计算探查位置slot = h(k, i)
   3. 检查其是否为空
      1. 若不为空, i++, 重复步骤2
      2. 若为空, 元素放入T[slot], 操作完成.
      3. 若i >= m, 表已满, 操作失败
2. 查找search(key):
   1. i = 0
   2. 计算探查位置slot = h(k, i)
   3. 检查其T[slot].key是否等于key
      1. 若不相等, i++, 重复步骤2
      2. 若相等, 查找成功
      3. 若为空, 查找失败
      4. 若i >= m, 查找失败
3. 删除delete(item): 这里出现了问题. 假如我们只是简单找到元素并将该位置设置为空, 那么假设另一个键k的探查路径经过这个位置时, 可能会提前遇到空位置并判定查找失败(而不探查后面的探查路径), 删除操作破坏了其他键的探查链.
   1. 解决办法: 可以设置一个特殊标记作为”已删除”状态, 删除某个元素时并不将其设定为空, 而是设定为”已删除”状态.
   2. 若插入操作遇到”已删除”状态, 可以直接当做空位使用, 也就是将”已删除”替换为需要插入的元素
   3. 若查找操作遇到”已删除”状态, 则认为该位置并非空位, 继续探查下一个位置.

加密哈希(Cryptographic Hashing)#

我们上面所讲的哈希算法追求的是快速($O(1)$操作), 而加密哈希追求的是安全性.

加密哈希的属性

1. 单向性: 从哈希值h(x)反推出原始输入x是计算上不可行的.
2. 抗碰撞性: 找到任意两个不同的输入x和y, 使得h(x) = h(y)是计算上不可行的.
3. 抗目标碰撞性: 给定某个输入x, 找到一个x’使得h(x) = h(x’)是计算上不可行的.

加密哈希的应用

1. 密码储存: 储存密码的哈希值, 而非原文, 防止数据泄露
2. 文件完整性校验: 计算文件哈希值如MD5, SHA-256等, 如果文件被篡改, 哈希值就会改变.
3. 数字签名: 对消息的哈希值签名, 而非对整个长消息签名.