字典
现有一个抽象数据类型(ADT)如下：
包括了一组元素，每个元素都有一个键key。假设没有元素拥有相同的key，如果有相同的key，则覆盖掉原有key的元素。
-insert(item)
-delete(item)
-search(key):根据给定的key，返回元素，如果没有，则报告不存在。
假如用树形结构实现该ADT，则需要时间复杂度O(logn)；而python的dictionary字典类型，可以以O(1)的时间实现。
字典的简单实现
可以用数组来简单实现字典，数组下标等于key，在对应的数组下标处存放相应的元素。
但这样有两个问题：
- 会占用大量的内存空间，造成存储空间的巨大浪费；
- 并且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 Srs.append(c)
for c in t[:len(s)]rt.append(c)
if rs.h() == rt.h()return 0for 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 matchreturn i-len(s)+1else# happens with possibility <= 1/|s|continue
时间复杂度为O(|s| + |t| + rs.h()==rt.h()的次数* |s|)
如果哈希函数设置的得当，发生碰撞的可能性是很小的，因此可将该算法的时间复杂度视为线性的。
