28. Хеширование. Поиск, включение и исключение элементов. Рандомизирующая функция (хеширования) и ее свойства

 

                Рассмотрим пример, в котором организация данных в виде массива ведет к крайне неэффективному использованию памяти компьютера. Пусть в некоторой базе данных изделия кодируются последовательностью целых неотрицательных чисел; в этой последовательности первая цифра обозначает класс изделия, вторая - номер склада, на котором хранится изделие, третья, четвертая и пятая - номер изделия в классе. Так как каждая из цифр может принимать 10 значений (0...9), то всего можно составить 105 различных последовательностей. Значит, мощность множества возможных значений ключей составляет 105. Пусть, кроме того, известно, что классов всего 5 (причем они имеют номера не с 1 до 5, а 1, 4, 6, 7, 9), складов - 4 (с номерами 3, 6, 8, 9), а изделий в классе - не более 50 (номера изделий тоже не последовательные). Таким образом, числовых последовательностей с заданными ограничениями можно составить не более 5*4*50=103. Это означает, что мощность множества фактических значений ключей составляет 103.

                Безусловно, для хранения этой базы данных можно организовать массив, имеющий по одному элементу на каждое возможное значение ключа. Такой массив будет содержать 105 элементов. В этом случае значения ключей можно непосредственно использовать для адресации элементов массива, т.е. применить метод самоиндексирования. Однако при таком подходе максимальный коэффициент загрузки массива (т.е. отношение мощности множества фактических значений ключей 103 к мощности множества возможных значений ключей 105) составит 1%. Массив практически пуст и при этом занимает огромный объем памяти ЭВМ!

 

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

 

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

 

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

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

                Рис. Организация данных при открытом хешировании.

 

                Поиск элемента в такой структуре данных сводится к следующему: по искомому ключу x за время О(1) определяется номер сегмента h(x), а затем последовательно просматриваются элементы списка этого сегмента. Если сегменты примерно одинаковы по размеру, а исходное множество состоит из n элементов, то в среднем списки будут содержать по n/B элементов. Значит, и среднее время поиска элемента по данному ключу составит О(n/B). Процедуры включения элементов в структуру и удаления из нее имеют такую же среднюю сложность.

                Схема действия рандомизирующей функции представлена на рис.

                Рис. Схема действия рандомизирующей функции.

 

Требования к рандомизирующей функции

                1. Рандомизирующая функция должна обеспечивать достаточно равномерный разброс значений ключей по адресам сегментов. Выполнение этого условия позволяет эффективно использовать всю область массива.

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

                4. Рандомизирующая функция должна быть достаточно простой, чтобы не требовалось длительного времени на вычисление адреса сегмента по заданному значению ключа. Если это требование не выполнено, то утрачиваются преимущества этого способа адресации по сравнению, например, со способом табличной адресации.

 

Примеры рандомизирующих функций

                1. Функция, использующая деление с остатком.

                Если n - это число блоков в файле, а m - ближайшее к n  превосходящее его простое число, то рандомизирующая функция представляет собой остаток от деления ключа, представленного в цифровом виде, на m:

H(k) = ord(k) mod m,

где ord(k) - порядковый номер ключа k в множестве всех возможных значений ключей.

                2. Функция, состоящая из логических операций.

                Эта функция применяется к некоторой части ключа, представленного в виде последовательности двоичных цифр.