Таблицы расстановки

Одним из эффективных способов организации таблицы символов является таблица расстановки (или хеш-таблица). Поиск в такой таблице может быть организован методом повторной расстановки. Суть его заключается в следующем.

Таблица символов

представляет собой массив фиксированного размера N. Идентификаторы могут храниться как в самой таблице символов, так и в отдельной таблице идентификаторов.

Определим некоторую функцию h1

(первичную функцию расстановки), определенную на множестве идентификаторов и принимающую значения от 0 до N - 1 (т.е. 0

h1(id)

N - 1, где id - символьное представление идентификатора). Таким образом, функция расстановки сопоставляет идентификатору некоторый адрес в таблице символов.

Пусть мы хотим найти в таблице идентификатор

id. Если элемент таблицы с номером h1(id) не заполнен, то это означает, что идентификатора в таблице нет. Если же занят, то это еще не означает, что идентификатор id в таблицу занесен, поскольку (вообще говоря) много идентификаторов могут иметь одно и то же значение функции расстановки. Для того чтобы определить, нашли ли мы нужный идентификатор, сравниваем id с элементом таблицы h1(id). Если они равны - идентификатор найден, если нет - надо продолжать поиск

дальше.

Для этого вычисляется вторичная функция расстановки h2(h) (значением которой опять таки является некоторый адрес в таблице символов). Возможны четыре варианта:

- элемент таблицы не заполнен (т.е. идентификатора в таблице нет),

- идентификатор элемента таблицы совпадает с искомым (т.е. идентификатор найден),

- адрес элемента совпадает с уже просмотренным (т.е. таблица вся просмотрена и идентификатора нет)

- предыдущие варианты не выполняются, так что необходимо продолжать

поиск.

Для продолжения поиска применяется следующая функция расстановки h3(h2), h4(h3) и т.д. Как правило, hi = h2 для i

2. Аргументом функции h2

является целое в диапазоне [0, N - 1] и она может быть быть устроена по-разному. Приведем три варианта.

1) h2(i) = (i + 1) mod N.

Берется следующий (циклически) элемент массива.
Этот вариант плох тем, что занятые элементы «группируются», образуют последовательные занятые участки и в пределах этого участка поиск становится по-существу
линейным.
2) h2(i) = (i + k) mod N, где k и N взаимно просты.
По-существу это предыдущий вариант, но элементы накапливаются не в последовательных элементах, а «разносятся».
3) h2(i) = (a * i + c) mod N - «псевдослучайная последовательность».
Здесь c и N должны быть взаимно просты, b = a - 1 кратно p для любого простого p, являщегося делителем N, b кратно 4, если N кратно 4 [5].
Поиск в таблице расстановки можно описать следующей функцией:

void Search(String Id,boolean * Yes,int * Point)
{int H0=h1(Id), H=H0;
   while (1)
   {if (Empty(H)==NULL)
      {*Yes=false;
       *Point=H;
       return;
      }
    else if (IdComp(H,Id)==0)
      {*Yes=true;
       *Point=H;
       return;
      }
    else H=h2(H);
    if (H==H0)
      {*Yes=false;
       *Point=NULL;
       return;
      }
   }
}

Функция IdComp(H,Id) сравнивает элемент таблицы на входе H с идентификатором и вырабатывает 0, если они равны. Функция Empty(H) вырабатывает NULL, если вход H пуст. Функция Search присваивает параметрам Yes и Pointer соответственно следующие значения :
true, P - если нашли требуемый идентификатор, где P - указатель на соответствующий этому идентификатору вход в таблице,
false, NULL - если искомый идентификатор не найден, причем в таблице нет свободного места, и
false, P - если искомый идентификатор не найден, но в таблице есть свободный вход P.
Занесение элемента в таблицу можно осуществить следующей функцией:

int Insert(String Id)
{boolean Yes;
int Point=-1;
Search(Id,&Yes,&Point);
if (!Yes && (Point!=NULL)) InsertId(Point,Id);
return(Point);
}

Здесь функция InsertId(Point,Id) заносит идентификатор Id для входа Point таблицы.

Содержание раздела