Хеш-таблица , Общие сведения о хешировании

[Krishkinn]

Допустим у нас есть некоторый словарь:

aaasdf
dfgbv
sdfdsf
ghghhj
sdfgf
asdser

Нам необходимо проверить входит ли слово: asdser в этот словарь.

Способ №1.

Просматриваем ВЕСЬ словарь и сравниваем это слово со всеми словами.
На все это у нас уйдет 6 проверок.

Способ №2.

Будем хранить эти слова в специальной таблице (хеш-таблице).

Каждому столбику сопоставим букву.
И получим следующую таблицу (некоторые буквы опущены):

a         …       d         …        g         …       s
aaasdf            dfgbv              ghghhj            sdfdsf
asdser                                                 sdfgf

Нетрудно заметить, что в столбце ‘a’ мы храним все слова начинающиеся с буквы ‘a’ и т.д.
И теперь для того, чтобы найти слово asdser нам необходимо просмотреть столбик ‘a’ , а это уже 2 сравнения.

P.S.
В данном примере мы использовали хеширование по первой букве,
но есть уйма других способов хеширования,
например по контрольной сумме.
Но это уже другая тема.

[tserega]

Продолжаю эту интересную тему.
Итак, существует громадное количество hash-функций. Для чисел это может быть сумма цифр, а для строк - сумма кодов символов, умноженных на их позицию в строке (например, для строки 'Вася' hash-функция будет выглядеть так: Ord('В') * 1 + Ord('а') * 2 + Ord('с') * 3 + Ord('я') * 4).
Вот модуль, в котором реализованы простейшие операции хеширования. Идея такая: создается несколько независимых групп (точнее, списков), в которые будут добавляться элементы. Hash-функция будет определять, в какой список следует добавлять элемент.
Реализовано все через ООП. Замечание: класс THash надо наследовать! В нем описана абстрактная функция HashFunction, которую надо "перекрыть".

{
 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.

Вот пример использования модуля (создается объект, перекрывается метод HashFunction):

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.

[Суть Зла]

Хэш на Pascal.
Реализация - готовая лаба, в ней, на мой скромный взгляд, проще разбираться..

Сообщение отредактировано: Romtek - 24.12.04, 22:21

Прикреплённый файлhash.zip (1.69 Кбайт, скачиваний: 657)