Dictionary Problem & Implementation

Dictionary Problem

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

方法

描述

insert(item)insert(item)

将一个 item 加入到集合中

delete(item)delete(item)

从集合中删除 item

search(key)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)insert(item)

O(1)O(1)

O(1)O(1)

delete(item)delete(item)

O(n)O(n)

O(n)O(n)

Search(key)Search(key)

O(n)O(n)

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 所处的整个空间 UU（通常很大）压缩到有限的可接受大小的表 mm 中，如下图所示：

由于 UU 远大于 mm ，必然存在冲突（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 的概率相互独立

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

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

Division Method

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

Multiplication Method

分为三步：

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

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

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

以上步骤可以总结为：

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

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

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

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

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

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

Knuth 建议：

A=(5−1)/2≈0.618A = (\sqrt{5} - 1)/2 ≈ 0.618
s=2654435769≈A∗232s = 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 的插入顺序是全排列中的任意一个的概率相同

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

#probes=11−α,α=nm\#probes = \frac{1}{1-\alpha}, \alpha = \frac{n}{m}

实践方案

Linear Probing

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

h(k,i)=(h′(k)+i) mod mh(k, i) = (h'(k) + i) \bmod m

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

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

Double Hashing

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

h(k,i)=(h1(k)+i×h2(k)) mod mh(k, i) = (h_{1}(k) + i \times h_{2}(k)) \bmod m

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

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

比如： m=2rm = 2^r ，且 h2(k)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，这样 nn 次 insertinsert 操作的复杂度就是 θ(n2)\theta(n^2)

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

什么时候放缩

  • 放大：当 load factor 达到阈值时，或者 nn 接近 mm 时（有点晚了）

  • 缩小：当 nn 接近 m4\frac{m}{4} 时

参考

2011 Fall, MIT 6.006, lecture 8-10

PreviousPriority Queue Interface & ImplementationNextSorting

Last updated