Funkcja skrótu przemiennego dla par wartości uint32_t

Question

Potrzebuję szybkiej, prostej funkcji skrótu, która tworzy unikalny identyfikator dla pary wartości uint32_t - tak więc ta sama wartość mieszania dla (2,7) i (7,2).

Każdy pomysł?

Answer 1

Aby odpowiedzieć na moje własne pytanie, rozwiązaniem jest:

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; 
} 

które mogą być ulepszone do branchless wersji

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 
} 

Metody te są doskonałe funkcje skrótu - gwarantują one zera kolizji. Mają jednak tę wadę, że nie można wartości mieszania powyżej 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; 
}; 

Dodatkowe nawiasy są dla kompilatora - łatwiej będzie zoptymalizować to wyrażenie.

Nie używaj żadnych instrukcji warunkowych (lub std::max/std::min) , które przerywają procesor (i jest wolny), jeśli chcesz wykonać szybką funkcję.