Что такое коллизия в хеш-таблице?

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

Пример возникновения (псевдокод):

def simple_hash(key, table_size):
    return len(key) % table_size

# Обе строки дают одинаковый хеш для table_size = 10
index1 = simple_hash("John", 10)  # 4 % 10 = 4
index2 = simple_hash("Anna", 10)  # 4 % 10 = 4 -> КОЛЛИЗИЯ

Основные методы разрешения коллизий:

1. Метод цепочек (Separate Chaining): Каждая ячейка массива содержит связный список (или другую структуру) всех элементов, попавших в неё.

   // Упрощенное представление
   HashMap<Integer, LinkedList<Entry>> table;
   // table[hash].add(new Entry(key, value));

   • + Простота, неограниченное количество элементов.
   • - Дополнительные затраты памяти на указатели, в худшем случае поиск O(n).

2. Открытая адресация (Open Addressing): При коллизии элемент помещается в другую, свободную ячейку таблицы, согласно выбранному алгоритму проб.

   • Линейное пробирование: index = (hash + i) % size
   • Квадратичное пробирование: index = (hash + i^2) % size
   • Двойное хеширование: index = (hash1 + i * hash2) % size
   • + Лучшая локальность кэша, нет дополнительных структур.
   • - Сложнее удаление, требуется контроль коэффициента заполнения.

На практике: В Java HashMap до определённого размера использует открытую адресацию, затем переходит на цепочки. В Python dict использует открытую адресацию. Выбор метода влияет на производительность в конкретных сценариях.