u_hash.pas

Delphi hash表

unit u_hash;

interface

uses SysUtils, Classes;
    
  type
    { THashTable }
    
  PPHashItem = ^PHashItem;
  PHashItem = ^THashItem;
  THashItem = record
    Next: PHashItem;
    Key: string;
    Value: String;
  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: Integer = 256);
  destructor Destroy; override;
  procedure Put(const Key: string; Value: String);
  procedure Clear;
  procedure Remove(const Key: string);
  function Modify(const Key: string; Value: String): Boolean;
  function Get(const Key: string): String;
  end;

  PPIntHashItem = ^PIntHashItem;
  PIntHashItem = ^TIntHashItem;
  TIntHashItem = record
    Next: PIntHashItem;
    Key: string;
    Value: integer;
  end;

  TIntHashTable = class
  private
    Buckets: array of PIntHashItem;
  protected
    function Find(const Key: string): PPIntHashItem;
    function HashOf(const Key: string): Cardinal; virtual;
  public
    constructor Create(Size: Integer = 256);
    destructor Destroy; override;
    procedure Put(const Key: string; Value: integer);
    procedure Clear;
    procedure Remove(const Key: string);
    function Modify(const Key: string; Value: integer): Boolean;
    function Get(const Key: string): integer;
  end;

implementation

  { THashTable }

  procedure THashTable.Put(const Key: string; Value: String);
  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;
    
  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;
    
  constructor THashTable.Create(Size: Integer);
  begin
    inherited Create;
    SetLength(Buckets, Size);
  end;
    
  destructor THashTable.Destroy;
  begin
    Clear;
    inherited;
  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.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: String): 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.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;
    
  function THashTable.Get(const Key: string): String;
  var
    P: PHashItem;
  begin
    P := Find(Key)^;
    if P <> nil then
    Result := P^.Value else
    Result := '';
  end;

  { TIntHashTable }

  procedure TIntHashTable.Put(const Key: string; Value: integer);
  var
    Hash: Integer;
    Bucket: PIntHashItem;
  begin
    Hash := HashOf(Key) mod Cardinal(Length(Buckets));
    New(Bucket);
    Bucket^.Key := Key;
    Bucket^.Value := Value;
    Bucket^.Next := Buckets[Hash];
    Buckets[Hash] := Bucket;
  end;
    
  procedure TIntHashTable.Clear;
  var
    I: Integer;
    P, N: PIntHashItem;
  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;
    
  constructor TIntHashTable.Create(Size: Integer);
  begin
    inherited Create;
    SetLength(Buckets, Size);
  end;
    
  destructor TIntHashTable.Destroy;
  begin
    Clear;
    inherited;
  end;
    
  function TIntHashTable.Find(const Key: string): PPIntHashItem;
  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 TIntHashTable.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 TIntHashTable.Modify(const Key: string; Value: integer): Boolean;
  var
    P: PIntHashItem;
  begin
    P := Find(Key)^;
    if P <> nil then
    begin
      Result := True;
      P^.Value := Value;
    end
    else
    Result := False;
  end;
    
  procedure TIntHashTable.Remove(const Key: string);
  var
    P: PIntHashItem;
    Prev: PPIntHashItem;
  begin
    Prev := Find(Key);
    P := Prev^;
    if P <> nil then
    begin
      Prev^ := P^.Next;
      Dispose(P);
    end;
  end;
    
  function TIntHashTable.Get(const Key: string): integer;
  var
    P: PIntHashItem;
  begin
    P := Find(Key)^;
    if P <> nil then
      Result := P^.Value
    else
      Result := -1;
  end;

end.