Отдельный метод обработки коллизий в цепочке при хешировании

Что такое столкновение?

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

Какова вероятность столкновения с большим столом?

Столкновения очень вероятны, даже если у нас есть большая таблица для хранения ключей. Важным наблюдением является парадокс дня рождения. При наличии всего 23 человек вероятность того, что у двух людей день рождения совпадает, составляет 50%.

Как обрабатывать столкновения?

В основном есть два метода обработки коллизий:

• Отдельная цепочка
• Открытая адресация

В этой статье обсуждается только отдельная цепочка. Мы обсудим открытую адресацию в следующем посте.

Отдельная цепочка:

Идея отдельной цепочки состоит в том, чтобы реализовать массив как связанный список, называемый цепочкой. Раздельное связывание — один из самых популярных и часто используемых методов обработки коллизий.

The linked list data structure is used to implement this technique. So what happens is, when multiple elements are hashed into the same slot index, then these elements are inserted into a singly-linked list which is known as a chain. 

Здесь все те элементы, которые хэшируются в один и тот же индекс слота, вставляются в связанный список. Теперь мы можем использовать ключ K для поиска в связанном списке, просто просматривая его линейно. Если внутренний ключ для какой-либо записи равен K, то это означает, что мы нашли нашу запись. Если мы достигли конца связанного списка, но не нашли нашу запись, то это означает, что запись не существует. Следовательно, вывод состоит в том, что в отдельной цепочке, если два разных элемента имеют одинаковое хеш-значение, мы сохраняем оба элемента в одном связанном списке один за другим.

Пример: рассмотрим простую хеш-функцию как « key mod 7 » и последовательность ключей как 50, 700, 76, 85, 92, 73, 101.

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

Преимущества:

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

Недостатки:

• Производительность кеша цепочки не очень хорошая, поскольку ключи хранятся с использованием связанного списка. Открытая адресация обеспечивает лучшую производительность кэша, поскольку все данные хранятся в одной таблице.
• Пустая трата места (некоторые части хеш-таблицы никогда не используются)
• Если цепочка становится длинной, то время поиска в худшем случае может стать O(n).
• Использует дополнительное место для ссылок

Производительность цепочки:

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

m = Number of slots in hash table
n = Number of keys to be inserted in hash table

Load factor α = n/m
Expected time to search = O(1 + α)
Expected time to delete = O(1 + α)

Time to insert = O(1)
Time complexity of search insert and delete is O(1) if  α is O(1)

Структуры данных для хранения цепочек:

1. Связанные списки

• Поиск: O(l), где l = длина связанного списка
• Удалить: О(л)
• Вставка: О(л)
• Не поддерживает кеширование

2. Массивы динамического размера (векторы в C++, ArrayList в Java, список в Python)

• Поиск: O(l), где l = длина массива
• Удалить: О(л)
• Вставка: О(л)
• Кеш дружественный

3. Самобалансирующийся BST (деревья AVL, красно-черные деревья)

• Поиск: O(log(l)), где l = длина связанного списка
• Удалить: О (журнал (л))
• Вставка: О(л)
• Не поддерживает кеширование
• Java 8 и более поздние версии используют это для HashMap

Связанный пост: Хеширование | Набор 1 (Введение)

Следующее сообщение:
Открытая адресация для обработки конфликтов