[分享] 闲聊哈希表（下）

richiefang 2010-3-16 20:56 楼主

前期链接：
上篇：https://bbs.eeworld.com.cn/thread-97607-1-3.html
中篇：https://bbs.eeworld.com.cn/thread-97778-1-3.html

　　上回我们说到，在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表这一种。

回复评论（6）

沙发 richiefang

给大家出道课后作业题：
背景是防火墙的工程设计。
防火墙对数据的处理，是按照以下的六元组（6-tuple）：
unsigned long src_addr; /* 源IP(Source Address) */
unsigned long dst_addr; /* 目的IP(Destination Address) */
unsigned short src_port; /* 源端口(Source Port) */
unsigned short dst_port; /* 目的端口(Destination Port) */
unsigned char inet_proto; /* 协议号(Protocol) */
unsigned char zone_token; /* 域描述符(Zone Token) */

对于每个六元组，建立一个会话(session)。为了让查找快捷，一般使用Hash表存储Session，因此，Hash函数的设计很重要。如果设计得不好，容易冲突，会导致防火墙的包转发率(Throughput)和新建连接速率(Connection Setup Rate)这两个重要指标严重降低。今天的作业就是，为防火墙设计一个输入为六元组，输出为32bit的一个Hash函数。

提示一下，防火墙经常用于什么地方呢？经常用于一个内部网络的出口，也就是说，Source Address的高位变化较少。
在网络中，80%以上的流量属于HTTP，目的端口为80，也就是说，Destination Port变化比较少。
在网络中，90%以上的流量为TCP(0x06)和UDP(0x11)，其他的很少。

有了以上几点提示，大家一定可以设计一个比较好的hash函数。
嗯，最接近我做的实现的，奖励50芯币～

点赞 2010-3-16 21:08