Методические материалы
по курсу
"Алгоритмы и алгоритмические языки"

(* Хеш-таблица - таблица, в которой доступ к записям        *)
(*               определяется хеш-функцией.                 *)

(* Хеш-функция (Функция расстановки) - функция, вычисляющая *)
(*   по заданному ключу записи                              *)
(*   номер позиции в таблице, начиная с которого следует    *)
(*                            искать/размещать запись.      *)
 
Const  So = 2000;         (* , например  *)
       Sx = 1999;         (*   Sx = So-1 *)
Type  pElem = ^Elem;
       Elem = record Key : integer; (* ... *) end;

(* Примеры хеш-функций:                                     *)
(*                      HashMod - метод деления             *)
(*                      HashMul - метод умножения и др.     *)
 
function HashMod(K : integer) : integer;
begin    HashMod:=K div So          end;
 
function HashMul(K : integer) : integer;
   var R : real;
begin   R:=0.618*abs(K);                  (* 0.618 = (Sqrt(5)-1)/2 *)
        R:=So*(R-trunc(R));               (* So*(Дробная Часть R)  *)
        if 0 <= K then HashMul:=+trunc(R)
                  else HashMul:=-trunc(R)   end;

(* Коллизия - ситуация, когда в хеш-таблице представлены    *)
(* две (или более) записей с различными ключами K1 и K2     *)
(* такими, что Hash(K1) = Hash(K2)                          *)

(* Хеш-функция должна:                                      *)
(*                   -1- допускать эффективную реализацию и *)
(*                   -2- минимизировать число коллизий      *)

(* Методы разрешения коллизий:                              *)
(*                                 -1- Отрытое  хеширование *)
(*                                 -2- Закрытое хеширование *)

(* Идея открытого хеширования (в идеальном случае) :        *)
(* Ячейка хеш-таблицы                                       *)
(*       - может быть свободна;                             *)
(*       - может содержать указатель на запись;             *)
(*       - может содержать указатель на цепочку записей     *)
(*         с одинаковыми значениями хеш-функции.            *)

(* //////////////////// Пусть: //////////////////////////// *)
 
   program ...;
   Const So = 2000; (* Например  *)
         Sx = 1999; (* Sx = So-1 *)
   ...
   Type pElem = ^Elem;
         Elem = record Key : integer; ... end;
        pPair = ^Pair;
         Pair = record ELE : pElem;
                       NXT : pPair   end;
   ...
   var  T : array [0..Sx] of pPair;
        I : integer;
   ...
   function Hash(K : integer) : integer; begin ... end;
   ...

   ...
   begin   (* Тело программы *)
           for I:=0 to Sx do T[I]:=nil; (* Породить пустую хеш-таблицу *)
           ...
   end.    (* Конец программы *)
 

(* FormHTC : Создать в хеш-таблице T (новую) запись с ключом K.*)
(*           FormHTC(K,pN) - указатель на (новую) запись.      *)
(* при этом: Если pN = true,  то такой записи ранее не было.   *)
(*           Если pN = false, то в таблице такая запись была.  *)

function FormHTC(K : integer; var pN : boolean) : pElem;
   var H : integer;
       P : pPair;
begin   H:=Hash(K);
        P:=T[H];
        while P <> nil do
        if P^.ELE^.Key = K then begin   (* K: найден в  *)
           FormHTC:=P^.ELE;             (* существующих *)
                pN:=false
           Exit
        end                else P:=P^.NXT;
        new(P);
        with P^ do begin                (* K: построить *)
           NXT:=T[H]; T[H]:=P;          (* и включить в *)
           new(ELE);  ELE^.Key:=K;      (* начало списка*)
           FormHTC:=ELE;
                pN:=true
        end                                         end;

(* rKillHTC - рекурсивная реализация KillHTC. Сравните и поймите. *)
 
procedure rKillHTC(K : integer);
   procedure VarpTest(var R : pPair);
      var Q : pPair;
   begin   if           R = nil then Exit;
           if R^.ELE^.Key = K   then begin
              Q:=R;
              R:=R^.NXT;         (* Исключить из списка *)
              Dispose(Q^.ELE);   (* Уничтожить          *)
              Dispose(Q);        (*             записи  *)
              Exit
           end;
           VarpTest(R^.NXT)
   end;
begin   VarpTest(T[Hash(K)])          end;

(* Примеры вторичных хеш-функций: Hash2A, Hah2B и др.       *)
 
function Hash2A(K,V : integer) : integer;
begin    Hash2A:=Hash(K)+V           end;
 
function Hash2B(K,V : integer) : integer;
begin    Hash2B:=Hash(K)+sqr(V)      end;

(* //////////////////// Пусть: //////////////////////////// *)
 
   program ...;
   Const So = 2000; (* Например  *)
         Sx = 1999; (* Sx = So-1 *)
   ...
   Type pElem = ^Elem;
         Elem = record Key : integer; ... end;
   ...
   var  T : array [0..Sx] of pElem;
        I : integer;
   ...
   function Hash (K   : integer) : integer; begin ... end;
   function Hash2(K,V : integer) : integer; begin ... end;
   ...

   ...
   begin   (* Тело программы *)
           for I:=0 to Sx do T[I]:=nil; (* Породить пустую хеш-таблицу *)
           ...
   end.    (* Конец программы *)

(* FormHTL : Создать в хеш-таблице T (новую) запись с ключом K.*)
(*           FormHTL(K,pN) - указатель на (новую) запись.      *)
(* при этом: Если pN = true,  то такой записи ранее не было.   *)
(*           Если pN = false, то в таблице такая запись была.  *)
(*           Если FormHTL(K,pN) = nil, то таблица полна.       *)
 
function FormHTL(K : integer; var pN : boolean) : pElem;
     var I : integer;
   function OH(N : integer) : boolean;
   begin   OH:=true;                  (* Оптимистический вариант *)
           if T[N] = nil then begin
              new(T[N]);
              T[N]^.Key:=K;
                                 FormHTL:=T[N]
           end           else
           if T[N]^.Key = K then FormHTL:=T[N]
                            else OH:=false
   end;
begin   FormHTL:=nil;
        if OH(Hash(K)) then Exit;
        for I:=1 to Sx do
        if OH(Hash2(K,I)) then Exit
end;