Приведи пример хеш-функции для целого числа (int) в C++.

Для целых чисел хорошая хеш-функция должна быстро вычисляться и обеспечивать равномерное распределение. Вот пример комбинированной функции, подходящей для использования в std::unordered_map или std::unordered_set.

Пример: функция, смешивающая биты (bit-mixing hash)

#include <cstdint>
#include <functional> // для std::hash

// 1. Простая и эффективная функция (подходит для вставки в стандартные контейнеры)
struct IntHash {
    std::size_t operator()(int key) const noexcept {
        // Используем умножение на большое простое число и сдвиг
        std::uint64_t x = static_cast<std::uint64_t>(key);
        x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
        x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
        x = x ^ (x >> 31);
        return static_cast<std::size_t>(x);
    }
};

// 2. Использование с std::unordered_set
#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int, IntHash> unique_numbers;

    for (int i = 0; i < 100; ++i) {
        unique_numbers.insert(i * 12345); // Вставка чисел с плохим распределением
    }

    // Проверяем распределение по корзинам (bucket)
    std::cout << "Bucket count: " << unique_numbers.bucket_count() << 'n';
    std::cout << "Load factor: " << unique_numbers.load_factor() << 'n';

    return 0;
}

Почему эта функция эффективна:

• Быстрая: Использует только целочисленные операции (XOR, сдвиг, умножение).
• Хорошее распределение: Многораундовое перемешивание бит минимизирует коллизии даже для последовательных чисел.
• Детерминированная: Для одного входного значения всегда возвращает одинаковый хеш.

Альтернатива для простых случаев: Если производительность критична, а данные достаточно случайны, можно использовать тривиальную функцию, но это может привести к кластеризации.

// Тривиальная функция (может плохо распределять последовательные числа)
std::size_t trivial_hash(int key) {
    return static_cast<std::size_t>(key);
}