3.3. Методы хеширования

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

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

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

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

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

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

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

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

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

Библиографический список

1. Мартин Дж. Организация баз данных в вычислительных системах.  М.: Мир, 1980.  662 с.

2. Ульман Дж. Основы систем баз данных.  М.: Финансы и статистика, 1983.  334 с.

3. Мейер Д. Теория реляционных баз данных.  М.: Мир, 1987.  608 с.

4. Вейнеров О.М., Самохвалов Э.Н. Разработка САПР: В 10 кн. Кн. 4. Проектирование баз данных САПР.  М.: Высш. шк., 1990.  144 с.

5. Дейт К. Введение в системы баз данных.  М.: Диалектика, 1998.  782 с.

6. Солтон Дж. Динамические информационносправочные системы.  М: Мир, 1979.  557 с.

7. Тиори Т., Фрай Дж. Проектирование структур баз данных.  М.: Мир, 1985. Т 2.  320 с.

8. Когаловский М.Р. Энциклопедия технологий баз данных. – М.: Финансы и статистика, 2002. – 800 с.

9. Кузин А.В. Базы данных: Учебное пособие. – М.: Academia, 2005. – 320 с.

10. Советов Б.Я., Цехановский В.В., Чертовской В.Д. Базы данных: теория и практика. – М.: Высшая школа, 2005. – 463 с.

11. Мирошниченко Г.А. Реляционные базы данных. Практические приемы оптимальных решений. – СПб.: BHV, 2005. – 400 с.

12. Диго С.М. Базы данных: проектирование и использование. – М.: Финансы и статистика, 2005. – 592 с.

13. Кузнецов С.Д. Основы баз данных.  М.: Интуит.ру, 2005.  488 с.

14. Уидом Д., Ульман Дж.Д. Основы реляционных баз данных. – М.: Лори, 2006. – 374 с.

15. Мальцев М.Г., Хомоненко А.Д., Цыганков В.М. Базы данных. Учебник для вузов. – М.: КОРОНА, 2006. – 736 с.