Dictionary Problem & Implementation

Dictionary Problem

dictionary, map, associated array 以及 symbol table 实际上都是指同一种抽象数据类型（ADT），它维护着一个键值对（这里记为 item）集合，支持以下方法：

方法	描述
$insert(item)$	将一个 item 加入到集合中
$delete(item)$	从集合中删除 item
$search(key)$	如果 key 存在，则返回对应的 item

几乎所有语言都有 Dictionary ADT 的实现，以 Python 为例：

• Python dictionary

• Python set （dictionary where items are keys without values）

场景

• 几乎所有现代编程语言必备：Python, Perl, Ruby, JavaScript, Java, C++, C#, ...

• database

• compilers & interpreters: names -> variables

• network routers: IP address -> wire

• network server: port number -> socket/app

• virtual memory: virtual address -> physical

• substring search

• string commonalities

• file/directory synchronization

• cryptography

Implementation

Associative List/Linked List

用 Linked List 将所有 item 串联起来，每次搜索最坏情况都需要遍历 Linked List，总结如下：

方法	复杂度（平均）	复杂度（最坏）
$insert(item)$	$O(1)$	$O(1)$
$delete(item)$	$O(n)$	$O(n)$
$Search(key)$	$O(n)$	$O(n)$

在 item 数量较少的时候，Linked List 的实现能展现出较高的性能，且它的常数系数很小。

Direct Access Table

将 items 存储在 array 中，用 key 做 array 的 index，但这会产生两个问题：

1. keys 必须是非负整数 解决方案："pre-hash" keys to integers （注意理解这里的 pre-hash）

2. 如果 key 的范围很大，将造成空间浪费 解决方案："hashing"

Hashing

本质就是通过 hash function 将 key 所处的整个空间 $U$（通常很大）压缩到有限的可接受大小的表 $m$ 中，如下图所示：

图 1: Hashing 概念

由于 $U$ 远大于 $m$ ，必然存在冲突（collision）的情况，即不同的 key 被映射到同一个值上，解决这个问题通常有两种做法：

1. chaining：hash function 指定 item 插入的位置，插入位置相同的 key 用链表串联起来

2. open addressing：hash function 指定 item 插入位置的顺序（多个位置，即所有位置的排列），发生冲突时，选择下一个位置

Hash Functions For Chaining

在 chaining 中，Hash Functions 指定 item 插入的位置

理想方案: Simple Uniform Hashing

什么样的 hash function 才是个好 hash function 呢？

• 每个 key 被 hash 到每个 slot 的概率相等

• 每个 key 被 hash 到某个 slot 的概率相互独立

设 $n$ 为 key 的个数， $m$ 为 table 的大小，那么负载系数（load factor) $\alpha = \frac{n}{m}$ ，search 的时间复杂度为 $θ(1+\alpha)$ ，如果 $\alpha = O(1)$ ，即 $m = \Omega(n)$ 时，search 的时间复杂度可进一步简化为 $O(1)$ 。如何实现呢？ 实践方案

在实践中，通常很难满足 Simple Uniform Hashing 的假设，但我们仍然能够做到很好的结果。基本的想法就是：避免 hash 值与 keys 出现的模式（patterns）存在相关关系。

Division Method

$h(k) = k \bmod m$ ，实践中 m 应取为质数且不接近 $2^x$（提示：计算 hash 时考虑的信息）

Multiplication Method

分为三步：

1. 确定一个 0 到 1 之间的常数 A

2. 将 key k 与 A 相乘，取其小数部分

3. 将小数部分与另一个常数 m 相乘，向下取整

以上步骤可以总结为：

$$h(k) = \lfloor m\{kA\} \rfloor$$

这里的 m 取值则应该尽量接近 $2^x$ （思考：计算的方便性）

假设计算机的 word size 为 w，那么上述思想的一种实现就是：

$$h(k) = [(a \times k) \bmod 2^w] >> (w-r)$$

即将 key k 与一个 w 位的常数 a 相乘，得到一个 2w 位的数，再取后者的后 w 位的前 r 位...如下图所示：

图 2 - multiplication method intuition

