# 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 概念](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LVclCu8w2DFq7oSX2p0%2F-LVcvFjkw6Geyg5dN0Rv%2FScreen%20Shot%202019-01-07%20at%2011.26.44%20PM.jpg?alt=media\&token=27833af4-8e5d-4c96-8919-faf380e6ef7d)

由于 $$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)$$ 。如何实现呢？\
\
\&#xNAN;*实践方案*

在实践中，通常很难满足 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](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LVhoWXuZfaPOo8DIY78%2F-LVhxiBv3nz4vlSg2J1F%2FScreen%20Shot%202019-01-08%20at%2010.56.07%20PM.jpg?alt=media\&token=7c4674b5-13fa-48a3-a5d8-e432e5ecfe61)

从图中可以看出，这种做法实际上就是将 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**

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

**Search**

```python
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)$$&#x20;
* m \*= 2：每次容量 \* 2，这样 $$n$$ 次 $$insert$$ 操作的复杂度就是 $$\theta(1+2+4+8+...+n) = \theta(n)$$&#x20;

*什么时候放缩*

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

### 参考

2011 Fall, MIT 6.006, lecture 8-10