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

Способы устранения хеш-коллизий

Хеш-коллизия происходит, когда две разные записи получают одинаковый хеш-код. Поскольку пространство хешей конечно, коллизии неизбежны. Существует несколько проверенных способов их разрешения.

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

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

template<typename K, typename V>
struct Node {
    K key;
    V value;
    Node* next;
};

void insert(const K& key, const V& value) {
    size_t hash = hashFunction(key) % table.size();
    Node* newNode = new Node{key, value, nullptr};
    
    newNode->next = table[hash];
    table[hash] = newNode;
}

V* find(const K& key) {
    size_t hash = hashFunction(key) % table.size();
    Node* current = table[hash];
    
    while (current != nullptr) {
        if (current->key == key) {
            return &current->value;
        }
        current = current->next;
    }
    return nullptr;
}

Преимущества:

• Простая реализация
• Удаление не требует перехеширования
• Работает хорошо при высоком load factor
• Реализована в std::unordered_map

Недостатки:

• Дополнительная память на указатели
• Cache misses при обходе цепи
• В худшем случае O(n)

2. Открытая адресация - Linear Probing

При коллизии ищем следующую пустую ячейку последовательно.

void insert(const K& key, const V& value) {
    size_t hash = hashFunction(key) % table.size();
    size_t index = hash;
    
    while (table[index].occupied) {
        index = (index + 1) % table.size();
        if (index == hash) {
            throw runtime_error("Table is full");
        }
    }
    
    table[index] = {key, value, true};
}

V* find(const K& key) {
    size_t hash = hashFunction(key) % table.size();
    size_t index = hash;
    
    while (table[index].occupied) {
        if (table[index].key == key) {
            return &table[index].value;
        }
        index = (index + 1) % table.size();
        if (index == hash) break;
    }
    return nullptr;
}

Проблема: Primary Clustering

Коллизии создают цепочки подряд идущих заполненных ячеек, что усугубляет проблему.

Индекс:  0  1  2  3  4  5  6  7  8
Занято:  X  X  X  -  X  X  X  -  -

Поиск новой позиции требует много итераций.

3. Quadratic Probing (квадратичное пробирование)

Вместо линейного пробирования используем шаг i^2.

void insert(const K& key, const V& value) {
    size_t hash = hashFunction(key) % table.size();
    size_t index = hash;
    size_t i = 1;
    
    while (table[index].occupied) {
        index = (hash + i * i) % table.size();
        i++;
        if (i > table.size()) {
            throw runtime_error("Table is full");
        }
    }
    
    table[index] = {key, value, true};
}

Последовательность проб: hash, hash+1, hash+4, hash+9, hash+16...

Преимущества:

• Лучше распределение чем linear probing
• Снижает clustering

Недостатки:

• Может не посетить все ячейки
• Требует размер таблицы простым числом для гарантии

4. Double Hashing (двойное хеширование)

Используем вторую хеш-функцию для определения размера шага.

void insert(const K& key, const V& value) {
    size_t hash1 = hashFunction1(key) % table.size();
    size_t hash2 = hashFunction2(key) % (table.size() - 1) + 1;
    size_t index = hash1;
    
    while (table[index].occupied) {
        index = (index + hash2) % table.size();
    }
    
    table[index] = {key, value, true};
}

Последовательность: hash1, hash1+hash2, hash1+2hash2, hash1+3hash2...

Преимущества:

• Отличное распределение элементов
• Минимизирует clustering
• Обычно требует O(1) в среднем
• Посещает все ячейки если hash2 взаимно просто с размером

Недостатки:

• Нужны две хеш-функции
• Сложнее реализовать

5. Robin Hood Hashing

Более продвинутый метод, который распределяет элементы более равномерно через "перераспределение богатства".

struct Entry {
    K key;
    V value;
    size_t distance;
};

void insert(const K& key, const V& value) {
    size_t index = hashFunction(key) % table.size();
    Entry entry = {key, value, 0};
    
    while (table[index].occupied) {
        if (entry.distance > table[index].distance) {
            swap(entry, table[index]);
        }
        index = (index + 1) % table.size();
        entry.distance++;
    }
    
    table[index] = entry;
}

Идея: Элемент "богач" вытесняет более близкого к дому элемента "бедняка".

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

Рекомендации

Используйте Chaining если:

• Нужна простота реализации
• Load factor может быть > 1
• Удаления часты

Используйте Open Addressing если:

• Важна кеш-локальность памяти
• Load factor < 0.75
• Нет частых удалений

Используйте Double Hashing если:

• Нужна оптимальная производительность
• Есть возможность реализовать две функции

Практические советы

// Хорошая хеш-функция уменьшает коллизии
size_t goodHash(const string& s) {
    size_t hash = 5381;
    for (char c : s) {
        hash = ((hash << 5) + hash) + c;  // hash*33 + c
    }
    return hash;
}

// Контролируйте load factor
map.max_load_factor(0.75);

// Предварительно выделяйте память
map.reserve(10000);

Заключение

В современном C++ используется Chaining (std::unordered_map), так как он обеспечивает хороший баланс между простотой и производительностью. Выбор метода зависит от конкретных требований и характеристик данных.