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

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

4.7. Структуры данных, основанные на хеш-таблицах

В реализации словарей с помощью массивов выполнение операторов INSERT, DELETE и MEMBER требует в среднем O(N) выполнений элементарных инструкций для словаря из N элементов. Подобной скоростью выполнения операторов обладает и реализация с помощью списков. При реализации словарей посредством двоичных векторов все эти три оператора выполняются за фиксированное время независимо от размера множеств, но в этом случае мы ограничены множествами целых чисел из некоторого небольшого конечного интервала.

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

Мы рассмотрим две различные формы хеширования. Одна из них называется открытым, или. внешним, хешированием и позволяет хранить множества в потенциально бесконечном пространстве, снимая тем самым ограничения на размер множеств. Другая называется закрытым, или внутренним, хешированием и использует ограниченное пространство для хранения данных, ограничивая таким образом размер множеств.

 

Открытое хеширование

На рис. 4.3 показана базовая структура данных при открытом хешировании. Основная идея заключается в том, что потенциальное множество (возможно, бесконечное) разбивается на конечное число классов. Для В классов, пронумерованных от О до В - 1, строится хеш-функция h такая, что для любого элемента х исходного множества функция h(x) принимает целочисленное значение из интервала 0, ..., В - 1, которое, естественно, соответствует классу, которому принадлежит элемент х. Элемент х часто называют ключом, h(х) — хеш-значением х, а "классы" — сегментами. Мы будем говорить, что элемент х принадлежит сегменту h(x).

Массив, называемый таблицей сегментов и проиндексированный номерами сегментов О, 1.....В - 1, содержит заголовки для В списков. Элемент х і-го списка — это элемент исходного множества, для которого h(x) = і.

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

Не всегда ясно, как выбрать хеш-функцию Л так, чтобы она примерно поровну распределяла элементы исходного множества по всем сегментам. Ниже мы покажем простой способ построения функции А, причем h(x) будет "случайным" значением, почти независящим от х.

Здесь же мы введем хеш-функцию (которая будет "хорошей", но не "отличной"), определенную на символьных строках. Идея построения этой функции заключается в том, чтобы представить символы в виде целых чисел, используя для этого машинные коды символов. В языке Pascal есть встроенная функция ord(c), которая возвращает целочисленный код символа с. Таким образом, если х — это ключ, тип данных ключей определен как аггау[1..10] of char (в примере 4.2 этот тип данных назван nametype), тогда можно использовать хеш-функцию, код которой представлен в листинге 4.7. В этой функции суммируются все целочисленные коды символов, результат суммирования делится на В и берется остаток от деления, который будет целым числом из интервала от 0 до В - 1.

Листинг4.7.'Простаяхеш-функция

function  Л   (   х:   name type   ):   О..В-1;

var

і,   sum:   integer;

begin

sum:=   0;

for i:= 1 to 10 do

sum:=  sum +  ord(x[i]);

h: =  sum mod В

end;    {   h   }

В листинге 4.8 показаны объявления структур данных для открытой хеш-таблицы и процедуры, реализующие операторы, выполняемые над словарем. Тип данных элементов словаря — nametype (здесь — символьный массив), поэтому данные объявления можно непосредственно использовать в примере 4.2. Отметим, что в листинге 4.8 заголовки списков сегментов сделаны указателями на ячейки, а не "настоящими" ячейками. Это сделано для экономии пространства, занимаемого данными: если заголовки таблицы сегментов будут ячейками массива, а не указателями, то под этот массив необходимо столько же места, сколько и под списки элементов. Но за такую экономию пространства надо платить: код процедуры DELETE должен уметь отличать первую ячейку от остальных.

 

51