数据结构之哈稀表

数据结构之哈稀表

前言

哈稀表在工作中常用,语言都内置有,对应于字典或者对象。
首先得定义一些操作。我有一组数据,每个数据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)

发表评论

电子邮件地址不会被公开。 必填项已用*标注