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

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

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

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

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

class HashTableWithChaining:
    def __init__(self, size: int = 10):
        self.table = [[] for _ in range(size)]
        self.size = size
    
    def _hash(self, key: str) -> int:
        return hash(key) % self.size
    
    def insert(self, key: str, value: str) -> None:
        index = self._hash(key)
        # Проверяем, есть ли уже такой ключ
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value  # Обновляем значение
                return
        # Если ключа нет, добавляем новую пару
        self.table[index].append([key, value])
    
    def get(self, key: str) -> str:
        index = self._hash(key)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        return None

hash_table = HashTableWithChaining()
hash_table.insert("name", "Alice")
hash_table.insert("age", "30")
print(hash_table.get("name"))  # Alice

Плюсы:

• Простая реализация
• Динамичная — можно добавлять элементы без переделки таблицы
• Легко удалять элементы

Минусы:

• При много коллизиях поиск становится медленным O(n)
• Требует дополнительной памяти для цепочек

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

Вместо цепочек ищем другую свободную ячейку в таблице. Есть несколько стратегий:

а) Linear Probing (Линейное сканирование)

При коллизии проверяем следующую ячейку, потом следующую, и так далее.

class HashTableLinearProbing:
    def __init__(self, size: int = 10):
        self.table = [None] * size
        self.size = size
    
    def _hash(self, key: str) -> int:
        return hash(key) % self.size
    
    def insert(self, key: str, value: str) -> None:
        index = self._hash(key)
        # Ищем свободную ячейку
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)  # Обновляем
                return
            index = (index + 1) % self.size  # Идём дальше
        self.table[index] = (key, value)
    
    def get(self, key: str) -> str:
        index = self._hash(key)
        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

Проблема: Clustering — образуются группы заполненных ячеек, что замедляет поиск.

б) Quadratic Probing (Квадратичное сканирование)

Вместо линейного сдвига используем квадратичный: index = (hash + 1²) % size, потом (hash + 2²) % size и т.д.

def insert_quadratic(self, key: str, value: str) -> None:
    index = self._hash(key)
    i = 1
    while self.table[index] is not None:
        if self.table[index][0] == key:
            self.table[index] = (key, value)
            return
        index = (index + i * i) % self.size
        i += 1
    self.table[index] = (key, value)

Плюсы: Лучше разбивает кластеры.

в) Double Hashing (Двойное хеширование)

Используем вторую хеш-функцию для определения шага.

class HashTableDoubleHashing:
    def __init__(self, size: int = 10):
        self.table = [None] * size
        self.size = size
    
    def _hash1(self, key: str) -> int:
        return hash(key) % self.size
    
    def _hash2(self, key: str) -> int:
        return 7 - (hash(key) % 7)  # Вторая функция
    
    def insert(self, key: str, value: str) -> None:
        index = self._hash1(key)
        step = self._hash2(key)
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = (index + step) % self.size
        self.table[index] = (key, value)

Плюсы: Лучше распределение, меньше кластеров.

3. Динамическое переразмеривание (Rehashing)

Когда таблица становится слишком полной (factor нагрузки > 0.75), создаём новую большую таблицу и перехешируем все элементы.

class DynamicHashTable:
    def __init__(self, initial_size: int = 10):
        self.table = [[] for _ in range(initial_size)]
        self.size = initial_size
        self.count = 0
    
    def load_factor(self) -> float:
        return self.count / self.size
    
    def _rehash(self) -> None:
        old_table = self.table
        self.size *= 2
        self.table = [[] for _ in range(self.size)]
        self.count = 0
        
        for bucket in old_table:
            for key, value in bucket:
                self.insert(key, value)
    
    def insert(self, key: str, value: str) -> None:
        if self.load_factor() > 0.75:
            self._rehash()
        
        index = hash(key) % self.size
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value
                return
        self.table[index].append([key, value])
        self.count += 1

4. В Python

Встроенные dict и set в Python используют combination методов:

# Python использует open addressing с quadratic probing
my_dict = {}
my_dict["name"] = "Alice"
my_dict["age"] = 30

# Нет явных коллизий для нас — Python разбирается сам
print(my_dict["name"])  # Alice

# Но можно посмотреть внутреннее устройство
import sys
print(sys.getsizeof(my_dict))

5. Сравнение методов

α = load factor (количество элементов / размер таблицы)

Выводы

• Chaining — лучший выбор для большинства случаев: простая реализация, хорошая производительность
• Open Addressing — экономит память, но может быть сложнее
• Double Hashing — лучше распределяет элементы, но медленнее вычисляется
• Динамическое переразмеривание — критично для поддержания O(1) доступа