admin管理员组文章数量:1565813
2024年7月25日发(作者:)
哈希函数
1 基本原理
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数, 也叫做散列函
数),使得每个元素的关键字都与一个函数值(即数组下标)相对应,于是用这个数组单元来存储这个
元素;也可以简单的理解为,按照关键字为每一个元素"分类",然后将这个元素存储在相应"类"所对
应的地方。
但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,
却计算出了相同的函数值,这样就产生了"冲突",换句话说,就是把不同的元素分在了相同的"类"之
中。后面我们将看到一种解决"冲突"的简便做法。
总的来说,"直接定址"与"解决冲突"是哈希表的两大特点。
2 函数构造
构造函数的常用方法(下面为了叙述简洁,设 h(k) 表示关键字为 k 的元素所对应的函数值):
a) 除余法:
选择一个适当的正整数 p ,令 h(k ) = k mod p
这里, p 如果选取的是比较大的素数,效果比较好。而且此法非常容易实现,因此是最常用的
方法。
b) 数字选择法:
如果关键字的位数比较多,超过长整型范围而无法直接运算,可以选择其中数字分布比较均匀的
若干位,所组成的新的值作为关键字或者直接作为函数值。
3 冲突处理
线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ,则当 h(k) 已经存储
了元素的时候,依次探查 (h(k)+i) mod S , i=1,2,3…… ,直到找到空的存储单元为止(或者从头到尾
扫描一圈仍未发现空单元,这就是哈希表已经满了,发生了错误。当然这是可以通过扩大数组范围避
免的)。
4 支持运算
哈希表支持的运算主要有:初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查
找元素(member)。
设插入的元素的关键字为 x ,A 为存储的数组。
初始化比较容易,例如
const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素
p=9997; // 表的大小
procedure makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[i]:=empty;
End;
哈希函数值的运算根据函数的不同而变化,例如除余法的一个例子:
function h(x:longint):Integer;
begin
h:= x mod p;
end;
我们注意到,插入和查找首先都需要对这个元素定位,即如果这个元素若存在,它应该存储在什
么位置,因此加入一个定位的函数 locate
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (ix)and(A[(orig+i)mod S]<>empty) do
版权声明:本文标题:哈希函数 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1721865255a901905.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论