Générer uint64_t clé de hachage avec plusieurs entiers uint32_t

Question

Je suis confronté au même problème que Eduardo (Generate a hash sum for several integers) mais le mien est un peu différent comme dit dans le titre.

J'ai quatre entiers 32 bits et j'ai besoin de générer une clé unique 64 bits. Ce que j'ai fait pour l'instant est de générer une concaténation de chaîne des quatre entiers séparés par un '/', puis de générer un CRC avec la chaîne.

char id_s[64]; 
sprintf(id_s, "%d/%d/%d/%d", a, b, c, d); 
uint64_t id = CRC(id_s); 

Mais le problème est que je dois le faire plusieurs millions de fois, donc il semble être très consommateur de CPU. Je pensais donc à stocker directement les quatre entiers dans un seul entier.

Cela peut être fait facilement si les quatre entiers où 16bits entiers. Cela pourrait simplement être fait en utilisant l'opérateur de décalage de bits. Avec quatre entiers de 32 bits, je dois mettre 128 bits dans un seul entier de 64 bits.

Est-ce que quelqu'un a une suggestion?

Answer 1

En fonction de la nature de vos données d'entrée, quelque chose de presque comme ce que vous suggérez pourrait fonctionner très bien:

uint64_t id = static_cast<uint64_t>(a & 0xFFFFu) << 48 + static_cast<uint64_t>(b & 0xFFFFu) << 32 + static_cast<uint64_t>(c & 0xFFFFu) << 16 + static_cast<uint64_t>(d & 0xFFFFu);

Tant que les bits supérieurs des valeurs sont des bits assez constants et les plus faibles relativement Au hasard, cela devrait vous rapprocher. Vous essayez d'entasser 128 bits de données en 64 bits, vous devez donc jeter des données quelque part. C'est juste une question de quels morceaux à jeter, et comment vous le faites.

Answer 2

Je pense que votre meilleur pari serait d'utiliser XOR:

uint64_t makeId(uint32_t a, uint32_t b, uint32_t c, uint32_t d) 
    { 
    uint64_t id = a; 
    id <<=11; 
    id ^= b; 
    id <<=11; 
    id ^= c; 
    id <<=10; 
    id ^=d; 

    return id; 
    } 

Cela fonctionne assez bien si vos entrées sont bien réparties et utiliser tous les 32 bits. Comme Mark a dit, vous ne pouvez pas transformer 128 bits en 64 bits sans duplication.