【对武林、完美中怪物ID以及很多处用到的hash运算,请一起探讨】
我也不太明白。我找了一些资料看起来比较清晰。我会不断补充我对他的理解和看法。希望大家都指教一下哈希表支持的运算主要有:初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。
========================初始化(makenull)========================
设插入的元素的关键字为 x ,A 为存储的数组。
初始化比较容易,例如
const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素
p=9997; // 表的大小
procedure makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[ i ]:=empty;
End;
========================函数值的运算(h(x))========================
function h(x:longint):Integer;
begin
h:= x mod p;
end;
========================定位函数 locate========================
我们注意到,插入和查找首先都需要对这个元素定位,即如果这个元素若存在,它应该存储在什么位置,因此加入一个定位的函数 locate
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do
inc(i);
//当这个循环停下来时,要么找到一个空的存储单元,要么找到这个元
//素存储的单元,要么表已经满了
locate:=(orig+i) mod S;
end;
=====================插入元素========================
procedure insert(x:longint);
var posi:integer;
begin
posi:=locate(x); //定位函数的返回值
if A=empty then A:=x
else error; //error 即为发生了错误,当然这是可以避免的
end;
========================查找元素========================
查找元素是否已经在表中
procedure member(x:longint):boolean;
var posi:integer;
begin
posi:=locate(x);
if A=x then member:=true
else member:=false;
end; 散列表的最主要的东西就是散列函数的选择,大多数使用的都是取模运算,也可以根据表中要存储的元素的特征自己去设计散列函数,
还有就是使用散列的根本用意就是速度,所以这里不要使用数组,用双链表实现,如果闲烦,你也可以使用TList去实现,都比数组要快. 能告诉我下完美国际的怪物数组是怎么找到的吗?
页:
[1]