Рандомизация

Этот метод доступа имеет несколько названий: перемешивание, рандомизация, хэширование. Общая схема представлена на рисунке 4:

Область размещения элементов

линейного списка

Рисунок 4

Область размещения элементов линейного списка делится на участки – бакеты. При добавлении элементов линейного списка в соответствии со значениями первичных ключей К_i алгоритм рандомизации определяет не адрес отдельного элемента (как это было в предыдущих случаях), а номер (адрес) бакета. Сам элемент размещается в бакете в первом свободном месте – после уже имеющихся в нем элементов. Таким образом, список элементов внутри бакета не упорядочен.

При поиске элемента алгоритм рандомизации по первичному ключу определяет вначале номер бакета, в котором должен находиться элемент. Затем уже в найденном бакете методом последовательного сканирования делается попытка найти нужный элемент (см. метод последовательного сканирования для неупорядоченного списка).

Алгоритм рандомизации состоит из следующих шагов:

1. этот шаг выполняется только для нечисловых значений ключа и состоит в их преобразовании в числовые значения. Для этого каждому символу алфавита, который используется для записи значения ключа, приписывается десятичная цифра от 0 до 9, и ключ переписывается. Например, пусть значения ключа формируются из букв русского алфавита. Припишем им десятичные цифры: