Методы хеширования. Исходные данные для построения функции хеширования: интервал изменения ключа и приблизительное количество записей в основном файле

Исходные данные для построения функции хеширования: интервал изменения ключа и приблизительное количество записей в основном файле. A=F(K), K – значение ключа, A – адрес записи. Основное требование к функции хеширования: квазиравномерное распределение значений величины A.

Определение. Два ключа K1 и K2 называются синонимами относительно функции хеширования F, если F(K1)=F(K2).

Второе требование к функции хеширования: как можно меньше синонимов.

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

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

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

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

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

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