{

 Hash operations for Borland Pascal 7.0

}

 

Unit Hash;

 

Interface

 

Const HashGroups = 1000;

 

Type

     HashElement = Integer;

     HashKey = String;

     PList = ^TList;

     TList = Record

      Key: HashKey;

      Value: HashElement;

      Removed: Boolean;

      Next: PList;

     End;

     THash = Object

      Data: Array[1..HashGroups] Of PList;

 

     Public

      Constructor Init;

      Function HashFunction(Key:HashKey):Longint; Virtual;{Must be overrided}

      Procedure AddValue(Key:HashKey;Value:HashElement);

      Function FindValue(Key:HashKey;Var Found:Boolean):HashElement;

      Procedure DeleteValue(Key:HashKey);

      Destructor Done; Virtual;

     Private

      Procedure AddToList(P:PList;Key:HashKey;Value:HashElement);

      Procedure DeleteGroup(P:PList);

     End;

 

Implementation

 

Uses Objects;

 

Constructor THash.Init;

Var I:Integer;

Begin

 For I:=1 To HashGroups Do

  Data[I]:=Nil;

End;

 

Destructor THash.Done;

Var I:Integer;

Begin

 For I:=1 To HashGroups Do

  DeleteGroup(Data[I]);

End;

 

Function THash.HashFunction(Key:HashKey):Longint;

Begin

 Abstract;

End;

 

Procedure THash.AddValue(Key:HashKey;Value:HashElement);

Var B:Boolean;

Begin

 FindValue(Key,B);

 If B Then Exit;

 AddToList(Data[HashFunction(Key)],Key,Value);

End;

 

Procedure THash.AddToList(P:PList;Key:HashKey;Value:HashElement);

Var N,O:PList;

Begin

 While O <> Nil Do

  Begin

   If (O^.Key = Key) And (O^.Removed) Then

    Begin

     O^.Removed:=False;

     O^.Value:=Value;

     Exit;

    End;

   O:=O^.Next;

  End;

 New(N);

 N^.Key:=Key;

 N^.Value:=Value;

 N^.Next:=P;

 N^.Removed:=False;

 Data[HashFunction(Key)]:=N;

End;

 

Procedure THash.DeleteGroup(P:PList);

Begin

 If P = Nil Then Exit;

 If P^.Next = Nil Then

  Dispose(P)

 Else

  DeleteGroup(P^.Next);

End;

 

Function THash.FindValue(Key:HashKey;Var Found:Boolean):HashElement;

Var Func: Longint;

    P:PList;

Begin

 Func:=HashFunction(Key);

 P:=Data[Func];

 While P <> Nil Do

  Begin

   If (Key = P^.Key) And (Not P^.Removed) Then

    Begin

     Found:=True;

     FindValue:=P^.Value;

     Exit;

    End;

   P:=P^.Next;

  End;

 Found:=False;

End;

 

Procedure THash.DeleteValue(Key:HashKey);

Var P,O:PList;

    Func:Longint;

Begin

 Func:=HashFunction(Key);

 P:=Data[Func];

 While P <> Nil Do

  Begin

   If Key = P^.Key Then

    P^.Removed:=True;

   P:=P^.Next;

  End;

End;

 

End.

Uses Hash;

 

Type TMyHash = Object(THash)

      Function HashFunction(Key:HashKey):Longint; Virtual;

     End;

 

Function TMyHash.HashFunction(Key:HashKey):Longint;

Var I:Integer;

    Sum:Integer;

Begin

 Sum:=0;

 For I:=1 To Length(Key) Do

  Sum:=Sum + (Ord(Key[I]) * I);

 HashFunction:=(Sum Mod HashGroups) + 1;

End;

 

Var H:TMyHash;

    B:Boolean;

    V:HashElement;

Begin

 Writeln('----');

 Writeln(MemAvail);

 H.Init;

 H.AddValue('chislo',5);

 H.DeleteValue('chislo1');

 V:=H.FindValue('chislo',B);

 If B Then Writeln(V) Else Writeln('No element');

 H.Done;

 Writeln(MemAvail);

End.

aaasdf

dfgbv

sdfdsf

ghghhj

sdfgf

asdser

a         …       d         …        g         …       s

aaasdf            dfgbv              ghghhj            sdfdsf

asdser                                                 sdfgf