散列表及其冲突处理方法的性能分析

贾永胜

（石家庄职业技术学院 信息工程系，河北 石家庄 050081）

散列表也称作哈希表，是根据记录的关键字（key）进行直地址运算，进而进行数据访问的一种数据结构.散列表地址转换的基本思路为：定义一个记录的关键字与地址之间的一种映射关系，通过这个映射关系，根据关键字直接计算出记录的地址.通常，记录关键字用key表示，用h表示关键字和记录地址间的函数关系，即为散列函数，记录的地址用h（key）表示［1］.本文主要介绍散列函数的构造方法、冲突处理方法及查找性能.

1 散列函数的构造方法

散列函数多种多样，应力争寻找一个这样的散列函数：该函数能使关键字在整个地址范围内分布比较均匀.常用的散列函数构造方法有：

（1）直接法

对关键字进行简单线性运算，将结果作为记录的地址.例如h（key）＝a＊key＋b，其中a，b是常数.这种方法获得的地址序列不发生地址冲突，计算简单，但得到的地址序列很分散，地址范围较广.

（2）折叠法

如果记录的关键字的位数较多，可将关键字划分成等位数的多段（最后一段除外），再将这多段进行简单的四则运算.例如｛12345678｝，可进行如下计算：

由此，可算出该关键字的散列地址为657.

（3）平方取中法

对关键字求平方，在所得结果中连续取若干位，位数由散列表的长度决定.例如key＝1234，key2＝1522756，取中间的三位227作为地址码.

（4）求余法

将关键字除以某个常数得到其余数，把该余数作为记录的地址h（key）＝key%c，常数c一般小于散列表的总长度.

2 冲突的处理方法

如果有两个或多个关键字使用同一个散列函数计算得到的地址为一个，即key1≠key2，但h（key1）＝h（key2），即为发生冲突.发生冲突的几个关键字通常称为同义词.在进行散列函数构造时，应尽量避免产生冲突，但实际上不发生冲突很难.本文给出两种冲突处理的常用方法，即拉链法和开放定址法［2］.

（1）拉链法

拉链法的基本思路是：将同义词存储在一个公共的线性链表中，把这个链表称为同义词链表；另外定义一个顺序表，里面记录各同义词在链表里的头指针.例如，关键字｛1，2，3，4，5，6，7，8｝，函数为h（key）＝key%4，用拉链法处理冲突时的散列表如图1所示.

图1 拉链法处理冲突散列表

（2）开放定址法

①线性探测法

线性探测法的原理是：将散列表t［0..Max－1］看成一个循环向量，首先试探地址h（key）＝d是否可用.若不可用，则按下列地址探查：d＋1，d＋2，…，Max－1，0，1，…，d－1.即探查时从地址d开始，首先探查t［d］，然后依次探查t［d＋1］，…，t［Max－1］，此后又循环到t［0］，t［1］，…，t［d－1］.按线性探测法进行插入操作时，先看当前被探查的单元是否为空.如果为空，就将关键字key写入这个空单元；若不空，则按上述规则依次继续向后探查，直到遇到空单元插入关键字为止，如果测试到t［d－1］时还没有找到空单元，说明表已满，插入失败.进行查找操作时，若当前正在探查的单元内的关键字为k，表示成功查找到记录；若不等于k，则继续按顺序向后探查，直至发现关键字为k的记录即为查找成功；若探查到t［d－1］时，还没有等于k的关键字，则查找失败.例如，序列｛91，123，149，183，230，6，20｝，表长为14，散列函数h（x）＝x%14，散列表如图2所示.

图2 线性探测法的散列表

②二次探测法

从线性探测法可知，可能第i个同义词存入了第i＋1个同义词对应的散列地址中，本应存入第i＋1个散列地址的元素只能存到第i＋2个记录的地址中……因此，可能有很多元素在其相邻的地址中存储，这就必然使每一个关键字的冲突几率增高，大大降低查找效率.为此，可采用二次探测法，以改善上述的“堆积”问题.

二次探测法的基本思想是：跳跃式生成探测地址序列，其计算公式为：di＝（h（key）＋i2）mod Max，0≤i≤Max－1，即探查的序列为：d＝h（key），d＋1，d＋4，d＋9….也就是说，探查从地址d开始，先探查t［d］，然后依次探查t［d＋1］，t［d＋4］，t［d＋9］….例如，序列｛91，123，149，183，230，6，20｝的表长为14.插入6时，有散列函数h（6）＝6%14＝6，地址6中已经有关键字230，冲突；套用上式得h＝（6＋1）%14＝7，地址7中也存在关键字91，冲突；继续套用h＝（6＋4）%14＝10，而地址10空闲，则将6插入到地址10中，其散列表如图3所示.

图3 二次探测法

3 散列表的查找及分析

散列表的查找过程和散列表的构造过程相似，一部分记录的地址可直接经关键字运算得到，另一部分关键字在地址运算时会发生冲突，需要选择一种冲突处理方法进行地址查找.在冲突处理的方法中，查找的总体思路是用给定值与关键字进行比较.所以，可用平均查找长度（ASL）来衡量散列表查找的效率［3］.关键字的比较次数与产生冲突的多少息息相关，产生的冲突和查找次数越少，效率越高；产生的冲突越多，查找效率就越低.因此，查找效率实际上是由产生冲突的影响因素决定的.通常，影响冲突产生次数的因素有三个：散列函数是否均匀、处理冲突方法的好坏和散列表的装填因子α的情况.散列表的装填因子定义为：

这三个因素中，尽管散列函数的“优劣”会直接影响冲突产生的频度，但在一般情况下，可认为散列函数“均匀”分布，可以忽略散列函数对平均查找长度产生的影响.分别用线性探测法和二次探测法来进行冲突处理发现，即使关键字集合和散列函数均相同，在查找概率相同的情况下，它们的平均查找长度仍有所不同.采用线性探测法的平均查找长度ASL＝（5×1＋3×1＋1×5）／7＝13／7，采用二次探测法的平均查找长度ASL＝（5×1＋3×1＋1×4）／7＝12／7.由于表长是定值，α与填入表中的元素个数成正比，所以，α越大，填入表中的元素越多，产生冲突的可能性就越大；α越小，填入表中的元素越少，产生冲突的可能性就越小.

事实上，散列表的ASL通常是装填因子α的函数.只是处理冲突的方法不同，函数也不同.不同处理冲突方法的平均查找长度见表1.

此方法的存取速度较快，空间复杂度也不高，但由于存取是随机的，不便于顺序查找.

表1 不同方法构造散列表的平均查找长度

［1］严蔚敏，吴伟民.数据结构：C语言版 ［M］.北京：清华大学出版社，1997：237.

［2］郭芳，曹桂琴.数据结构基础：第5版 ［M］.大连：大连理工大学出版社，2004：210.

［3］张世和.数据结构 ［M］.北京：清华大学出版社，2000：258.