Что такое хэш коллизия и какие методы её разрешения существуют?

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

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

1. Открытая адресация — при коллизии ищется следующая свободная ячейка по определённой последовательности (линейное, квадратичное пробирование, двойное хэширование).
2. Цепочки (chaining) — в каждой ячейке хэш-таблицы хранится связанный список всех элементов с одинаковым хэш-значением.
3. Рехэширование — при коллизии применяется другая хэш-функция.

Пример с цепочками на Python:

hash_table = [[] for _ in range(10)]

def insert(key, value):
    index = hash(key) % 10
    hash_table[index].append((key, value))

insert('apple', 1)
insert('papel', 2)  # возможна коллизия