yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->„Случайные" методики разрешения коллизий

Алгоритмы структуры данных

„Случайные" методики разрешения коллизий

Мы ранее видели, что методика линейного повторного хеширования приводит к группированию заполненных сегментов в большие непрерывные блоки. Можно предложить хеш-функции с более "случайным" поведением, например, ввести целочисленную константу с > 1 и определить hi(x) = (h(x) + сі) mod В. В этом случае для В = 8, с = 3 и h(x) = 4 получим "пробные" сегменты в следующем порядке: 4, 7, 2, 5, 0, 3, 6 и 1. Конечно, если Бис имеют общие делители (отличные от единицы), то эта методика не позволит получить все номера сегментов, например при В = 8 и с = 2. Но более существенно, что даже если В и с взаимно простые числа (т.е. не имеют общих делителей), то все равно существует проблема "группирования", как и при линейном хешировании, хотя здесь разделяются блоки заполненных сегментов, соответствующие различным константам с. Этот феномен увеличивает время выполнения операторов словарей (как и при линейном хешировании), поскольку попытка вставить новый элемент в заполненный сегмент приводит к просмотру цепочки заполненных сегментов, различных для различных с, и длина этих цепочек при каждой вставке увеличивается на единицу.

Фактически любая методика повторного хеширования, где очередная проба зависит только от предыдущей (например, как зависимость от числа предыдущих "неудачных" проб, от исходного значения h(x) или от самого элемента х), обнаруживает группирующие свойства линейного хеширования. Возможна простейшая методика, для которой проблема "группирования" не существует: для этого достаточно положить hi(x) = (h(x) + di) mod В, где d1, d2, ..., dB-1— "случайные" перестановки чисел 1, 2, ..., В - 1. Конечно, такой набор чисел d1, d2, ..., dB-1 должен использоваться при реализации всех операторов, выполняемых над словарями, а "случайное" перемешивание целых чисел должно быть сделано (выбрано) еще при разработке алгоритма хеширования.

Генерация "хороших случайных" чисел — достаточно сложная задача, но, к счастью, существуют сравнительно простые методы получения последовательности "случайных" чисел путем "перемешивания" целых чисел из заданного интервала. При наличии такого генератора случайных чисел можно воспроизводить требуемую последовательность d1, d2, ..., dB-1 при каждом выполнении операторов, работающих с хеш-таблицей.

Одним из эффективных методов "перемешивания" целых чисел является метод "последовательных сдвигов регистра". Пусть В является степенью числа 2 и k — константа из интервала от 1 до В - 1. Начнем с некоторого числа d1, взятого из интервала от 1 до В - 1. Далее генерируется последовательность чисел di путем удвоения предыдущего значения до тех пор, пока последнее значение не превысит В. Тогда для получения следующего числа di из последнего значения отнимается число В и результат суммируется побитово по модулю 2 с константой k. Сумма по модулю 2 чисел х и у (записывается как x  у) определяется следующим образом: числа х и у записываются в двоичном виде с возможным приписыванием ведущих нулей так, чтобы числа имели одинаковую длину. Результат формируется по правилу логической операции "исключающего ИЛИ", т.е. 1 в какой-либо позиции результата будет стоять тогда и только тогда, когда только в одной аналогичной позиции слагаемых стоит 1, но не в обеих.

Пример 4.7. 25  13 вычисляется следующим образом:

             25 = 11001

             13 = 01101

25  13 = 10100

Отметим, что такое "суммирование" возможно с помощью обычного двоичного суммирования, если игнорировать перенос разрядов.

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

Пример 4.8. Пусть В = 8. Если мы положим k — 3, то сгенерируем все числа от 0 до 7. Например, если начнем с числа d1 = 5, то для нахождения следующего числа d2 сначала удваиваем число d1( получаем число 10, которое больше 8. Поэтому из 10 вычитаем 8, получаем 2 и вычисляем d2 = 2  3 = 1. Отметим, что для любого х сумму х  3 можно вычислить путем инвертирования (преобразования в обратный код) последних двух двоичных разрядов числа x.

Повторяя описанную последовательность действий, получим числа dl, d2, ..., d7 в виде 3-битовых двоичных чисел. Все этапы их вычисления показаны в табл. 4.2. Отметим, что умножение двоичного числа на 2 равнозначно сдвигу влево этого числа на один разряд — это оправдывает название "метод последовательного сдвига регистра".

"Таблица 4.2. Вычисления по методу последовательного сдвига регистра

 

сдвиг

удаление ведущей 1 (вычитание 8)

З

сдвиг

сдвиг

сдвиг 

удаление ведущей 1

 3

сдвиг

сдвиг

удаление ведущей 1

d1 = 101 = 5

1010

010

d2 = 001 = 1

d3 = 010 = 2

d4 = 100 = 4

1000

000

d5 = 011 = 3

d6 = 110 = 6

1100

100

d7 = 111 = 7

Вы можете проверить, что полный "перемешанный" набор чисел 1, 2, ..., 7 можно получить и для k = 5, но ни при каких других значениях k.

 

57