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

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

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

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

Хеш для "alice": 54321 % 8 = 1
Хеш для "bob":   54329 % 8 = 1  ← Коллизия! Оба хотят в бакет 1

Хороший дизайн хеш-таблицы сводит коллизии к минимуму.

1. Хорошая хеш-функция

Требования к хеш-функции:

• Распределение почти равномерное (не кластеризация)
• Быстрое вычисление
• Детерминированность (одинаковый ключ = одинаковый хеш)
• Не предсказуемость (для защиты от DoS атак)

// Плохая хеш-функция
struct BadHash {
    size_t operator()(const std::string& s) const {
        return s[0];  // Только первый символ!
    }
};

// Хорошая хеш-функция (FNV-1a)
struct GoodHash {
    size_t operator()(const std::string& s) const {
        size_t hash = 14695981039346656037ULL;
        for (char c : s) {
            hash ^= (unsigned char)c;
            hash *= 1099511628211ULL;
        }
        return hash;
    }
};

// Ещё лучше: встроенная в std
std::unordered_map<std::string, int> map1;  // Использует std::hash

2. Размер таблицы

Размер хеш-таблицы критично влияет на коллизии:

// Load factor = количество элементов / размер таблицы
// Если load factor > 1.0, коллизии становятся частыми

std::unordered_map<int, int> map;

// Заранее выделить место
map.reserve(10000);

// Теперь load_factor будет низким, коллизии редкие
for (int i = 0; i < 5000; i++) {
    map[i] = i;
}

std::cout << "Load factor: " << map.load_factor() << "\n";  // 0.5

Оптимальные параметры:

• Load factor < 0.75 — хорошо (мало коллизий, мало потраченного места)
• Load factor = 1.0 — среднее (много коллизий)
• Load factor > 1.5 — плохо (очень много коллизий, нужен rehash)

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

a) Chaining (цепочки)

buckets[0] → nullptr
buckets[1] → [alice, 25] → [bob, 30] → nullptr
buckets[2] → [charlie, 35] → nullptr

// std::unordered_map использует chaining по умолчанию
std::unordered_map<std::string, int> map;
map["alice"] = 25;
map["bob"] = 30;     // Коллизия, добавляется в цепь к alice

Плюсы:

• Простая реализация
• Удаление элемента быстро
• Хорошо работает при высоком load factor

Минусы:

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

b) Open addressing (открытая адресация)

Вставка: ключ "bob", хеш = 1, занято
         ищем следующее свободное: 2 (занято) → 3 (свободно!)
         вставляем в buckets[3]

// Пример реализации с linear probing
class SimpleHashTable {
    std::vector<std::pair<std::string, int>> buckets;
    
public:
    void insert(const std::string& key, int value) {
        size_t hash = std::hash<std::string>()(key) % buckets.size();
        
        // Linear probing: ищем первый пустой бакет
        while (!buckets[hash].first.empty()) {
            hash = (hash + 1) % buckets.size();
        }
        
        buckets[hash] = {key, value};
    }
};

Плюсы:

• Лучше кеш-локальность (все данные в одном массиве)
• Меньше памяти на указатели

Минусы:

• Кластеризация (коллизии группируются)
• Удаление сложное (нужна "tombstone" отметка)
• Плохо при высоком load factor

c) Double hashing

// Вместо линейного проб (hash + 1, hash + 2, ...),
// используем вторую хеш-функцию
size_t hash1(const std::string& s);
size_t hash2(const std::string& s);

void insert(const std::string& key) {
    for (int i = 0; i < bucket_count; i++) {
        size_t idx = (hash1(key) + i * hash2(key)) % bucket_count;
        if (!occupied[idx]) {
            // Вставляем
            break;
        }
    }
}

Плюсы:

• Лучше распределение, чем линейный probing
• Меньше кластеризация

Минусы:

• Медленнее (две хеш-функции)
• Всё ещё сложнее чем chaining

4. Rehashing

std::unordered_map<int, int> map;

std::cout << "Initial buckets: " << map.bucket_count() << "\n";

// Когда load_factor превесит max_load_factor, происходит rehash
for (int i = 0; i < 10000; i++) {
    int old_buckets = map.bucket_count();
    map[i] = i;
    
    if (map.bucket_count() > old_buckets) {
        std::cout << "Rehash! New size: " << map.bucket_count() << "\n";
    }
}

Процесс rehash:

1. Выделить новый, больший массив бакетов (обычно 2x или 1.5x)
2. Пересчитать хеш для каждого элемента
3. Переместить элементы в новые бакеты
4. Освободить старый массив

Стоимость: O(n), где n — количество элементов

5. Cryptographic hashing (для защиты)

// Если нужна защита от DoS атак:
// Используй хеш-функцию с salt

struct SafeHash {
    size_t seed;  // Случайный seed
    
    SafeHash() {
        std::random_device rd;
        seed = rd();
    }
    
    size_t operator()(const std::string& s) const {
        size_t hash = seed;
        for (char c : s) {
            hash = hash * 31 + c;
        }
        return hash;
    }
};

std::unordered_map<std::string, int, SafeHash> secure_map;

Практические рекомендации

// 1. Используй встроенную хеш-функцию std::hash
std::unordered_map<std::string, int> map;

// 2. Заранее выделяй память если знаешь размер
std::unordered_map<int, int> large_map;
large_map.reserve(1000000);

// 3. Следи за load factor
if (map.load_factor() > 0.75) {
    map.rehash(map.bucket_count() * 2);
}

// 4. Для критичного по производительности кода
// рассмотри более специализированные структуры
// (robin hood hashing, hopscotch hashing)

// 5. Профилируй частоту коллизий
std::cout << "Max chain length: " << get_max_chain_length(map) << "\n";

Выводы

• Хорошая хеш-функция — основа эффективной таблицы
• Load factor < 0.75 — оптимальный баланс
• Chaining — надёжный, масштабируемый метод (используется в std)
• Open addressing — быстрее кеш, но сложнее в реализации
• Reserve заранее — избегай частых rehash'ей
• Профилируй — коллизии могут быть узким местом