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

Question

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

Любая идея?

Answer 1

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

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.

Answer 2

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) , который разрушает трубопровод центрального процессора (и медленно), если вы хотите, чтобы сделать быструю функцию.