3. Алгоритмы
хэширования
2. числовое значение ключа ni – аргумент хэш-
функции f, которая формирует
псевдослучайное число Yi.
Желательно, чтобы эти числа в пределах отведенного для них диапазона были распределены с максимальной равномерностью.
Например, значения Yi состоят из четырех десятичных цифр,
т.е. число возможных комбинаций S равно 10000.
Тогда хэш-функция f должна обеспечить равномерность распределения значений Yi в диапазоне 0–9999;
31
хэширования
3. полученные числа Yi умножаются на
константу N/S (где N – число блоков), которая позволяет преобразовывать числа Yi в
адреса блоков Aблi, лежащие в диапазоне 1–
N.
Например,
N=7000, S =10000, т.е. константа N/S=0.7.
Тогда если Yi =9825, то
Аблi =9825*0.7=6877.
32
3. Алгоритмы
хэширования
Для реализации хэш-функции f разработано множество алгоритмов.
Основное требование заключается в том,
чтобы результаты Yi были
распределены как можно более
равномерно.
В действительности эти алгоритмы не во
всех случаях обеспечивают равномерность получаемого распределения результатов, что приводит к отсылке некоторых записей
в область переполнения. |
33 |
|
3. Алгоритмы
хэширования
Метод квадратов
1. Числовое |
i |
квадрат. |
|
2.Из полученного результата выделяется число Yi, состоящее из центральных цифр.
3.Вычисляется адрес блока: Aблi = Yi.* (N/S).
Позиция и длина участка в ni2 для значения Yi в каждой
системе устанавливаются отдельно
34
3. Алгоритмы
хэширования
Метод квадратов
Допустим, что N=7000, S =10000 (N/S=0.7). Если ni = 172148, то его
квадрат ni2 = 029634933904. Для Yi
отводятся четыре центральные десятичные цифры, т.е. Yi = 3493.
После этого вычисляется адрес блока:
Aблi =3493*0.7=2445
35
хэширования
Метод деления
Адрес блока вычисляется при помощи выражения:
Aблi = ni mod nбл,
где mod – операция получения остатка от
деления (25 mod 4 =0; 25 mod 7=4); ni – числовое
значение ключа; nбл – число, равное числу блоков
N или близкое к нему.
Число nбл должно быть простым или не
содержащим больших сомножителей.
Например, если число блоков N=7000, то nбл
может иметь значение nбл =6997.
Пусть ni = 172148; тогда
Aблi =172148 mod 6997= 4220.
хэширования
Метод
складывания
Числовое значение ключа ni
разбивается на три части, которые складываются друг с другом.
Сумма представляет собой значение Yi, на основании
которого вычисляется адрес блока исходной записи:
Aблi = Yi* (N/S). |
37 |
|
Выводы
oВ настоящее время разработано большое количество алгоритмов хэширования и индексации. Выбор конкретного
метода определяется в каждой системе отдельно.
oРассмотренные вопросы затрагивают лишь часть проблем физической организации БД.
oИх анализ позволяет получить
некоторое представление о
внутреннем устройстве БД.
БЛАГОДАРЮ ЗА ВНИМАНИЕ !
ВОПРОСЫ ?
Александр Николаевич Кривцов |
39 |
an.krivtsov@gmail.com |
|