哈希、散列表和Rabin-Karp算法

字典

现有一个抽象数据类型(ADT)如下：

包括了一组元素，每个元素都有一个键key。假设没有元素拥有相同的key，如果有相同的key，则覆盖掉原有key的元素。

-insert(item)

-delete(item)

-search(key):根据给定的key，返回元素，如果没有，则报告不存在。

假如用树形结构实现该ADT，则需要时间复杂度O(logn)；而python的dictionary字典类型，可以以O(1)的时间实现。

字典的简单实现

可以用数组来简单实现字典，数组下标等于key，在对应的数组下标处存放相应的元素。

但这样有两个问题：

1. 会占用大量的内存空间，造成存储空间的巨大浪费；
2. 并且key的值不一定是非负数。

解决方案

对②的解决方案：prehash

• 将key映射为非负数
• 理论上，key是有穷数，并且是离散的。计算机中的任何东西最终都可以被表示为一连串的bit，而一连串的bit又能用一个整数表示。
• 在python中，hash(x)相当于x的prehash。
• prehash可能会得到相同的值。理想的情况是hash(x)==hash(y) <=> x=y

对①的解决方案：hashing

hashing方法可以将全部u个keys，减少为可接受的数量大小m。简单来说就是形成一个散列表，通过散列函数hash(x)，将原来键空间内的键放入散列表中进行存放。因为散列函数本身会有冲突collision（即x ≠ y，但hash(x) = hash(y) ），所以散列表下某个键里可能有多个来自键空间内的items。而为了处理这种情况，拉链法Chaining出现了，它是将散列表每个槽内中的冲突元素进行链接。拉链法最差的情况是所有的元素都发生碰撞，所有的元素都被链接在一条链表上，时间复杂度为O(n)。

如果该散列表是简单平均式散列（即每个键被平均(uniformally)地hash到表内的槽里，并假设有n个keys和m个槽，那么散列表里链长度为n / m = α = load factor。而运行时间为Ο(1 + |chain|) = Ο(1 + α)， 其中1指计算hash的时间，|chain|是指形成chain的时间等于它的长度。简单平均式散列是一种理想情况，现实中是几乎不可能存在的。

散列函数

介绍三种散列函数。

（1）Divison Method

h(k) = k mod m    (mod为求余)

（2）Multiplication Method

h(k) = [(a * k) mod 2w] >> (w - r)    (k为w bits，m=2r， ‘>>’为shift right操作)

（3）Universal Hashing

h(k) = [(a * k + b) mod p] mod m    (a和b为从{0,...,p-1}中抽取的随机数，p为大于|u|的质数，质数是只能被1和自身整除的数，u为key space的大小)

对于最差情况k1 ≠ k2下， P{h(k1) = h(k2)} = 1 / m，其小于简单平均式散列下的n / m。

hash用于字符串匹配

假设s为子串，t为主串。

简单的暴力算法伪代码如下：

for i in range (len(t) - len(s))
    if(s == t[i:i+len(s)])
        return i
return -1

时间复杂度为O(|s| * (|t| - |s|)) = O(|s|*|t|)

如何用hash来解决字符串匹配问题，使其能在线性时间复杂度内完成？

一个想法是，将比较主串与子串的每一个字符改为比较主串与子串的哈希值。但每次移动子串，都重新计算t[i:i+len(s)]中每个字符的哈希值显然不会提高效率，其时间复杂度还是O(|s|*|t|)。

如何改进？

可以想到，再后移子串的时候，前len(s)-1个字符的哈希值已经计算过，我们能否将前面已经计算过的哈希值用于下一次的哈希运算呢？如果可以的话，就只需计算新加入的字符的哈希值即可，这样便可以大幅提高时间性能。

基于这个想法，可以提出滚动哈希(Rolling Hash)的ADT：

r中维护了字符串x

- r.append(c) : 将字符c加入字符串x的末尾

- r.skip(&c) : 将字符串x的第一个字符删除，并用字符c接收删除的字符

- r.h() : 返回h(x)的值，h(x)为计算x哈希值的函数

当然，通过哈希值来匹配字符串可能会出现碰撞的情况，即h(x1) == h(x2)，但x1 != x2；因此要对这种情况做特殊处理：假如h(x1) == h(x2)了，那么再逐个比较x1和x2的每个字符，如果x1==x2了，则返回i，如果x1 != x2，则继续匹配。

以上便是Rabin-Karp算法的主要思想。

伪代码如下：

for c in S
    rs.append(c)
for c in t[:len(s)]
    rt.append(c)
if rs.h() == rt.h()
    return 0

for i in range (len(s), len(t))
    rt.skip(t[i-len(s)])
    rt.append(t[i])
    if rs.h() == rt.h()
        if s == t[i-len(s)+1 : i+1]
            # found match
            return i-len(s)+1
        else
            # happens with possibility <= 1/|s|
            continue

时间复杂度为O(|s| + |t| + rs.h()==rt.h()的次数* |s|)

如果哈希函数设置的得当，发生碰撞的可能性是很小的，因此可将该算法的时间复杂度视为线性的。