Рандомизация
Этот метод доступа имеет несколько названий: перемешивание, рандомизация, хэширование. Общая схема представлена на рисунке 4:
Область размещения элементов
линейного списка
Рисунок 4
Область размещения элементов линейного списка делится на участки – бакеты. При добавлении элементов линейного списка в соответствии со значениями первичных ключей Кi алгоритм рандомизации определяет не адрес отдельного элемента (как это было в предыдущих случаях), а номер (адрес) бакета. Сам элемент размещается в бакете в первом свободном месте – после уже имеющихся в нем элементов. Таким образом, список элементов внутри бакета не упорядочен.
При поиске элемента алгоритм рандомизации по первичному ключу определяет вначале номер бакета, в котором должен находиться элемент. Затем уже в найденном бакете методом последовательного сканирования делается попытка найти нужный элемент (см. метод последовательного сканирования для неупорядоченного списка).
Алгоритм рандомизации состоит из следующих шагов:
1. этот шаг выполняется только для нечисловых значений ключа и состоит в их преобразовании в числовые значения. Для этого каждому символу алфавита, который используется для записи значения ключа, приписывается десятичная цифра от 0 до 9, и ключ переписывается. Например, пусть значения ключа формируются из букв русского алфавита. Припишем им десятичные цифры:
Дата добавления: 2015-03-03; просмотров: 740;