Как обойти коллизию?

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

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

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

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

Методы разрешения коллизий

1. Цепочки (Chaining)

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

Пример:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]  # Создаем список списков для хранения цепочек
​
    def hash_function(self, key):
        return hash(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)  # Находим индекс для ключа
        for k, v in self.table[index]:  # Проходим по цепочке
            if k == key:
                return v  # Возвращаем значение, если ключ найден
        return None  # Возвращаем None, если ключ не найден

• __init__: Инициализирует хеш-таблицу заданного размера, создавая список списков для хранения цепочек.
• hash_function: Вычисляет индекс для ключа, используя встроенную функцию hash и операцию взятия остатка.
• insert: Добавляет пару (ключ, значение) в соответствующую цепочку.
• get: Ищет ключ в цепочке и возвращает соответствующее значение.

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

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

Пример:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size  # Создаем список фиксированного размера
​
    def hash_function(self, key):
        return hash(key) % self.size  # Вычисляем индекс на основе хеш-функции
​
    def insert(self, key, value):
        index = self.hash_function(key)  # Находим начальный индекс для ключа
        while self.table[index] is not None:  # Ищем свободную ячейку
            index = (index + 1) % self.size  # Переходим к следующей ячейке
        self.table[index] = (key, value)  # Сохраняем пару (ключ, значение)
​
    def get(self, key):
        index = self.hash_function(key)  # Находим начальный индекс для ключа
        while self.table[index] is not None:
            k, v = self.table[index]
            if k == key:
                return v  # Возвращаем значение, если ключ найден
            index = (index + 1) % self.size  # Переходим к следующей ячейке
        return None  # Возвращаем None, если ключ не найден

• __init__: Инициализирует хеш-таблицу заданного размера, создавая список фиксированного размера.
• hash_function: Вычисляет индекс для ключа.
• insert: Ищет свободную ячейку, начиная с вычисленного индекса, и сохраняет пару (ключ, значение).
• get: Ищет ключ, начиная с вычисленного индекса, и возвращает соответствующее значение.