贾永胜

（石家庄职业技术学院 信息工程系，河北 石家庄 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 冲突的处理方法

如果有两个或……