我需要一个快速、简单的散列函数,它为一对值创建一个唯一标识符- 因此和uint32_t
的散列值相同。(2,7)
(7,2)
任何想法?
To answer my own question, the solution is:
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;
}
Which can be improved to the branchless version
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
}
These methods are perfect hash functions - they guarantee zero collisions. However, they have the disadvantage that you cannot hash values above 2^32 - 1
.
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;
};
额外的括号用于编译器 - 优化此表达式会更容易。
如果要创建快速函数,请不要使用任何会破坏 CPU 管道(并且速度很慢)的条件指令(或std::max
/ )。std::min