Какие есть способы разрешения коллизий в хеш-таблицах?

1️⃣ Как кратко ответить

В хеш-таблицах коллизии разрешаются несколькими способами: методом цепочек (chaining), открытой адресацией (open addressing), двойным хешированием (double hashing) и методами, основанными на перфектных хеш-функциях. Метод цепочек использует связные списки для хранения элементов с одинаковым хешем. Открытая адресация хранит все элементы в самой таблице, используя линейное, квадратичное пробирование или двойное хеширование для поиска следующей свободной ячейки. Выбор метода зависит от требований к производительности и памяти.

2️⃣ Подробное объяснение темы

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

Способы разрешения коллизий

Метод цепочек (Chaining)

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

• Преимущества: Простота реализации, эффективное использование памяти.
• Недостатки: В худшем случае (все элементы в одном списке) время поиска становится линейным.

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]
​
    def insert(self, key, value):
        index = hash(key) % self.size
        self.table[index].append((key, value))
​
    def get(self, key):
        index = hash(key) % self.size
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

Открытая адресация (Open Addressing)

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

• Линейное пробирование (Linear Probing): Последовательно проверяются следующие ячейки.

• Квадратичное пробирование (Quadratic Probing): Используется квадратичная функция для определения следующей ячейки.

• Двойное хеширование (Double Hashing): Используются две хеш-функции для определения следующей ячейки.

• Преимущества: Все элементы хранятся в одном массиве, что может улучшить кэширование.

• Недостатки: Может возникнуть проблема кластеризации, когда несколько элементов группируются в одной области массива.

class OpenAddressingHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
​
    def insert(self, key, value):
        index = hash(key) % self.size
        while self.table[index] is not None:
            index = (index + 1) % self.size
        self.table[index] = (key, value)
​
    def get(self, key):
        index = hash(key) % self.size
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
        return None