哈希表
现在有一个表S里放着n条记录，每条记录都会有键值及其指向的具体内容
哈希碰撞：将两个key映射到一个slot，就会造成哈希碰撞。
理想哈希：每个key都有相同的概率被映射到每个hash。
理想哈希表
- 键随机映射到槽上——简单均匀哈希,表
- 每个键与其他被哈希的记录或者键之间相互独立
- 如果有一个键被哈希映射到同一个槽的概率是 $1/m$
- 哈希表装在因子：$α$ ——每个槽里键的平均数量
- 预计搜索时间 $Θ(1+α)$ ~ $Θ(1)$
操作
必须先找到键值，才可以操作
- Insert(S,x) : S <– S u {x}
- Delete(S,x) : S <– S - {x}
- Search(S,k) : returns x key[x] = k or null if no such x
直接映射表
可以将全域 $U={0,1,…m-1}$ 映射到一个称为直接寻址表的数组 $T[0,m-1]$上。直接寻址表中每个位置称为槽(slot)。如果 $k \in U$ ，但不属于关键字集合,则 $T[k]=NIL$.
字典操作 $Θ(1)$
1
2
3
4
5
6
7
8
DIRECT-ADDRESS-SEARCH(T, k)
return T[k]
DIRECT-ADDRESS-INSERT(T, x)
T[x.key] = x
DIRECT-ADDRESS-DELETE(T, x)
T[x.key] = NIL
快速哈希函数
除法哈希法
$h(k) = k mod m$k对m取余，m是哈希表里槽的数量。
【注意：】不要选择太小的m来做除数，取质数最好，不要接近2的幂或10的幂。
乘法哈希法
假设：槽的数量是m,是以2为底的幂数；计算机一个字长度是w位。
$h(k) = （A · k mod 2^k） rsh (w-r)$ A是奇数，满足 $2^(w-r)<A<2^w$, rsh指二进制位运算右偏移
第一步，用关键字 k 乘以常数 A(0 < A < 1), 并提取 kA 的小数部分。 第二步，用 m 乘以这个值，再向下取整。
开放寻址法 （open addressing）
所有关键字均存放于散列表中，即每个槽位包含至多一个关键字。用开放寻址法处理冲突，散列表是可以被填满的，且散列表的装填因子 $α$ 不会超过 1。键数不能大于槽数。
【优点：】避免了指针的聚集，而且由于可以直接存储关键字，不需要存储指针，节约了存储空间。
使用开放寻址法插入一个关键字，需要连续探查（probe）散列表，直到找到一个空槽位来存放关键字为止。探测的顺序取决于将要插入的关键字。
探查方法
如果有n个项存放在m个槽里，有$m!$种探查序列，探查过程中碰撞到一个已经被占用的槽的概率是 $n/m$，第二次探查发生碰撞的概率是$(n-1)/(m-1)$…之后的以此类推。
探查期望次数是 <= $1/(1-α)$
线性探查
$h(k,i) = (h(k,0) + i) mod m$
【问题：】会遇到“一次群集”的问题
二次哈希
$h(k,i) = (h1(k) + i * h2(k)) mod m$ 其中, $i = 0,1,…,m-1$
h1决定指针初始位置 ,h2(k)在指针初始位置的基础上进行偏移。为了保证整个散列表都能被探测到，h2(k)的值必须与散列表的大小m互质。