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

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

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]
    def hash_function(self, key):
        return key % self.size
    def insert(self, key, value):
        index = self.hash_function(key)
        self.table[index].append((key, value))
    def get(self, key):
        index = self.hash_function(key)
        slot = self.table[index]

        for item in slot:
            if item[0] == key:
                return item[1]

        return None

2. Открытая адресация – линейное зондирование.
   При линейном зондировании при возникновении коллизии следующий доступный слот в хеш-таблице проверяется последовательно, пока не будет найден пустой слот. Вот пример реализации линейного зондирования в Python:

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

3. Открытая адресация – квадратичное зондирование.
   Квадратичное зондирование разрешает коллизии с помощью квадратичной функции для поиска следующего доступного слота. Он использует последовательность зондирования, которая увеличивается квадратично. Вот пример реализации квадратичного зондирования в Python:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
    def hash_function(self, key):
        return key % self.size
    def insert(self, key, value):
        index = self.hash_function(key)
        i = 1
        while self.table[index]:
            index = (index + i2) % self.size
            i += 1
        self.table[index] = (key, value)
    def get(self, key):
        index = self.hash_function(key)
        i = 1
        while self.table[index]:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + i2) % self.size
            i += 1
        return None

4. Хеширование с кукушкой.
   Хеширование с кукушкой — это метод, при котором каждый ключ может храниться в двух разных хеш-таблицах. Если происходит конфликт, ключ перемещается в альтернативную позицию в другой хэш-таблице. Этот процесс продолжается до тех пор, пока не исчезнут столкновения. Вот пример реализации хеширования cuckoo в Python:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table1 = [None] * size
        self.table2 = [None] * size
    def hash_function1(self, key):
        return key % self.size
    def hash_function2(self, key):
        return (key // self.size) % self.size
    def insert(self, key, value):
        index1 = self.hash_function1(key)
        index2 = self.hash_function2(key)
        if self.table1[index1] is None:
            self.table1[index1] = (key, value)
        elif self.table2[index2] is None:
            self.table2[index2] = (key, value)
        else:
            evicted_key, evicted_value = self.table1[index1]
            self.table1[index1] = (key, value)
            self.insert(evicted_key, evicted_value)
    def get(self, key):
        index1 = self.hash_function1(key)
        index2 = self.hash_function2(key)
        if self.table1[index1] and self.table1[index1][0] == key:
            return self.table1[index1][1]
        elif self.table2[index2] and self.table2[index2][0] == key:
            return self.table2[index2][1]
        else:
            return None