Ответ
Для целых чисел хорошая хеш-функция должна быстро вычисляться и обеспечивать равномерное распределение. Вот пример комбинированной функции, подходящей для использования в 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);
}Ответ 18+ 🔞
Давай разберёмся с этой хеш-функцией, ёпта. Ты знаешь, что такое хеш? Это как паспорт для числа, чтобы его быстро найти в бардаке, который зовётся unordered_map. Главное, чтобы этот паспорт выдавался мгновенно и чтобы у всех чисел были разные, иначе начнётся пиздец и коллизии.
Вот смотри, классическая проблема: если взять тривиальную функцию, которая просто возвращает само число, то последовательные значения 1, 2, 3, 4... все попадут в соседние корзины. Это пизда рулю, распределение будет, как говно в проруби — всё в одну кучу. Нагрузка на одну корзину будет овердохуища, и поиск превратится в линейный обход списка. Терпения ебать ноль, пока найдёшь нужный элемент.
Поэтому умные дядьки придумали bit-mixing. Суть в том, чтобы взять исходное число и так перемешать его биты, чтобы на выходе получилась каша, не имеющая ничего общего с исходным порядком. Даже если на входе идут подряд 1, 2, 3, на выходе хеши будут разбросаны по всему диапазону, как ошмётки после хорошего взрыва.
Смотри на этот код, ядрёна вошь:
struct IntHash {
std::size_t operator()(int key) const noexcept {
// Превращаем int в uint64_t, чтобы не было знакового расширения, которое может всё испортить
std::uint64_t x = static_cast<std::uint64_t>(key);
// Первый раунд: XOR со сдвигом и умножение на магическое простое число
x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
// Второй раунд: ещё раз перемешиваем
x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
// Финальный аккорд: ещё один XOR для пущей равномерности
x = x ^ (x >> 31);
// Возвращаем как size_t
return static_cast<std::size_t>(x);
}
};Почему это работает? Ну, умножение на большое нечётное число — это как взболтать коктейль, биты начинают взаимодействовать друг с другом. Операция XOR со сдвигом (x ^ (x >> N)) — это классический приём, чтобы младшие биты узнали о существовании старших. Всё вместе это даёт тот самый эффект лавины: изменение даже одного бита на входе кардинально меняет весь выходной хеш. Коллизии, конечно, возможны, но их будет дохуя меньше, чем при тривиальном подходе.
А теперь главное, чувак: не выёбывайся без нужды. Если твои данные — это, например, ID пользователей, которые уже являются случайными 64-битными числами, то тебе эта навороченная функция нахуй не сдалась. Можно просто кастовать uint64_t к size_t и всё. Зачем городить огород? Ты только добавишь лишних тактов процессору. Но если ты засовываев в мапу ключи типа (x, y) координат чанков в игре, которые идут подряд, то тут без перемешивания — просто манда с ушами получится, производительность просядет в сраку.
Вот смотри, как это вставляется в unordered_set:
int main() {
// Указываем нашу кастомную функцию хеширования вторым шаблонным параметром
std::unordered_set<int, IntHash> unique_numbers;
for (int i = 0; i < 100; ++i) {
unique_numbers.insert(i * 12345); // Вставка чисел с плохим распределением
}
// Смотрим, не обосрались ли мы с распределением
std::cout << "Bucket count: " << unique_numbers.bucket_count() << 'n';
std::cout << "Load factor: " << unique_numbers.load_factor() << 'n';
return 0;
}Если load_factor близок к 1, а bucket_count маленький — это плохой знак, контейнер будет постоянно рехешироваться. Наша же функция должна размазать ключи по корзинам равномерно, что и требуется.
Итог, бля: Не изобретай велосипед, если данные уже случайны. Но если есть подозрение ебать, что ключи будут иметь паттерны (последовательные числа, только чётные и т.д.), то бери готовую bit-mixing функцию, как выше. Она проверена, быстра и делает из упорядоченной хуйни — равномерную кашу. И да, код в блоках не трогай, там всё правильно.