从图中可以看出，这种做法实际上就是将 key k 平移多次并加总，然后取图中红色区域的 bits 作为 hash 值，直觉可以观察出，红色区域的 bits 是随机程度最高的。此时 $2^r$ 就应该接近 hash 表的大小。

Knuth 建议：

$$A = (\sqrt{5} - 1)/2 ≈ 0.618$$

$$s = 2654435769 ≈ A * 2^{32}$$

Universal Hashing

Universal Hashing 是一种随机算法，核心思想是从一组预定义好的 hash functions 中随机选取一个来执行 hash，从概率上可以证明它的预期效果与 Simple Uniform Hashing 一致。

将在 6.046 的笔记中详细介绍。

Hash Functions For Open Addressing

在 open addressing 中，hash functions 指定 item 尝试插入的位置先后顺序

各操作实现逻辑

Insert

for i in range(m):
    if T[h(k, i)] is None:
        T[h(k, i)] = (k, v)
        return
raise 'full'

Search

for i in range(m):
    if T[h(k, i)] is None:
        return None
    elif T[h(k, i)][0] == k:
        return T[h(k, i)]
return None

Delete

注意在删除元素的时候，我们不能直接找到该元素然后将其删除，这样之前依赖于这个位置的元素都将无法找到，可以使用特殊的标记，如 "DeleteMe"，Insert 将它当作是 None，但是 Search 将它当作存在的元素。

理想方案：Uniform Hashing Assumption （与 Simple Hashing Assumption 不同）

对于 Open Addressing 来说，什么样的 hash function 才是个好 hash function 呢？

• 每个 key 的插入顺序是全排列中的任意一个的概率相同

通过推导可以得到：假设我们将 $n$ 个元素插入到大小为 $m$ 的表中，下一次插入尝试的次数期望为：

$$\#probes = \frac{1}{1-\alpha}, \alpha = \frac{n}{m}$$

实践方案

Linear Probing

Linear Probing 就是在发生冲突的时候，找到最近的下一个空闲位置，将 item 插入。

$$h(k, i) = (h'(k) + i) \bmod m$$

一个形象的例子就是停车位，通常驾驶员会从马路边的某个车位开始向一个方向寻找空闲车位，知道找到为止。

这种策略的问题很明显，在 hash function 不够随机的时候，可能会出现聚簇（cluster)，导致所有聚簇附近的操作的效率下降。经过概率分析，可以推导出：当 $0.01 < \alpha < \frac{n}{m} < 0.99$ 时，聚簇的大小为 $\theta(log(n))$ ，因此从概率分析角度上看， insert, search, delete 的操作复杂度都将降格为 $\theta(log(n))$ 。

Double Hashing

顾名思义，就是使用两个 hash function 组合而成，其公式如下：

$$h(k, i) = (h_{1}(k) + i \times h_{2}(k)) \bmod m$$

但我们仍然需要保证 $h(k, i)$ 是位置的一个排列（permutation），怎么做？

要保证 $h_{2}(k)$ 与 $m$ 互质（relatively prime）

比如： $m = 2^r$ ，且 $h_{2}(k)$ 是奇数

可以通过证明推导出，在一定条件下，Double Hashing 能达到 Uniform Hashing Assumption 的效果。

Table Resizing

目前为止，我们的讨论都是在 Hash Table 大小不变的前提下，但不论我们使用 chaining 还是 open addressing，当负载系数 $\alpha$ 逐渐增大时，Hash Table 的性能都将受到影响。

Hash Table 应该设为多大？

• 通常我们也不知道表应该设置为多大，所以简单地想法就是：从一个小的常数开始，按需放缩。

• 在扩容和缩容操作之后，通常我们还需要重新计算每个元素的 hash 值，这个过程称为 Rehashing

放缩的速度

• m += 1：每次容量 +1，这样 $n$ 次 $insert$ 操作的复杂度就是 $\theta(n^2)$
• m *= 2：每次容量 * 2，这样 $n$ 次 $insert$ 操作的复杂度就是 $\theta(1+2+4+8+...+n) = \theta(n)$

什么时候放缩

• 放大：当 load factor 达到阈值时，或者 $n$ 接近 $m$ 时（有点晚了）
• 缩小：当 $n$ 接近 $\frac{m}{4}$ 时

参考

2011 Fall, MIT 6.006, lecture 8-10