ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->Реструктуризация хеш-таблиц

Алгоритмы структуры данных

Реструктуризация хеш-таблиц

При использовании открытых хеш-таблиц среднее время выполнения операторов возрастает с ростом параметра N/B и особенно быстро растет при превышении числа элементов над числом сегментов. Подобным образом среднее время выполнения операторов также возрастает с увеличением параметра N/B и для закрытых хеш-таблиц, что видно из рис. 4.5 (но превышения N над В здесь невозможно).

Чтобы сохранить постоянное время выполнения операторов, которое теоретически возможно при использовании хеш-таблиц, мы предлагаем при достижении N достаточно больших значений, например при N ≥ 0.9В для закрытых хеш-таблиц и N ≥ 2В — для открытых хеш-таблиц, просто создавать новую хеш-таблицу с удвоенным числом сегментов. Перезапись текущих элементов множества в новую хеш-таблицу в среднем займет меньше времени, чем их ранее выполненная вставка в старую хеш-таблицу меньшего размера. Кроме того, затраченное время на перезапись компенсируется более быстрым выполнением операторов словарей.

4.9. Реализация АТД для отображений

Вернемся к АТД MAPPING (Отображение), введенным в главе 2, где мы определили отображение как функцию, ставящую в соответствие элементам области определения соответствующие элементы из области значений. Для этого АТД мы определили такие операторы.

1.    MAKENULL(A). Инициализирует отображение А, где ни одному элементу области определения не соответствует ни один элемент области значений.

2.    ASSIGN(A, d, r). Задает для A(d) значение r.

3.    COMPUTE(A, d, r).  Возвращает значение true и устанавливает значение r для A(d), если A(d) определено, в противном случае возвращает значение false.

Отображения можно эффективно реализовать с помощью хеш-таблиц. Операторы ASSIGN и COMPUTE реализуются точно так же, как операторы INSERT и MEMBER для словарей. Сначала рассмотрим применение открытых хеш-таблиц. Предполагаем, что хеш-функция h(x) распределяет элементы области определения по сегментам хеш-таблицы. Так же, как и для словарей, в данном случае сегменты содержат связанные списки, в ячейках которых находятся поля для элементов области определения и для соответствующих им элементов области значений. Для реализации такого подхода надо в листинге 4.8 заменить определение типа ячеек следующим объявлением:

type

celltype  =  record

domainelement:   domaintype;

range:   rangetype;

next:   ↑celltype

end

Здесь domaintype и rangetype — типы данных для элементов области определения и области значений соответственно. Объявление АТД MAPPING следующее:

type

MAPPING =  array[0..B-l]   of ↑celltype

Последний массив — это массив сегментов для хеш-таблицы. Код процедуры ASSIGN приведен в листинге 4.10. Написание процедур для операторов MAKENULL и COMPUTE оставляем для упражнения.

Листинг 4.10. Процедура ASSIGN для открытой хеш-таблицы

procedure ASSIGN   (  var A:   MAPPING;   d:   domaintype;   r:   rangetype   );

var

bucket:   integer;

current:   ↑celltype;

begin

bucket:=  h(d);

current:= A [bucket] ;

while current <> nil do

if current↑.domainelement =  d then begin

current↑.range: =  r;

{  замена старого значения для d }

return

end

else

current: =  current↑.next;   {   d не  найден  в  списке   }

current:= A[bucket];

{использование   current для  запоминания первой  ячейки)

new(A[bucket]);

А[bucket]↑.domainelement:=  d;

A[bucket]↑.range:=  r;

A[bucket]↑.next:=   current;

end;    {  ASSIGN   }

Подобным образом для реализации отображений можно использовать закрытое хеширование. Ячейки хеш-таблицы будут содержать поля для элементов областей определения и значений, а АТД MAPPING можно определить как массив таких ячеек. Как и в случае открытого хеширования, хеш-функция применяется к элементам области определения, а не к элементам области значений. Мы оставляем читателю в качестве упражнения реализацию соответствующих операторов для закрытых хеш-таблиц.

 

58