Delphi中的THashTable

原作者: [db:作者] 来自: [db:来源] 收藏邀请

在Delphi中,Inifiles单元中有一个TStringHash的类，不过它的Value仅支持Integer(其实也不是问题，有其它类型可以将变量变为Pointer)，有点不舒服，今天没事做就把它替换为variant了，其中Key的名称大小写无关，就是为了加快开发速度！

使用Hashtable,查找和删除复杂度都是常数级别的!

type
  PPHashItem = ^PHashItem;
  PHashItem = ^THashItem;
  THashItem = record
    Next: PHashItem;
    Key: String;
    Value: Variant;
  end;
  THashTable = class
  private
    Buckets: array of PHashItem;
  protected
    function Find(const Key: String): PPHashItem;
    function HashOf(const Key: String): Cardinal; virtual;
  public
    constructor Create(Size: Cardinal = 256);
    destructor Destroy; override;
    procedure Put(const Key: String; Value: Variant);
    procedure Clear;
    procedure Remove(const Key: String);
    function Modify(const Key: String; Value: Variant): Boolean;
    function Get(const Key: String): Variant;
    function ContainKey(const Key: String):boolean;
  end;
procedure THashTable.Clear;
var
  I: Integer;
  P, N: PHashItem;
begin
  for I := 0 to Length(Buckets) - 1 do
  begin
    P := Buckets[I];
    while P <> nil do
    begin
      N := P^.Next;
      Dispose(P);
      P := N;
    end;
    Buckets[I] := nil;
  end;
end;
function THashTable.ContainKey(const Key: String): boolean;
var
  P: PHashItem;
begin
  P := Find(Key)^;
  if P <> nil then
  begin
    Result := True;
  end
  else
    Result := False;
end;
constructor THashTable.Create(Size: Cardinal);
begin
  inherited Create;
  SetLength(Buckets, Size);
end;
destructor THashTable.Destroy;
begin
  Clear;
  inherited Destroy;
end;
function THashTable.Find(const Key: String): PPHashItem;
var
  Hash: Integer;
begin
  Hash := HashOf(Key) mod Cardinal(Length(Buckets));
  Result := @Buckets[Hash];
  while Result^ <> nil do
  begin
    if Result^.Key = Key then
      Exit
    else
      Result := @Result^.Next;
  end;
end;
function THashTable.Get(const Key: String): Variant;
var
  P: PHashItem;
begin
  P := Find(AnsiUpperCase(Key))^;
  if P <> nil then
    Result := P^.Value
  else
    Result := -1;
end;
function THashTable.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[I]);
end;
function THashTable.Modify(const Key: String; Value: Variant): Boolean;
var
  P: PHashItem;
begin
  P := Find(Key)^;
  if P <> nil then
  begin
    Result := True;
    P^.Value := Value;
  end
  else
    Result := False;
end;
procedure THashTable.Put(const Key: String; Value: Variant);
var
  Hash: Integer;
  Bucket: PHashItem;
begin
  Hash := HashOf(AnsiUpperCase(Key)) mod Cardinal(Length(Buckets));
  New(Bucket);
  Bucket^.Key := AnsiUpperCase(Key);
  Bucket^.Value := Value;
  Bucket^.Next := Buckets[Hash];
  Buckets[Hash] := Bucket;
end;
procedure THashTable.Remove(const Key: String);
var
  P: PHashItem;
  Prev: PPHashItem;
begin
  Prev := Find(Key);
  P := Prev^;
  if P <> nil then
  begin
    Prev^ := P^.Next;
    Dispose(P);
  end;
end;

使用：

var
  Demo:THashTable;
begin
  Demo:=THashTable.Create();
  try
    Demo.Put('id',1);
    ShowMessage(Demo.Get('id'));
  finally
    Demo.Free;
  end;
end;