闲聊哈希表 （下）
作者 帅云霓 | 2010-03-07 11:53 | 类型 专题分析 | 11条用户评论 »
|
上回我们说到，在Hash表的建立时，会发生Hash值冲突的情况。实际上，如果记录Hash值的范围多于Hash表的条数，根据抽屉原理，一定会发生冲突。对于冲突的处理，我们一般有这几种方法： 1， 对Hash表中每个Hash值建立一个冲突表，即将冲突的几个记录以表的形式存储在其中； 2， 改变规则重新计算一次Hash值； 3， 建立一个公用的区域存放冲突的表项； 在工程上，考虑到实现算法的复杂度，方法1用得是最多的。对于方法1，又有两种不同的实现，一种方法是对每个Hash值，建立一个Hash桶(Bucket)，桶的容量是固定的，也就是只能处理固定次数的冲突，如1048576个Hash桶，每个桶中有4个表项(Entry)，总计4M个表项。另一种方法是，不限制Hash桶的容量，以链表形式将冲突的记录挂接在一个Hash桶中。 这两种实现各有什么利弊呢？首先，让我们看看第一种实现： 在这种情况下，由于Hash桶容量的限制，所以，有可能发生Hash表填不满的情况，也就是，虽然Hash表里面还有空位，但是新建的表项由于冲突过多，而不能装入Hash表中。不过，这样的实现也有其好处，就是查表的最大开销是可以确定的，因为最多处理的冲突数是确定的，所以算法的时间复杂度为O(1)+O(m)，其中m为Hash桶容量。 而另一种实现，由于Hash桶的容量是无限的，因此，只要没有超出Hash表的最大容量，就能够容纳新建的表项。但是，一旦发生了Hash冲突严重的情况，就会造成Hash桶的链表过长，大大降低查找效率。在最坏的情况下，时间复杂度退化为O(n)，其中n为Hash表的总容量。当然，这种情况的概率小之又小，几乎是可以忽略的。 Hash表的一个应用例子，是在网关(Gateway)中。以网络防火墙为例，它是根据源IP，目的IP，源端口，目的端口，协议号构成的五元组来标识一条网络数据流的，并且根据五元组来建立会话表项(session entry)。为了查找便捷，一般都使用Hash表来实现这个会话表，以提高转发的效率。事实上，对于大量表项的查找，逐项查找是不允许的，一般都使用Hash表来实现。不夸张的说，我们可以说，在你生活的每一天，都免不了同Hash表打交道，比如，查字典。 最后，我想说，数据结构的万紫千红中，我独爱Hash表这一种。 | |
 (4个打分， 平均：5.00 / 5) |
雁过留声
“闲聊哈希表 （下）”有11个回复
这三篇看起来真像是混积分的
咔咔。反正我期盼帅帅下面的文章是：Atom vs Arm系列，而非来个闲聊二叉树的广度优先算法。。。厚积薄发。帅帅，你能行。You can do it.
其实HASH本来是一个很有技术含量的话题的….
建议弯曲的文章分类可以更细一点
为什么我这么喜欢线性表呢
线性表 cache miss 少？
不知道有哪家的产品里flow table不是用哈希表实现的。比如在某些允许flase positive的情况下用bloom filter实现，应该可以省不少memory
开源的Packet Filter(PF)使用Tree来实现，虽然可以BOUND住最坏性能，但是性能不好，特别是插入和删除的时候，会严重pollution cache。
#5, 为什么我这么喜欢线性表呢
如何构建一百万个TCP flow 的线性表哪？
表中每一个项至少有：(S_IP, D_IP, S_port, D_port) 四元组.
1000w个随机五元组hash到23个bit位宽，二次hash到11bit，桶深32，冲突率怎么算呢？-,- 概率没学好。
深入浅出