Что происходит при коллизии в хэш-таблице?

Коллизии в хэш-таблицах

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

Парадокс дня рождения

Даже для случайно распределённых хэшей коллизии начинают появляться уже при количестве элементов, равном квадратному корню из размера таблицы. Например, в таблице из 10 000 позиций первая коллизия вероятнее всего произойдёт уже при добавлении ~100 элементов.

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

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

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

#include <iostream>
#include <vector>
#include <list>
#include <utility>

template<typename K, typename V>
class HashTable {
private:
    static constexpr size_t TABLE_SIZE = 10;
    std::vector<std::list<std::pair<K, V>>> table;
    
    size_t hash_function(const K& key) const {
        return std::hash<K>{}(key) % TABLE_SIZE;
    }
    
public:
    HashTable() : table(TABLE_SIZE) {}
    
    void insert(const K& key, const V& value) {
        size_t index = hash_function(key);
        
        // Проверяем, есть ли уже такой ключ
        for (auto& pair : table[index]) {
            if (pair.first == key) {
                pair.second = value;  // Обновляем значение
                return;
            }
        }
        
        // Добавляем новую пару в цепочку
        table[index].push_back({key, value});
        std::cout << "Inserted " << key << " at index " << index << std::endl;
    }
    
    bool find(const K& key, V& value) const {
        size_t index = hash_function(key);
        
        // Ищем в цепочке
        for (const auto& pair : table[index]) {
            if (pair.first == key) {
                value = pair.second;
                return true;
            }
        }
        return false;
    }
    
    void display() {
        for (size_t i = 0; i < TABLE_SIZE; i++) {
            std::cout << "Index " << i << ": ";
            for (const auto& pair : table[i]) {
                std::cout << "(" << pair.first << ", " << pair.second << ") ";
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    HashTable<std::string, int> ht;
    
    ht.insert("Alice", 30);
    ht.insert("Bob", 25);
    ht.insert("Charlie", 35);  // Может быть коллизия с Alice
    ht.insert("Diana", 28);
    
    ht.display();
    
    int value;
    if (ht.find("Bob", value)) {
        std::cout << "Found Bob with value: " << value << std::endl;
    }
    
    return 0;
}

// Пример вывода:
// Index 0: (Alice, 30) (Charlie, 35) 
// Index 1: 
// Index 2: (Bob, 25) 
// Index 3: (Diana, 28)

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

• Простая реализация
• Удаление элемента тривиально
• Граждане коллизий не влияют на другие элементы

Недостатки:

• Дополнительная память на указатели в списках
• Кэш-мисс при доступе к элементам в цепочке

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

Все элементы хранятся непосредственно в массиве таблицы. При коллизии ищут следующую свободную позицию по определённому алгоритму.

Linear Probing (Линейный зонд)

template<typename K, typename V>
class HashTableLinear {
private:
    static constexpr size_t TABLE_SIZE = 10;
    std::vector<std::pair<K, V>> table;
    std::vector<bool> is_occupied;
    
    size_t hash_function(const K& key) const {
        return std::hash<K>{}(key) % TABLE_SIZE;
    }
    
public:
    HashTableLinear() : table(TABLE_SIZE), is_occupied(TABLE_SIZE, false) {}
    
    void insert(const K& key, const V& value) {
        size_t index = hash_function(key);
        size_t original_index = index;
        
        // Линейный поиск свободной позиции
        while (is_occupied[index]) {
            if (table[index].first == key) {
                table[index].second = value;  // Обновляем
                return;
            }
            index = (index + 1) % TABLE_SIZE;  // Следующая позиция
            
            if (index == original_index) {
                throw std::overflow_error("Hash table is full!");
            }
        }
        
        // Вставляем в найденную позицию
        table[index] = {key, value};
        is_occupied[index] = true;
        std::cout << "Inserted " << key << " at index " << index << std::endl;
    }
    
    bool find(const K& key, V& value) const {
        size_t index = hash_function(key);
        size_t original_index = index;
        
        while (is_occupied[index]) {
            if (table[index].first == key) {
                value = table[index].second;
                return true;
            }
            index = (index + 1) % TABLE_SIZE;
            if (index == original_index) break;  // Полный цикл
        }
        return false;
    }
};

Quadratic Probing (Квадратичный зонд)

Интервалы поиска: 1, 4, 9, 16, 25... (i²)

// Вместо: index = (index + 1) % TABLE_SIZE;
// Используем: index = (original_index + i*i) % TABLE_SIZE;

void insert_quadratic(const K& key, const V& value) {
    size_t original_index = hash_function(key);
    size_t index = original_index;
    
    for (size_t i = 1; i < TABLE_SIZE; i++) {
        index = (original_index + i * i) % TABLE_SIZE;
        
        if (!is_occupied[index]) {
            table[index] = {key, value};
            is_occupied[index] = true;
            return;
        }
    }
    throw std::overflow_error("Hash table is full!");
}

Double Hashing (Двойное хэширование)

Шаг поиска вычисляется вторая хэш-функция.

size_t hash_function2(const K& key) const {
    return 7 - (std::hash<K>{}(key) % 7);  // Вторая функция
}

void insert_double_hash(const K& key, const V& value) {
    size_t original_index = hash_function(key);
    size_t step = hash_function2(key);
    size_t index = original_index;
    
    for (size_t i = 0; i < TABLE_SIZE; i++) {
        if (!is_occupied[index]) {
            table[index] = {key, value};
            is_occupied[index] = true;
            return;
        }
        index = (index + step) % TABLE_SIZE;
    }
    throw std::overflow_error("Hash table is full!");
}

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

• Эффективное использование памяти
• Хорошая локальность кэша

Недостатки:

• Clustering (группировка) — коллизии создают цепочки
• Сложное удаление элементов (нужно использовать маркеры удаления)

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

здесь α = n/m (коэффициент заполнения: количество элементов / размер таблицы)

Коэффициент заполнения (Load Factor)

α = n / m
где n — количество элементов, m — размер таблицы

• α < 0.5 — хорошо (мало коллизий)
• α = 0.5-0.75 — нормально
• α > 0.75 — надо перехэшировать

При превышении α таблица расширяется (обычно в 2 раза), и все элементы перехэшируются.

Стандартная библиотека C++

std::unordered_map использует chaining (раздельные цепочки):

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> map;
    
    map["Alice"] = 30;
    map["Bob"] = 25;
    map["Charlie"] = 35;
    
    // При коллизии стандартная библиотека использует chaining
    std::cout << "Alice age: " << map["Alice"] << std::endl;
    
    // Информация о коллизиях:
    std::cout << "Bucket count: " << map.bucket_count() << std::endl;
    std::cout << "Load factor: " << map.load_factor() << std::endl;
    
    // Номер buckets для ключа:
    std::cout << "Alice bucket: " << map.bucket("Alice") << std::endl;
    std::cout << "Bucket size: " << map.bucket_size(map.bucket("Alice")) << std::endl;
    
    return 0;
}

Итог

Коллизии в хэш-таблицах неизбежны и разрешаются несколькими методами. Chaining — самый простой и популярный (используется в std::unordered_map). Open addressing экономит память, но сложнее в реализации. Выбор метода зависит от требований к памяти и производительности конкретного приложения.