阅读 82

什么是散列表(Hash Table)

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

一个通俗的例子是,为了查找电话簿中某人的号码,可以创建一个按照人名首字母顺序排列的表(即建立人名 x 到首字母 F(x) 的一个函数关系),在首字母为W的表中查找“王”姓的电话号码,显然比直接查找就要快得多。这里使用人名作为关键字,“取首字母”是这个例子中散列函数的函数法则F(),存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。

1.基本概念

  • 若关键字为 k,则其值存放在f(k) 的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数,按这个思想建立的表为散列表。
  • 对不同的关键字k可能得到同一散列地址,即 k1≠k2,而f(k1)=f(k2) ,这种现象称为冲突(或碰撞,英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数f(k) 和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。
  • 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

2.构造散列函数的方法

散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快定位。

  • 直接定址法:取关键字或关键字的某个线性函数值为散列地址。即hash(k)=khash(k)=a \cdot k+b, 其中a  b为常数(这种散列函数叫做自身函数)
  • 数字分析法:假设关键字是以r为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。
  • 平方取中法:取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况,取其中的哪几位也不一定合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
  • 折叠法:将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。
  • 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 即 hash(k)=k\,{\bmod {\,}}p , p\leq m。不仅可以对关键字直接取模,也可在折叠法、平方取中法等运算之后取模。对p的选择很重要,一般取素数或m,若p选择不好,容易产生冲突。

3.处理冲突

为了知道冲突产生的相同散列函数地址所对应的关键字,必须选用另外的散列函数,或者对冲突结果进行处理,而不发生冲突的可能性是非常之小的,所以通常对冲突进行处理。常用方法有以下几种:

开放寻址法(open addressing)。想象一下,有一趟对号入座的火车,假设它只有一节车厢,上来一位坐7号座位的旅客。过了一会儿,又上来一位旅客,他买到的是一张假票,也是7号座位,这时怎么办呢?列车长想了想,让拿假票的旅客去坐8号座位。过了一会儿,应该坐8号座位的旅客上来了,列车长对他说8号座位已经有人了,你去坐9号座位吧。哦?9号早就有人了?10号也有人了?那你去坐11号吧。可以想见,越到后来,当空座越来越少时,碰撞的几率就越大,寻找空座愈发地费劲。但是,如果是火车的上座率只有50%或者更少的情况呢?也许真正坐8号座位的乘客永远不会上车,那么让拿假票的乘客坐8号座位就是一个很好的策略了。所以,这是一个空间换时间的游戏。玩好这个游戏的关键是,让旅客分散地坐在车厢里。如何才能做到这一点呢?答案是,对于每位不同的旅客使用不同的探查序列。例如,对于旅客 A,探查座位 7,8,23,56……直到找到一个空位;对于旅客B,探查座位 25,66,77,1,3……直到找到一个空位。如果有 m 个座位,每位旅客可以使用 <0, 1, 2, ..., m-1>m! 个排列中的一个。

显而易见,最好减少两个旅客使用相同的探查序列的情况。也就是说,希望把每位旅客尽量分散地映射到 m! 种探查序列上。换句话说,理想状态下,如果能够让每个上车的旅客,使用 m! 个探查序列中的任意一个的可能性是相同的,我们就说实现了一致散列。(这里没有用“随机”这个词儿,因为实际是不可能随机取一个探查序列的,因为在查找这名旅客时还要使用相同的探查序列)。

线性探查:最简单的方法是,如果发现 values[8] 已经被占用了,就看看 values[9] 是否空着,如果 values[9] 也被占用了,就看看 values[0] 是不是还空着。完整的描述是,先使用 H() 函数获取 k 的第一个地址,如果这个地址已被占用,就探查下一个紧挨着的地址,如果还是不能用,就探查下一个紧挨着的地址,如果到达了数组的末尾,就卷绕到数组的开头,如果探查了 m 次还是没有找到空槽,就说明数组已经满了,这就是线性探查(linear probing)

真正的一致散列是难以实现的,实践中,常常采用它的一些近似方法。常用的产生探查序列的方法有:线性探查,平方探测,以及双重散列探查。这些方法都不能实现一致散列,因为它们能产生的不同探查序列数都不超过 m^2 个(一致散列要求有 m! 个探查序列)。在这三种方法中,双重散列能产生的探查序列数最多,因而能给出最好的结果。

显示线性探测填装一个散列表的过程:

关键字为{89,18,49,58,69}插入到一个散列表中的情况。此时线性探测的方法是取 d_{i}=i。并假定取关键字除以10的余数为散列函数法则。

第一次冲突发生在填装49的时候。地址为9的单元已经填装了89这个关键字,所以取 i=1,往下查找一个单位,发现为空,所以将49填装在地址为0的空单元。

第二次冲突则发生在58上,取i=3,往下查找3个单位,将58填装在地址为1的空单元。69同理。 表的大小选取至关重要,此处选取10作为大小,发生冲突的几率就比选择质数11作为大小的可能性大。越是质数,mod取余就越可能均匀分布在表的各处。

聚集(Cluster,也翻译做“堆积”)的意思是,在函数地址的表中,散列函数的结果不均匀地占据表的单元,形成区块,造成线性探测产生一次聚集(primary clustering)和平方探测的二次聚集(secondary clustering),散列到区块中的任何关键字需要查找多次试选单元才能插入表中,解决冲突,造成时间浪费。对于开放定址法,聚集会造成性能的灾难性损失,是必须避免的。

关注下面的标签,发现更多相似文章
评论