Организация данных для поиска по вторичным ключам

Переполнение таблицы и рехеширование

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

Рис. 8.8. Циклический переход к началу таблицы.

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

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

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

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

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

Алгоритм вставки, реализующий такой подход:

1.

2.

3. Если или , то , записать элемент, элемент добавлен. Если , требуется рехеширование , перейти к шагу 2.

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

Однако даже при наличии первичного ключа, для поиска записи могут быть использованы вторичные. Например, поисковые системы сети Internet часто организованы как наборы записей, соответствующих Web-страницам. В качестве вторичных ключей для поиска выступают ключевые слова, а задача поиска сводится к выборке из таблицы некоторого множества записей, содержащих требуемые вторичные ключи.

Дата добавления: 2014-01-07