使用什么数据结构存储HASH

将每一项存在数组中，通过下标来索引。这种实现的方式问题在于：

要存储的key不是int,不能作为下标；

解决方案：将key从string映射成int

需要的key非常多，储存key所需要的空间可能非常大

解决方案：将所有可能的key映射到一个大小为m的table中,理想情况 m=n,n表示table中key的个数。问题：有可能造成冲突，即两个不同的key计算hash之后，却得到了同一个key

如何将key映射到table的索引的方案

使用hash函数。

除法

h(k)=k mod m

这种方式选择的m通常是与2的幂次方不太接近的质数

乘法

$h(k) = [(a · k) mod 2^w] >> (w − r)$

其中a是个随机数，k包含w个bit,m一般选择 $m=2^r$

取值规则如下：

全局hash

h(k)=[(ak+b)mod p]mod m
其中a,b是{0,..,p-1}中的随机值，P是一个大的质数

使用链表解决hash冲突

如果key是一样的，就在table的当前索引值之后加一个链表，指向新的加入的值，此时，最坏的情况就是，所有的key都hash冲突，导致最坏的查找时间为O(n)

简单一致hash

假设每个key被映射到table中的任意一个索引的概率是一样的，与其它的key通过hashing计算出来的位置无关。
在这种假设下，假设一共有n个key,表的大小为m,那么每个链条的长度

$α =n/m$

那么一般情况下，运行时间为 O(1+α),因而可以看到在假设的前提之下，使用链表解决hash冲突是个不错的选择

使用open address来解决hash冲突

具体策略为，hash函数包括要计算hash的key和尝试的次数来得到具体的下标

假设经过3次插入数据，h(586,1)=1,h(133,1)=2,h(112,1)=4

再次插入一个数据h(226,1)=4，此时产生了冲突，增加重试的次数，得到h(226,2)=3此时还没有存储值，可以插入

插入：通过给定的hash函数计算下标位置，如果计算出来的下标没有值，或者数据已经删除了，就插入，否则增加尝试的次数，再次计算
搜索：通过hash函数计算得到下标，如果得到的key和要搜索的key不一致，就增加尝试的次数，直到找到或者是计算得到的下标所在处没有值，就停止
删除：首先找到对应的值，此时，仅标记为这个数据已经删除了，但是不把存储的地方置为空

标记的方式用于解决，示例中的，加入删除了112,在查找226的过程中，计算h(226,1)==4，而之前的位置被112占据，如果删除112的时候置为空，那么此时会标记为找不到，很明显不正确，如果仅标记为已经删除则可以解决这个问题，对于带有删除标记的位置，同样可以插入，这样就解决了问题

尝试的策略选择

线性增长。选取h(k,i)=(h'(k)+i)mod m，其中h'(k)为一个可行的hash函数，这种场景下它是能够去遍历所有的存储数组的位置，但是这种方式存在一个问题，随着已经存储的数据越多，需要尝试的次数也就越多，最终插入和搜索将不会是常数时间
double hash。选取 $h(k,i)=(h_1(k)+ih_2(k))mod\space m$ ,当 $h_2$ 和m互为素数的时候，就可以遍历所有的存储数组的位置

这种情况下，需要尝试的次数为 $1/(1-\alpha)，\alpha=n/m$

Hash冲突的一般解决方案与字符串查找中hash的使用

正文