open-courses
Search…
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. 1.
    keys 必须是非负整数 解决方案:"pre-hash" keys to integers (注意理解这里的 pre-hash)
  2. 2.
    如果 key 的范围很大,将造成空间浪费 解决方案:"hashing"

Hashing

本质就是通过 hash function 将 key 所处的整个空间
UU
(通常很大)压缩到有限的可接受大小的表
mm
中,如下图所示:
图 1: Hashing 概念
由于
UU
远大于
mm
,必然存在冲突(collision)的情况,即不同的 key 被映射到同一个值上,解决这个问题通常有两种做法:
  1. 1.
    chaining:hash function 指定 item 插入的位置,插入位置相同的 key 用链表串联起来
  2. 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)=kmodmh(k) = k \bmod m
,实践中 m 应取为质数且不接近
2x2^x
(提示:计算 hash 时考虑的信息)
Multiplication Method
分为三步:
  1. 1.
    确定一个 0 到 1 之间的常数 A
  2. 2.
    将 key k 与 A 相乘,取其小数部分
  3. 3.
    将小数部分与另一个常数 m 相乘,向下取整
以上步骤可以总结为:
h(k)=m{kA}h(k) = \lfloor m\{kA\} \rfloor
这里的 m 取值则应该尽量接近
2x2^x
(思考:计算的方便性)
假设计算机的 word size 为 w,那么上述思想的一种实现就是:
h(k)=[(a×k)mod2w]>>(wr)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 是随机程度最高的。此时
2r2^r
就应该接近 hash 表的大小。
Knuth 建议:
A=(51)/20.618A = (\sqrt{5} - 1)/2 ≈ 0.618
s=2654435769A232s = 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)modmh(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))modmh(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