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

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

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

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

Самый распространённый способ — использование связных списков. При коллизии элементы с одинаковым хешем хранятся в одном бакете в виде цепочки.

class HashTableChaining:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        index = self._hash(key)
        # Проверяем, есть ли уже такой ключ
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        # Добавляем новую пару
        self.table[index].append((key, value))
    
    def get(self, key):
        index = self._hash(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

Преимущества: простота реализации, удаление элементов — тривиально.

Недостатки: плохая локальность кеша, память под цепочки может быть значительной.

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

При коллизии поиск альтернативной ячейки в таблице по определённому алгоритму.

Линейный поиск (Linear Probing)

class HashTableLinearProbing:
    def __init__(self, size=10):
        self.size = size
        self.table = [None] * size
        self.keys = [None] * size
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        index = self._hash(key)
        # Ищем первую свободную ячейку
        while self.table[index] is not None:
            if self.keys[index] == key:
                self.table[index] = value
                return
            index = (index + 1) % self.size
        
        self.table[index] = value
        self.keys[index] = key
    
    def get(self, key):
        index = self._hash(key)
        while self.table[index] is not None:
            if self.keys[index] == key:
                return self.table[index]
            index = (index + 1) % self.size
        return None

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

Квадратичный поиск (Quadratic Probing)

def _next_index(self, index, attempt):
    return (index + attempt ** 2) % self.size

Уменьшает кластеризацию лучше, чем линейный поиск.

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

class HashTableDoubleHashing:
    def __init__(self, size=10):
        self.size = size
        self.table = [None] * size
        self.keys = [None] * size
    
    def _hash1(self, key):
        return hash(key) % self.size
    
    def _hash2(self, key):
        # Вторая хеш-функция должна быть взаимно простой с size
        return 1 + (hash(key) % (self.size - 1))
    
    def insert(self, key, value):
        index = self._hash1(key)
        step = self._hash2(key)
        
        while self.table[index] is not None:
            if self.keys[index] == key:
                self.table[index] = value
                return
            index = (index + step) % self.size
        
        self.table[index] = value
        self.keys[index] = key

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

3. Динамическое расширение таблицы (Rehashing)

Когда коэффициент заполнения превышает порог, таблица увеличивается.

class HashTableWithRehashing:
    def __init__(self, initial_size=8):
        self.size = initial_size
        self.table = [[] for _ in range(self.size)]
        self.count = 0
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def _rehash(self):
        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, value):
        # Проверяем коэффициент заполнения
        if self.count / self.size > 0.75:
            self._rehash()
        
        index = self._hash(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        
        self.table[index].append((key, value))
        self.count += 1

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

5. В Python на практике

Python использует открытую адресацию с компактным хешированием для словарей:

# Python dict — оптимальная реализация
my_dict = {"key1": "value1", "key2": "value2"}

# Автоматическое расширение
for i in range(1000):
    my_dict[f"key_{i}"] = i  # Внутри происходит rehashing

Вывод: выбор метода зависит от требований к производительности, памяти и специфики данных.