unit Hashtable;

    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;

    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;

    end.