На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Правила ЧаВо (FAQ) разделов Паскаля
В этом разделе разрешено создавать только темы, в которых описано РЕШЕНИЕ какой-либо общей проблемы, или описание какого-либо аспекта языка Паскаль.
Обсуждение уже созданных тем разрешено, но только конструктивное, например указание на ошибку или уточнение имеющегося текста.

Также читать Требования к оформлению статей
Модераторы: Romtek, volvo877
  
    > Хеш-таблица , Общие сведения о хешировании
      Допустим у нас есть некоторый словарь:
      ExpandedWrap disabled
        aaasdf
        dfgbv
        sdfdsf
        ghghhj
        sdfgf
        asdser


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

      Способ №1.

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

      Способ №2.

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

      Каждому столбику сопоставим букву.
      И получим следующую таблицу (некоторые буквы опущены):
      ExpandedWrap disabled
        a         …       d         …        g         …       s
        aaasdf            dfgbv              ghghhj            sdfdsf
        asdser                                                 sdfgf



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

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

          Прикреплённый файлПрикреплённый файлhash.zip (1.69 Кбайт, скачиваний: 661)
          0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
          0 пользователей:


          Рейтинг@Mail.ru
          [ Script execution time: 0,0272 ]   [ 16 queries used ]   [ Generated: 21.05.24, 16:28 GMT ]