除留余数法建立哈希表的方法改进.pdfVIP

第24卷第7期 甘肃科技 v0Z．24No．7 2008年4月 GansuScienceand A声r． 2008 Technology 除留余数法建立哈希表的方法改进 贺元香，史宝明 (1．甘肃联合大学理工学院，甘肃兰州730000；2．甘肃联合大学数学与信息学院，甘肃兰州730000) 摘要：查找是从大量的数据中得到所需信息经常要进行的工作。为了更好的查找，在存人数据时一种常用而有效 的方法是用除留余数法来建立哈希表，用线性探测法处理冲突。目前，大部分书籍上在建立哈希表时都是一边存 储，一边解决冲突。该方法由于哈希表中存在的“堆积”现象，大大降低了查找效率，并且从思想上来看，没有很好的 符合哈希法的初衷，是不顾后效的。文章对该方法做了改进，有效的克服了该方法的缺点。 关键词：哈希表；查找；冲突；队列 中图分类号：TP301．6 在英汉字典中查找某个英文单词的中文解释， 对于n个数据元素的集合，总能找到关键码K 在新华字典中查找某个汉字的读音、含义，在对数 与存放地址一一对应的函数f(K)。若最大关键码 表、平方根表中查找某个数的对数、平方根，以及邮 为m，可以分配m个存放数据元素的单元，选取函 递员送信件要按收件人的地址确定位置等等。可以 数f(K)一K即可，但这样会造成存储空间的很大浪 说查找是为了从大量的数据中得到所需信息经常要 费，甚至不可能分配这么大的存储空间。通常关键 进行的工作。 码的集合比哈希地址集合大得多，因而经过哈希函 计算机及网络使信息查询更快捷、方便、准确。 数变换后，可能将不同的关键码映射到同一个哈希 要从计算机及网络中查找特定的信息，就需要在计 地址上，这种现象称为冲突(Collision)，映射到同一 算机中存储包含该特定信息的表。如要从计算机中 哈希地址上的关键码称为同义词。可以说，冲突不 查找英文单词的中文解释，就需要存储类似英汉字 可能避免，只能尽可能减少。所以，哈希方法需要解 典这样的信息表，以及对该表进行的查找操作。本 决以下两个问题： 文将讨论的即是“信息的存储和查找”方面的问题。 (1)构造好的哈希函数 *所选函数尽可能简单，以便提高转换速度。 1 概念 *所选函数对关键码计算出的地址，应在哈希 查找是许多程序中最消耗时间的一部分。因 地址集中大致均匀分布，以减少空间浪费。 而，一种好的查找方法会大大提高运行速度。 (2)制定有效的解决冲突的方案。 查找效率依赖于查找过程所进行的比较次数。 在我们接触到的算法中，设查找表总长为n，一般要 2除留余数法建立哈希表 找到所需元素，大部分都得比较n／2次以上。而当 下面讨论常用而有效的方法——除留余数法来 n趋于一个比较大的值时，这个n／2就不能小瞧了!建立哈希表，用线性探测法处理冲突。 rood 对于查找来说，理想的情况是希望不经过任何 除留余数法：f(K)一KP(P是一个整数) 比较，一次存取便能得到所查记录，那就必须在记录 即取关键码除以P的余数作为哈希地址。使用除留 的存储位置和他的关键字之间建立一个确定的对应 余数法，选取合适的P很重要，若哈希表表长为m， 关系f，使每个关键字和结构中一个唯一的存储位置 则要求p≤m，且接近m或等于rn。P一般选取质 相对应。因而在查找时，只要根据这个对应关系f， 数，也可以是不包含小于20质因子的合数。 找到给定值K的像f(K)。若