Хеш-таблица на основе стеков. Dephi

[Satevg]

Задание: организовать данные в хеш-таблице на основе стеков.

Есть наработка, но там хеш-таблица организована на массивах указателей на связанные списки.

Код:

Type

       TInf=Record

        In:Tin;  // Поле информации

        Key:Word; // Поле ключа

       end;

        Tsel=^sel

        sel=Record

        Inf:TInf;

        A:Tsel;

        end;

TH=class(Tobject);

  protected iM:word; p:Tsel;  // Защищенная область полей

       H:^array[0..1] of Tsel;  // Указатель на массив указателей

  public

  Constructor create(M:word);  // Создание таблицы

  Destructor Free(M);  // Освобождение таблицы

  Procedure Add(Inf:TInf);  // Добавление элемента

  Procedure Del(key:Tkey);  // Удаление элемента

  Procedure Read(key:Tkey;var Inf); // Чтение элемента без удаления

  end;

       Constructor TH.create;

        begin

        Inherited create;        // Вызов конструктора

                                       // родительского класса Tobject

               GetMem(H,4*M);  // Создание массива из M указателей

               for i:=0 to M-1 do H[i]:=Nil;  // и его очистка

        end;

       Procedure TH.Add;

        begin

               i:=Inf.key mod M;  // Хэш-функция

               New(P);P^.Inf:=Inf;  // Добавление элемента в стека

               P^.A:=H[i];                 // с вершиной H[i]

               H[i]:=P;

        end;

Procedure TH.Del;  // Поиск и удаление записи

Var p1:Tsel;

  begin

       i:=key mod M;

       p:=H[i];

       if p=Nil then exit else  // Нет записи

       if P^.Inf.key=key then  // Ключ в первой записи

                       begin H[i]:=P.^A;  Dispose(p)  end

       else

  begin p1:=p^.A  // Переход ко второй записи

       While P1<>Nil do begin

        if P1^.Inf.key=key then

               begin

                       P^.A:=P1^.A;

                       Dispose(P1);

                       Exit

               End;

        P:=P1;P1:=P1^.A

        end;

  end;

Procedure TH.Read;  // Поиск и чтение записи без удаления

Var bl:boolean;         // Сравнение с предыдущей

  begin

               i:=key mod M; p:=H[i];bl:=false;

       if p=Nil then bl:=false;

       else

               Repeat

                       bl:=P^.Inf.Key=Key;

                       p1:=p; P:=P^.A;

               Until bl or P=Nil;

       If bl then Inf:=P1^.Inf else Inf:=<отсутствует>;

  end;

       После описания этого класса работа с хэш-таблицей осуществляется следующим образом:

Var H1:TH;  // Экземпляр таблицы

..

begin

       …

               H1.create(Mzap);

               Repeat

  <ввод Inf>;

                H1.Add(Inf);

               Until <пока не закончилась информация>;

               <ввод key>

               H1.read(key,Inf);

               ….

               <ввод key>

               H1.Del(key);

               ….

               H1.free(Mzap);

Как бы это все теперь организовать на основе стеков? Спасибо!

[Satevg]

Функция h(key) называется функцией расстановки, или хеш-функцией. Ввиду того, что число возможных значений ключа K обычно значительно превосходит возможное количество записей K>>М, любая функция расстановки может для нескольких значений ключа давать одинаковое значение позиции i в таблице. В этом случае i=h(key) только определяет позицию, начиная с которой нужно искать запись с ключом key. Поэтому схема хеширования должна включать алгоритм разрешения конфликтов, определяющий порядок действий, если позиция i=h(key) оказывается занятой записью с другим ключом.

Имеется множество схем хеширования, различающихся как выбором удачной функции h(key), так и алгоритма разрешения конфликтов. Эффективность решения реальной практической задачи будет существенно зависеть от выбираемой стратегии.

Алгоритм размещения записей в хеш-таблицу содержит следующие действия: сначала ключ key очередной записи отображается на позицию i=h(key) таблицы. Если позиция свободна, то в нее размещается элемент с ключом key, если занята, то отрабатывается алгоритм разрешения конфликтов, который находит место для размещения данного элемента.

Алгоритм поиска сначала находит по ключу позицию i в таблице, и если ключ не совпадает, то последующий поиск осуществляется в соответствии с алгоритмом разрешения конфликтов, начиная c позиции i.

Часто ключами таблиц являются не числа, а последовательность букв (строки). При выборе функции i=H(key) важно, чтобы ее значения вычислялись, как можно проще и быстрее. Поэтому символьные ключи обычно заменяют целыми числами из некоторого диапазона. Например, если key – слово, то суммой кодов первых 2-3-х букв, если фраза (Ф.И.О.), то сумма кодов первых букв. При написании алгоритма разрешения конфликтов поиск ведут уже по полному слову.

теории чуть еще скину на всякий случай, у самого уже голова кипит =\