Что такое коллизия в HashMap?

Что такое коллизия в HashMap?

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

Пример коллизии

std::unordered_map<std::string, int> map;
map.size() = 16;  // Размер таблицы

// Хеш-функция просто берёт остаток от количества ячеек
структура данных:
int hash("apple") = 123 % 16 = 11
int hash("orange") = 456 % 16 = 8
int hash("banana") = 235 % 16 = 11  // КОЛЛИЗИЯ! Как "apple"

Двое ключей ("apple" и "banana") хотят занять позицию 11.

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

1. Chaining (цепочки, привязка)

На каждой позиции хранится список (linked list) всех элементов с одинаковым хешем:

Index   Value
  0     []
  1     []
  ...
  8     [orange]
  ...
  11    [apple] -> [banana]  // Цепочка из 2 элементов
  ...
  15    []

Поиск: hash(key) → перейти в ячейку → пройти по цепочке, сравнивая ключи.

std::unordered_map в C++ использует именно этот метод.

std::unordered_map<std::string, int> map;
map["apple"] = 1;
map["banana"] = 2;
// Внутри: оба элемента в позиции 11, связаны в цепочку

int value = map["apple"];  // O(1) в среднем, O(n) в худшем

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

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

Linear Probing:

Если позиция i занята, попробуем i+1, i+2, i+3...

Вставка "banana" при коллизии с "apple" на позиции 11:
  11: [apple] -> занято
  12: [] -> свободно!
  banana -> позиция 12

Quadratic Probing:

Пробуем позиции: i, i+1, i+4, i+9, i+16... (i+k²)
Уменьшает clustering (скопление элементов подряд)

Double Hashing:

Вторая хеш-функция определяет шаг: i, i+h₂(key), i+2*h₂(key)...
Расстояние между попытками зависит от ключа

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

Коэффициент загрузки (load factor)

load_factor = количество элементов / размер таблицы

// Хороший диапазон: 0.5 - 0.75
// При превышении обычно выполняется rehashing

Когда load factor > 0.75, HashMap часто автоматически удваивает размер:

std::unordered_map<std::string, int> map;
map.max_load_factor(0.8);  // Установить свой порог

Плохая хеш-функция — проблема

// Плохая функция (много коллизий)
int bad_hash(int key) {
    return key % 16;  // Если ключи: 16, 32, 48, 64... - все коллизии!
}

// Хорошая функция (распределение)
int good_hash(int key) {
    return (key * 2654435761U) >> 27;  // Множитель Fibonacci
}

Для C++ разработчика

std::unordered_map/set использует chaining по умолчанию. Для критичных по производительности мест можно:

// Резервировать место заранее
std::unordered_map<int, int> map;
map.reserve(10000);  // Избежать rehashing

// Пользовательская хеш-функция
struct MyHash {
    size_t operator()(int key) const {
        return std::hash<int>{}(key ^ 0x9e3779b9);
    }
};
std::unordered_map<int, int, MyHash> map;

Совет: Всегда профилируйте! Иногда std::map (красно-чёрное дерево, O(log n)) работает быстрее, чем HashMap с плохой хеш-функцией.