Анализ поставленной задачи

Двойное хеширование — один из лучших методов открытой адресации. Последовательности индексов, возникающие при зондировании с двойным хешированием, близки к равномерному хешированию. При двойном хешировании хеш-функция имеет вид обычной хеш-функции. То есть, последовательность проб при зондировании является арифметической прогрессией по модулю m с первым членом h (k) и шагом h1(k).

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

Интервал в двойном хешировании между ячейками фиксирован, как при линейном пробировании, но, в отличие от него, размер интервала вычисляется второй, вспомогательной хеш-функцией, а значит может быть различным для разных ключей. Значения этой хеш-функции должны быть ненулевыми и взаимно-простыми с размером хеш-таблицы, что проще всего достичь, взяв простое число в качестве размера, и потребовав, чтобы вспомогательная хеш-функция принимала значения от 1 до N — 1.

Наилучшим вариантом (во избежание коллизий) взять следующую функции h1, которая представлена в следующей формуле:

h1 = ,.

где h1 — хеш-функция № 1;

C — сумма кодов ASCII символов ключа;

L — размер (количество символов) ключа.

В свою очередь, функция h2 имеет вид (формула 2.2):

h2 = L*2,.

где h2 — хеш-функция № 2;

L — размер ключа.

Функции с данными функции (формула 2.1 и формула 2.2) и будут выступать в разрабатываемом программном продукте в качестве функций № 1 и № 2.