Давайте рассмотрим различные методы обработки коллизий в хеш-таблицах.
Линейное зондирование:
Когда происходит столкновение, сталкивающийся элемент будет помещен в следующий доступный блок.
Давайте представим хеш-функцию: h(x) = x mod 6 ;
Возьмем массив arr с n равным нулю.
прибытие знак равно [ п , п , п , п , п , п ]
Мы сохраняем значение 10 с индексом 10 mod 6 (что равно 4).
приб = [п, п, п, п, 10, п]
Затем мы сохраняем значение 16.
Поскольку 16 по модулю 6 возвращает 4 , возникает конфликт между 10 и 16.
Затем мы просто выберем следующий доступный блок.
[ n ,n , n , n, 10, 16 ];
если бы блок с индексом +1 был недоступен, мы попытались бы вставить его в блок с индексом +2 и так далее. При достижении конца массива следующее доступное пространство становится началом массива. Если бы нам пришлось вставить 26, массив выглядел бы так:
[ 26 , n , n , n , 10, 16 ];
Чтобы получить нужный элемент. Сначала вычислите его хеш-значение. Затем найдите соответствующее место. Если сохраненное значение не совпадает, проверьте следующий пробел. Продолжайте до тех пор, пока вы не проверите все пробельные блоки (имеется в виду, если индекс равен длине массива), вы не найдете пустой блок или не найдете целевой элемент.
Чтобы удалить элемент, действуйте таким же образом.
Но, обратите внимание, важно не просто удалить целевой элемент, оставив блок «пустым». Действительно, представим, что мы просто удалили 16. Получился бы вот такой массив:
[ 26 , n, n, n, 10 , n];
Теперь, когда мы решили получить 26 , цикл прервется, так как по пути мы встретим пустой элемент. Итак, нам нужно вставить маркер, предупреждающий о том, что в этом блоке ранее было значение, что означает, что значения могут присутствовать в следующих блоках.
Отдельная цепочка:
Используйте блоки как связанные списки. Таким образом, не будет никаких коллизий, так как значения, возвращающие похожие хэши, могут храниться рядом друг с другом.
Квадратичное зондирование:
Квадратичное зондирование обеспечивает эффективное решение проблемы «эффекта кластеризации», вызванного использованием линейного зондирования.
Действительно, линейное зондирование может привести к тому, что элементы начнут формировать группы последовательных продаж, что может сильно замедлить выполнение алгоритма, независимо от того, думаем ли мы об извлечении, удалении или вставке.
Ex:
arr = [n,n,n,n,n,n,n,n,n,n,n,n];
Вот функция, которая может быть для линейного зондирования:
(h(x) + i) по модулю 6
Для квадратичного зондирования мы поступим следующим образом:
(ч (х) + я ^ 2) по модулю п
Давайте возьмем хеш-функцию, которую мы использовали ранее:
ч(х) = х по модулю 5;
вставьте 7, это даст вам 2.
приб = [п, п, 7, п, 10, п]
Теперь вставьте 12. Он также вернет 2.
Итак, выполняем квадратичное зондирование:
i = 1
2 + i^2 ;
Значение будет сохранено как индекс 2 + 1 => 3.
Далее, давайте представим, что мы хотим вставить 22:
i = 2
Значение будет храниться по индексу 2 + 2 ^2=> 4.
Если вы хотите вставить 32 :
i =3
Значение будет храниться по индексу 2 + 3 ^2 => 11.
Вот такой массив будет получен:
arr = [n,n, 12,n, 22,n,n,n,n,n,n, 32,n];
Мы можем ясно видеть, что при использовании этого метода элементы распределяются по доступному пространству.
Однако мы можем прийти к точке, называемой вторичной кластеризацией.
Действительно, мы могли бы прийти к циклу, в котором мы снова и снова проверяем только пустые места.
Это один из недостатков квадратного зондирования. Однако есть способы справиться с этим недостатком, о которых мы поговорим далее.
Двойное хеширование:
Вместо одной функции хэширования мы можем комбинировать разные.
Ex:
arr = [n,n,n,n,n,n,n,n,n,n,n,n];
Давайте создадим хеш-функцию h1 и хеш-функцию h2 для значения h(x):
ч(х) = хеш1(х) + я * хэш(х)
hash1(x) = k по модулю 5
hash2(x) = (3+x) по модулю 5
Вставка 7;
хеш1(7) = 2 ;
хеш2(7) = 5
i=0
h(x) = 2 + i*5 => 2
arr = [n,n,7,n,n,n,n,n,n,n,n,n];
Теперь представим, что нам нужно было вставить 12.
хеш1(12) = 2 ;
хеш2(12) = 5
i=0
h(x) = 2 + i*5 => 2
Из-за столкновения мы увеличиваем индекс на 1.
i=1
h(x) = 2 + i*5 => 7
Заметим, что до тех пор, пока не произойдет коллизия, вторая хеш-функция не используется для вычисления хеш-значения.
