一种减少哈希冲突的哈希查找方法 技术领域

本发明属于査找算法领域，具体涉及一种哈希 查找方法，尤其涉及一 种减少哈希冲突的哈希查找方法。

背景技术

哈希表是种数据结构，它可以提供快速的插入 操作和查找操作。哈希 表（Hash table, 也叫散列表）， 是根据关键码值 (Key value)而直接迸行 访问的数据结构。也就是说，它通过把关键码 值映射到表中一个位置来访 问记录， 以加快査找的速度。这个映射函数叫做哈希函 数（或散列函数)， 存放记录的数组叫做哈希表（或散列表）。 所有哈希函数都有如下一个基 本特性： 如果两个哈希值是不相同的 （根据同一函数)， 那么这两个哈希 值的原始输入也是不相同的。这个特性使哈希 函数具有确定性的结果。但 另一方面，哈希函数的输入和输出不是一一对 应的，如果两个哈希值相同， 两个输入值很可能是相同的，但并不能绝对肯 定二者一定相等。对不同的 关键字可能得到同一哈希值， 即 keyl≠key2，而 f (keyl)=f (key2)， 这种 现象称为哈希冲突。

哈希査找是通过计算数据元素的存储地址迸行 查找的一种方法。 传统的哈希查找方法的操作步骤为： ω用给定的哈希函数构造哈希 表； （2〉根据选择的冲突处理方法解决地址冲突� � （3)在哈希表的基础上 执行哈希查找。 传统的建立哈希表的操作步骤为：

1.取数据元素的关键字 key, 计算其哈希函数值（地址） 。 若该 地址对应的存储空间还没有被占用， 则将该元素存入； 否则执行步骤 2解决沖突。

2.根据选择的冲突处理方法，计算关键字 key的下一个存储地址。 若下一个存储地址仍被占用， 则继续执行步骤 2, 直到找到能用的存 储地址为止。

传统的哈希査找步骤为：

1.设哈希表为 HST [0~M- 1]， 哈希函数取 H ( key) ， 解决冲突的 方法为 R ( X ) ；

2.对给定 k值， 计算哈希地址 Di=H (k) ； 若 HST为空， 则查找 失败； 若 HST=k， 则查找成功； 否则， 执行步骤 3 (处理冲突） 。

3.重复计算处理沖突的下一个存储地址 Dk=R ( Dk-1 ) ， 直到 HST [Dk]为空， 或 HST [Dk]=k为止。若 HST [Dk]二 K, 则查找成功， 否则 查找失败。

虽然我们不希望发生哈希沖突，但实际上发生 冲突的可能性仍是存在 的。当关键字值域远大于哈希表的长度，而且 事先并不知道关键字的具体 取值时， 哈希冲突就难免会发生。

发明内容

本发明要解决的技术问题是提供一种减少哈希 冲突的哈希查找方法， 该方法可以有效地降低发生哈希冲突的概率。

为解决上述技术问题， 本发明提供一种减少哈希冲突的哈希查找方 法， 包括如下步骤：

( 1 )增加一个 index表， 采用 rule表结合 index表的方法， 并将 index表项大小扩大为 rule表项的 2倍 （即该 index表项大小扩大为 rule表中 rule数量 N的 2倍， 使哈希函数的结果扩大了一倍） ；

(2) rule表中将 rule分为 N个桶， 每个桶包含 m个 rule; index 表的内容是！ "ule所在的桶的索引；

( 3)在以上改进后的哈希表的基础上执行哈希查� ��。

步骤 （3) 中， 添加一条 rule的步骤如下：

A.根据哈希函数得到的哈希值， 索引 index表， 得到桶的地址；

B.然后在该桶内的空闲位置写入 _rU le。 所述桶内的空闲位置的有效 标识位 V为 0， 写入 rule后将有效标识位 V值置为 1。

步骤 （3) 中， 查找一条 rule的步骤如下：

A.根据哈希函数得到哈希值， 索引 index表；

B.通过查 index表，得到桶的索引，如果该索引是个无效� ��， 则表示 rule表里无命中项， 结束査找； 否则进入步骤 C;

C.根据得到的桶索引， 继续索引 rule表， 找到指定的桶后， 在该桶 里的有效标识位 V为 1的若干条 rule里进行查找， 最后得到査找结果。

和现有技术相比，本发明具有以下有益效果： 跟传统的哈希査找方法 相比， 本发明将 rule表的结构进行了调整， 并增加了一个 index表， 引 入 bucket (桶） 的思想， 分级查找， 使得哈希冲突的可能性大大降低， 同时将哈希函数的结果扩大为实际 rule数目的 2倍， 更加降低发生哈希 冲突的概率。 附图说明

图 1是本发明方法的示意图。

具体实施方式

下面结合附图和实施例对本发明作进一步详细 的说明。

如图 1所示，本发明在现有的 rule表基础上增加一个 index表，采 用 rule表结合 index表的方法， 且对 rule表的结构做一下调整， 将 ra 个规则 (rule)分在一个桶（bucket)内，所有 rule分为 N/m个桶。除了 rule 表之外， 霈要另增加一个 index (索引）表， index表的内容是 rule所在 的桶的索引， 这样査找时进行两次索引就可以得到结果。 同时， 将 index 表项大小扩大为 rule表的 2倍，即 rule表为 INCrule的数量）， index表 为 2N (rule数量的 2倍）， 使得哈希函数的结果扩大了一倍， 可以更加有 效的降低哈希冲突的概率。 '

下面举一实施例详细说明本发明哈希查找方法 的实施步骤（见图 1 ): 在 rule表中添加 rule, 具体步骤如下：

1.根据哈希函数得到的哈希值 K， 索引 index表， 得到 bucket的 ID (地址）;

2.然后在该 bucket内的空闲位置（图 1中有效标识位 V为 0)， 写入 rule, 并将有效标识位 V值置为 1。

哈希查找过程如下：

1.根据哈希函数得到哈希值 K， 索引 index表；

2.通过查 index表， 得到 bucket的索引， 如果该索引是个无效值， 则表示 rule表里无命中项， 结束査找； 否则进入下一步步骤 3; 3.根据得到的 bucket索引， 继续索引 rule表， 找到指定的 bucket 后,接下来在该 bucket里的有效标 i只位 V为 1的若干条 rule里进行查找， 最后得到査找结果。

由上述实施例可见， 本发明增加了一个 index表， 釆用 mle表结合 index表的方法， 且引入 bucket (桶）的思想， 分级査找， 使得哈希冲突 的可能性大大降低，同时将哈希函数的结果扩 大为实际 rule数目的 2倍， 更加降低发生哈希冲突的概率。