哈希表的问题 (100分)

  • 主题发起人 主题发起人 kun
  • 开始时间 开始时间
K

kun

Unregistered / Unconfirmed
GUEST, unregistred user!
在单元IniFiles中:
function TStringHash.HashOf(const Key: string): Cardinal;
var
I: Integer;
begin
Result := 0;
for I := 1 to Length(Key)do
Result := ((Result shl 2) or (Result shr (SizeOf(Result) * 8 - 2))) xor
Ord(Key);
end;
function TStringHash.Find(const Key: string): PPHashItem;
var
Hash: Integer;
begin
Hash := HashOf(Key) mod Cardinal(Length(Buckets));
Result := @Buckets[Hash];
while Result^ <> nildo
begin
if Result^.Key = Key then
Exit
else
Result := @Result^.Next;
end;
end;

如果key相同,那找回来的value就可能不是我想要找的了。
 
procedure TStringHash.Add(const Key: string;
Value: Integer);
var
Hash: Integer;
Bucket: PHashItem;
begin
Hash := HashOf(Key) mod Cardinal(Length(Buckets));
New(Bucket);
Bucket^.Key := Key;
Bucket^.Value := Value;
Bucket^.Next := Buckets[Hash];
Buckets[Hash] := Bucket;
end;
这个链表有什么用?
Bucket^.Next := Buckets[Hash];
Buckets[Hash] := Bucket;
这两句是作什么用的?
 
这是用“链地址法”处理哈希冲突的方法。
“如果key相同,那找回来的value就可能不是我想要找的了。 ”
非也,非也,代码并不是找到hash值就算了,而是沿着hash函数指向的链,直到找到目标为止。有诗为证:
while Result^ <> nildo
begin
if Result^.Key = Key then
Exit
else
Result := @Result^.Next;
end;
(偶猜楼主可能误会了key的意思,这里的变量key是要找的值,而变量hash才是楼主理解的'key')。
“这个链表有什么用?
Bucket^.Next := Buckets[Hash];
Buckets[Hash] := Bucket;
这两句是作什么用的?”
这里的做用是将新插入的key放置在key对应的hash值指向的队列的对首。
 
后退
顶部