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 中,如下图所示:

图 1: Hashing 概念

由于 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)=kmodmh(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)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,这样 nninsertinsert 操作的复杂度就是 θ(n2)\theta(n^2)

  • m *= 2:每次容量 * 2,这样 nninsertinsert 操作的复杂度就是 θ(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