Come creare un buon hash_combine con output a 64 bit (ispirato a boost :: hash_combine)

Question

Attualmente Boost ha una funzione hash_combine che emette un numero intero senza segno a 32 bit (per essere precisi, size_t). Alcuni riferimenti:

http://www.boost.org/doc/libs/1_43_0/doc/html/hash/reference.html#boost.hash_combine

http://www.boost.org/doc/libs/1_43_0/doc/html/hash/combine.html

Magic number in boost::hash_combine

vorrei esplorare su come creare la versione a 64 bit di hash_combine.

La prima cosa è ottenere il rapporto aureo o qualsiasi altro numero irrazionale in 64 bit.

La seconda parte consiste nell'utilizzare i turni. Questa parte è piuttosto complicata e mi piacerebbe chiedere se ci sono buone pratiche o guida sull'uso dei turni per ottenere i valori hash? O scegliendo turni come il codice originale:

seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); 

è totalmente casuale?

Inoltre, come valutare l'output di hash_combine per assicurarsi che non crei più collisioni rispetto alla funzione di hash originale hash_value?

Answer 1

Leggere http://burtleburtle.net/bob/hash/doobs.html per alcune informazioni di base sulla progettazione della funzione hash e il resto degli articoli in http://burtleburtle.net/bob/hash/ per informazioni più dettagliate. CityHash è stato testato utilizzando http://code.google.com/p/smhasher/ e probabilmente è possibile testare il proprio hash_combine utilizzando la stessa suite di test.

Anche se non sono un esperto di hashing, i disegni delle recenti funzioni di hash mi portano a credere che l'uso della spinta di 2 turni della tecnica hash_combine() non sia più all'avanguardia e possa essere migliorato.

Answer 2

Se si desidera solo un hash_combine che blocca 2 valori a 64 bit in uno e non è necessaria una nuova funzione di hash per le stringhe, è sufficiente sollevare un po 'di codice da CityHash, qualcosa di simile (assumendo size_t è un numero intero senza segno a 64 bit, aggiungere la tua parte preferita del preprocessore o un modello inganno per convalidare che):

template <class T> inline void hash_combine(std::size_t& seed, const T& v) 
{ 
    std::hash<T> hasher; 
    const std::size_t kMul = 0x9ddfea08eb382d69ULL; 
    std::size_t a = (hasher(v)^seed) * kMul; 
    a ^= (a >> 47); 
    std::size_t b = (seed^a) * kMul; 
    b ^= (b >> 47); 
    seed = b * kMul; 
} 

(penso che riproduce questo frammento qui e altrove è OK perché non costituisce una 'porzione sostanziale' del codice CityHash, ma si prega di verificare i diritti di licenza di CityHash & per decidere autonomamente)