這個HASH類是我在學習《DELPHI算法與數據結構》的時候按照上面的文字和例子重新整理的，就是為了自己看起來比較方便。這個HASH類使用的是線性探測的方式來消除沖突。希望這個HASH類對大家編寫代碼有一定的幫助。同時希望大家在發現代碼中的錯誤或者問題后能給我留言。 {
類名????? ：線性探測HASH表
作者????? ：張超
創建時間? ：2008-07-06
說明????? ：此HASH表使用線性探測方法實現。
修改說明? ：
??????????? 2008-07-06? 創建
測試說明? ：
} unit Hash_Unit;
interface
uses
? RecordList_Unit,Windows; type
? TOnRomveHash??? = procedure(Buf:Pointer) of object; //槽結構
? THashSlot = record
??? FKey? : String;?????? //Hash的Key
??? FItem : Pointer;????? //內容
??? FInUse: Boolean;????? //是否在使用
? end;
? PHashSlot = ^THashSlot; type
? THashClass = class
? private
??? FHashCS:TRTLCriticalSection;
??? FCount:Integer;
??? FTable??? : TRecordList;
??? FOnRomve: TOnRomveHash;
??? function? HashFunc(FKey:String;FTableSize:Integer):Integer;
??? function? IndexOf(FKey:String;var FItem:Pointer):Integer;
??? procedure SetTableSize(FTableSize:Integer);
??? function? GetPrime(N:Integer):Integer;??????????????????????? //得到最接近的質數
??? procedure SetOnRomve(const Value: TOnRomveHash);
? public
??? constructor Create(TableSize:Integer = 1024);
??? destructor Destroy; override; (****方法****)
??? function? Delete(FKey:String):Boolean;
??? function? Find(FKey:String;var FItem:Pointer):Boolean;
??? function? Insert(const FKey:String;FItem:Pointer):Boolean;
??? procedure Clear;
? published
??? property? OnRomve:TOnRomveHash read FOnRomve write SetOnRomve;
??? property? Count:Integer read FCount;
? end; implementation { THashClass } procedure THashClass.Clear;
var
? Inx : integer;
begin
? EnterCriticalSection(FHashCS);
? try
??? if FCount<>0 then
??? begin
????? for Inx := 0 to pred(FTable.Count) do
????? begin
??????? if PHashSlot(FTable[Inx])^.FInUse then
??????? begin
????????? PHashSlot(FTable[Inx])^.FKey:='';
????????? //拋出清空Hash中有數據的槽事件
????????? if Assigned(OnRomve) then
????????? begin
??????????? OnRomve(PHashSlot(FTable[Inx])^.FItem);
????????? end;
??????? end;
??????? PHashSlot(FTable[Inx])^.FInUse:=false;
????? end;
????? FCount := 0;
??? end;
? finally
??? LeaveCriticalSection(FHashCS);
? end;
end; constructor THashClass.Create(TableSize:Integer);
begin
? InitializeCriticalSection(FHashCS);
? FTable:=TRecordList.Create(SizeOf(THashSlot));
? FTable.Name:='';
? FTable.Count:=GetPrime(TableSize);
end; function THashClass.Delete(FKey: String):Boolean;
var
? Inx:Integer;
? ItemSlot : Pointer;
? Slot : PHashSlot;
? Key? : string;
? Item : pointer;
begin
? EnterCriticalSection(FHashCS);
? try
??? Result:=true;
??? Inx := IndexOf(FKey, ItemSlot);
??? if (Inx = -1) then
??? begin
????? //沒有找到
????? Result:=false;
????? Exit;
??? end;
??? //Dispose(PHashSlot(ItemSlot).FItem);
??? PHashSlot(ItemSlot).FInUse:=False;
??? PHashSlot(ItemSlot).FKey:='';
??? dec(FCount);
??? inc(Inx);
??? if (Inx = FTable.Count) then
??? begin
????? Inx := 0;
??? end;
??? Slot := PHashSlot(FTable[Inx]);
??? while Slot^.FInUse do
??? begin
????? Item := Slot^.FItem;
????? Key := Slot^.FKey;
????? Slot^.FKey := '';
????? Slot^.FInUse := False;
????? dec(FCount);
????? Insert(Key, Item);
????? {move to the next slot}
????? inc(Inx);
????? if (Inx = FTable.Count) then
????? begin
??????? Inx := 0;
????? end;
????? Slot := PHashSlot(FTable[Inx]);
??? end;
? finally
??? LeaveCriticalSection(FHashCS);
? end;
end; destructor THashClass.Destroy;
begin
? if (FTable <> nil) then
? begin
??? Clear;
??? FTable.Destroy;
? end;
? DeleteCriticalSection(FHashCS);
? inherited Destroy;
end; function THashClass.Find(FKey: String; var FItem: Pointer): Boolean;
var
? Slot : Pointer;
begin
? EnterCriticalSection(FHashCS);
? try
??? if IndexOf(FKey,Slot)<>-1 then
??? begin
????? Result:=true;
????? FItem:=PHashSlot(Slot).FItem;
??? end
??? else
??? begin
????? Result:=False;
????? FItem:=nil;
??? end;
? finally
??? LeaveCriticalSection(FHashCS);
? end;
end; function THashClass.GetPrime(N: Integer): Integer;
{$I TDPrimes.inc}
const
? Forever = true;
var
? L, R, M : integer;
? RootN?? : integer;
? IsPrime : boolean;
? DivisorIndex : integer;
begin
? EnterCriticalSection(FHashCS);
? try
??? if (N = 2) then
??? begin
????? Result := N;
????? Exit;
??? end;
??? if Odd(N) then
??? begin
????? Result := N;
??? end
??? else
??? begin
????? Result := succ(N);
??? end;
??? if (Result <= MaxPrime) then
??? begin
????? L := 0;
????? R := pred(PrimeCount);
????? while (L <= R) do
????? begin
??????? M := (L + R) div 2;
??????? if (Result = Primes[M]) then
??????? begin
????????? Exit;
??????? end
??????? else if (Result < Primes[M]) then
??????? begin
????????? R := pred(M);
??????? end
??????? else
??????? begin
????????? L := succ(M);
??????? end;
????? end;
????? Result := Primes[L];
????? Exit;
??? end;
??? if (Result <= (MaxPrime * MaxPrime)) then
??? begin
????? while Forever do
????? begin
??????? RootN := round(Sqrt(Result));
??????? DivisorIndex := 1; {ignore the prime number 2}
??????? IsPrime := true;
??????? while (DivisorIndex < PrimeCount) and (RootN > Primes[DivisorIndex]) do
??????? begin
????????? if ((Result div Primes[DivisorIndex]) * Primes[DivisorIndex] = Result) then
????????? begin
??????????? IsPrime := false;
??????????? Break;
????????? end;
????????? inc(DivisorIndex);
??????? end;
??????? if IsPrime then
??????? begin
????????? Exit;
??????? end;
??????? inc(Result, 2);
????? end;
??? end;
? finally
??? LeaveCriticalSection(FHashCS);
? end;
end; function THashClass.HashFunc(FKey: String; FTableSize: Integer): Integer;
var
? G:Longint;
? I:Integer;
? Hash:Longint;
begin
? Result:=0;
? Hash:=0;
? for I:=0 to Length(FKey) do
? begin
??? Hash:=(Hash shl 4) + Ord(FKey[I]);
??? G:=Hash and $F0000000;
??? if (G<>0) then
??? begin
????? Hash:=Hash xor (G shr 24) xor G;
??? end;
??? Result:=Hash mod FTableSize;
? end;
end; function THashClass.IndexOf(FKey: String; var FItem: Pointer): Integer;
var
? Inx:Integer;
? CurSlot? : PHashSlot;
? FirstInx : integer;
begin
? EnterCriticalSection(FHashCS);
? try
??? //計算此KEY的Index
??? Inx:=HashFunc(FKey,FTable.Count);
??? FirstInx := Inx;
??? while True do
??? begin
????? CurSlot := PHashSlot(FTable[Inx]);
????? if not CurSlot.FInUse then
????? begin
??????? FItem:=CurSlot;
??????? Result:=-1;
??????? Exit;
????? end
????? else
????? begin
??????? if CurSlot^.FKey = FKey then
??????? begin
????????? FItem:=CurSlot;
????????? Result:=Inx;
????????? Exit;
??????? end;
????? end;
????? //沒有找到，需要循環
????? Inc(Inx);
????? if (Inx = FTable.Count) then
????? begin
??????? Inx := 0;
????? end
????? else if (Inx = FirstInx) then
????? begin
??????? FItem := nil;
??????? Result := -1;
??????? Exit;
????? end;
??? end;
? finally
??? LeaveCriticalSection(FHashCS);
? end;
end; function THashClass.Insert(const FKey: String; FItem: Pointer):Boolean;
var
? Slot:Pointer;
begin
? EnterCriticalSection(FHashCS);
? try
??? //加入HASH表中
??? Result:=true;
??? if IndexOf(FKey,Slot)<>-1 then
??? begin
????? //已經存在
????? Result:=false;
????? Exit;
??? end;
??? if Slot = nil then
??? begin
????? //Hash表已經滿了
????? Result:=false;
????? Exit;
??? end;
??? PHashSlot(Slot).FKey:=FKey;
??? PHashSlot(Slot).FItem:=FItem;
??? PHashSlot(Slot).FInUse:=true;
??? Inc(FCount);
??? if FCount * 3 > (FTable.Count * 2) then
??? begin
????? //已經大于2/3需要擴展Hash表
????? SetTableSize(GetPrime(succ(FTable.Count * 2)))
??? end;
? finally
??? LeaveCriticalSection(FHashCS);
? end;
end; procedure THashClass.SetOnRomve(const Value: TOnRomveHash);
begin
? FOnRomve := Value;
end; procedure THashClass.SetTableSize(FTableSize: Integer);
var
? Inx:Integer;
? OldTable:TRecordList;
begin
? OldTable := FTable;
? FTable := TRecordList.Create(sizeof(THashSlot));
? try
??? FTable.Count := FTableSize;
??? FCount := 0;
??? for Inx := 0 to pred(OldTable.Count) do
??? begin
????? with PHashSlot(OldTable[Inx])^ do
????? begin
??????? if FInUse then
??????? begin
????????? Insert(FKey, FItem);
????????? FKey := '';
??????? end;
????? end;
??? end;
? except
??? FTable.Free;
??? FTable := OldTable;
??? raise;
? end;
? OldTable.Free;
end; end.

總結

以上是生活随笔為你收集整理的一个自己整理的HASH类的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。