Методы сортировки и поиска

       

Совершенное хэширование


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

Рис. 4.17.

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

Прием совершенного хэширования дает превосходные результаты при задании известного заранее не очень большого набора ключей, но не помогает в случае необходимости динамического включения или исключения записей.

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