Функции хеширования

Рассмотрим примеры реализации хеш-функций. Функция должна принимать ключ элемента и преобразовывать его в значение индекса. Если в таблице предусмотрено место для n элементов, то функция хеширования должна генерировать значения индексов, лежащих в диапазоне 0..n-1. Кроме того, для различных типов ключей должны быть использованы различные функции. В идеале функция хеширования должна создавать значение индексов, которые никак не связаны с ключами. В определенном смысле хеш-функция должны быть подобна функции рандомизации, т.е. очень похожие ключи должны приводить к созданию совершенно различных хеш-значений.

Простейший случай – использование целочисленных ключей, когда элемент уникально идентифицируется целочисленным значением. Самой простой функцией будет операция деления по модулю. Если хеш-таблица содержит n элементов, хеш-значение ключа k равно:

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

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

Пример реализации простой функции хеширования строковых ключей приведен ниже.

function SimpleHash(aKey: string; aTableSize: Integer): Integer;

Дата добавления: 2014-01-07