Коммутативная хеш-функция для пар значений uint32_t

Question

Коммутативная хеш-функция для пар значений uint32_t

Мне нужна быстрая, простая хеш-функция, которая создает уникальный идентификатор для пары uint32_t значения — так же хеш-значение для (2,7) а также (7,2),

Любая идея?

8

algorithm c++hash uint32

Решение

Другие решения

constexpr uint32_t hash_max = ...;

constexpr uint32_t commutative_hash(uint32_t i, uint32_t j) {
return (i*j + (i*i)*(j*j) + (i*i*i)*(j*j*j)) % hash_max;
};

Дополнительные скобки предназначены для компилятора — будет проще оптимизировать это выражение.

Не используйте какие-либо условные инструкции (или std::max/std::min)
который прерывает конвейер процессора (и работает медленно), если вы хотите сделать быструю функцию.

2

Источник

Accepted Answer

Чтобы ответить на мой собственный вопрос, решение:

uint64_t hash(uint32_t x, uint32_t y)
{
const uint64_t a = static_cast<uint64_t>(x);
const uint64_t b = static_cast<uint64_t>(y);

if (x < y) return (b << 32) | a;
else return (a << 32) | b;
}

Что может быть улучшено до версия без ответвлений

uint64_t hash(uint32_t x, uint32_t y)
{
const uint64_t a = static_cast<uint64_t>(x);
const uint64_t b = static_cast<uint64_t>(y);

const uint64_t h0 = (b << 32) | a;
const uint64_t h1 = (a << 32) | b;

return (x < y) ? h0 : h1; // conditional move (CMOV) instruction
}

Эти методы являются идеальными хеш-функциями — они гарантируют ноль столкновений. Однако у них есть недостаток, заключающийся в том, что вы не можете хэшировать значения выше 2^32 - 1,

5