Таблицы со случайным перемешиванием

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

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

В методе открытого перемешивания при отображении таблицы в вектор длины n применяется следующий алгоритм включения и выборки записей по заданному ключу k:

1. Вычислить i = f(k).

2. Если при включении в таблицу новой записи позиция i свободна, а при выборке записи эта позиция содержит заданный ключ k, то поиск завершен. В противном случае нужно перейти к следующему пункту.

3. Положить

i = i + 1(mod n)

и перейти к пункту 2. Здесь

Нетрудно видеть, что при включении новых записей алгоритм остается конечным до тех пор, пока вектор, в который отображается таблица, содержит хотя бы одну свободную позицию. При выборке записей алгоритм конечен, если таблица содержит запись c заданным ключом. При невыполнении этих условий возможно зацикливание, против которого нужно принимать специальные меры. Например, можно ввести счетчик числа просмотренных позиций, если это число станет больше n, то алгоритм «зациклился».

Пример. В таблице имен, имеющей 8 позиций, требуется разместить идентификаторы:

а, а1, h, h1, b, a2.

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

а, b, с, d, е, f, g, h,

а значение функции расстановки равно порядковому номеру в алфавите первой буквы идентификатора.

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

Средняя длина поиска в методе открытого перемешивания исследовалась теоретически и экспериментально. Оказалось, что при случайном равномерном распределении значений функции расстановки в интервале (1,n) средняя длина поиска не зависит от размера таблицы, а зависит только от заполненности

отображающего вектора

s =m/n

где m — длина таблицы, a n — длина отображающего вектора. Это весьма важное свойство, особенно ценное для больших таблиц. Заметим, что детерминированные таблицы как упорядоченные, так и неупорядоченные не обладают этим свойством. В детерминированных таблицах средняя длина поиска возрастает с ростом длины таблицы, что видно из формул (2.8) и (2.9).

Следующая приближенная формула для средней длины поиска в методе открытого перемешивания дает удовлетворительное согласование с экспериментом при s £ 0,85:

D(s)=(2-s)/(2-2s) (2.10)

Формула получена в предположении случайного равномерного распределения записей по позициям отображающего вектора. Значения средней длины поиска, вычисленные по формуле (2.10), приведены в табл. 2.4.

Эксперименты показывают, что при s = 1 средняя длина поиска не превосходит 20.

При неравномерном распределении записей по позициям отображающего вектора приведенные в табл. 2.4 числа, как показали эксперименты,возрастают в среднем в 1,5—2 раза. Даже с этой поправкой открытое перемешивание имеет меньшую среднюю длину поиска, чем другие методы. Например, для таблицы в 400 записей при длине отображающего вектора, равной 512, средняя длина поиска по таблице с открытым перемешиванием с учетом поправки на неравномерность распределения записей не превосходит 4,5—6. В этих же условиях длина двоичного поиска равна 10, а средняя длина последовательного просмотра — 200. Правда, в открытом перемешивании около 20% памяти, отведенной под таблицу, не используется.

Таблица 2.4

ТЕОРЕТИЧЕСКАЯ СРЕДНЯЯ ДЛИНА ПОИСКА В ТАБЛИЦЕ С ОТКРЫТЫМ ПЕРЕМЕШИВАНИЕМ