数据结构之哈稀表
数据结构之哈稀表
前言
哈稀表在工作中常用，语言都内置有，对应于字典或者对象。
首先得定义一些操作。我有一组数据，每个数据x有key=>value这样的结构。
操作1, 插入一对新的x到这个集合中。
操作2，删除这个集合中的x.
操作3，搜索这个集合中key为k的x。
最简单的实现
直接映射表。
要求这些x的key是在有限集合中，并且是不重复的，如U = {0,1,…m-1}
你只需要建立一个数组，key为索引,值为value就可以了。
但他的问题是可能m很大，但要操作的数据很小，这样这个数组就会很稀。
哈稀的引入
所谓的哈稀法，就是用一个哈希函数H来随机映射那些键。
其实就是针对上面直接映射表的。即然key的集合很大，那我就通过一个函数把这个key的集合映射到一个比较小的集合上。
但这会引入另一个问题，从大集合到小集合，一定存在着多个key映射到同一个值的情况。这被称为碰撞。
链表法解决碰撞
解决办法就是在新的小集合上，new-key存放的并不是x,而是一个存放有x的链表。当要查找时，就遍历这个链表，对比key和x.key即可。
但这种实现在最坏情况下访问效率很低。
最坏情况是所有key映射到同样的一个new-key,这时候就只剩下一个链表了，查找效率是(\theta(n))
从这可看出哈希的关键是选取恰当哈希函数H, 使得key能均匀地哈希到new-key。
装载因子>1, 即平均每个槽放的元素>1.
开放寻址法解决碰撞
这种方案不是使用链表，而是在第一次哈希后，如果遇到碰撞则再哈希一次看看，如此形成一个哈希序列，也叫探查序列。
好处是不需要增加额外的数据结构，不需要修改元素。缺点是删除不好处理，如果直接删除，则原来因为碰撞而需要再次探查的数据会误以为元素不在哈希表中。
装载因子(\alpha)<1, 即平均每个槽放的元素<1.预期探查次数是( \frac{1}{1-\alpha} )
探查序列有两种方案。
线性方法
[h(k, i) = (h(k, 0) + i)\ mod\ m]
h(k, i)表示对k的第i次探查。
这种方法简单，但是容易遇到集群现象，即当碰撞时，会在局部集中有值。
二次哈希
这种在实践中比较实用。
[h(k ,i) = (h_1(k) + i * h_2(k))\ mod\ m]
其中(m= 2^r), h_2(k) 为奇数。
哈希函数的选择
除法
h(k) – k mod m (m是新集合的大小)
这里m不能太小，最好是质数。
乘法
m是(2^r)， 机器字长为w。
[h(k) = (A*k\ mod\ 2^w)\ rsh\ (w-r)]
A为介于(2^{w-1})到(2^w)之间的某个奇数。 rsh表示右移操作。
因为CPU有指令直接可以得到两个w相乘后的低w位，mod和rsh都是位移操作。所以这个算法相对上面的除法效率要高。
高级主题
哈希的问题
因为哈希是从一个大的集合哈希到一个小的集合，那么对于任意一个哈希函数来说，
都存在一个不好的key集合，都会哈希到同一个槽。
全域哈希
为了解决上面的问题，我们从哈希函数的集合中采取随机的哈希函数，这就叫做全域哈希。这里要求选取随机哈希函数的有限集有一个规律：当从中随机选择两个哈希函数时，他们哈希到同一个槽的概率是1/m。
做法
这里有个前提，选择槽数m为质数。
把key按m进制表示为(<k_0, k_1, …k_r>).
再随机选择一个数a, 也按m进制表示为(<a_0, a_1, a_2…a_r>)
定义(h_a(k) = (\sum_{i=0}^{r}a_iK_i)\ mod \ m)
完全哈希
完全哈希是用来处理静态哈希表。
有两个要求：
1. m = O(n)
2. 在最坏情况下查找的时间效率是O(1)
做法
用二级结构。并且每级结构都用全域哈希。
假设在第一级第i个槽有(n_i)个元素发生碰撞，则二级结构的大小是(n_i^2)
About The Author
bjmayor
程序员，码农，php,python,ios,android,go，产品经理，创业。