C++ - Perché boost: hash_combine è il modo migliore per combinare i valori hash?

Question

Ho letto in altri post che questo sembra essere il modo migliore per combinare i valori hash. Qualcuno potrebbe rompere questo e spiegare perché questo è il modo migliore per farlo?

template <class T> 
inline void hash_combine(std::size_t& seed, const T& v) 
{ 
    std::hash<T> hasher; 
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2); 
} 

Modifica: L'altra questione sta chiedendo solo per il numero magico, ma mi piacerebbe ottenere conoscere l'intera funzione, non solo questa parte.

Answer 1

Essendo il "migliore" è polemico.

Essere "buoni", o anche "molto buoni", almeno superficialmente, è facile.

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

Ci presume seed è il risultato precedente hasher o di questo algoritmo.

^= significa che i bit sulla sinistra e i bit sulla destra cambiano tutti i bit del risultato.

hasher(v) si presume che sia un discreto hash su v. Ma il resto è difesa nel caso non sia un hash decente.

0x9e3779b9 è un valore a 32 bit (potrebbe essere esteso a 64 bit se size_t era 64 bit discutibile) che contiene metà 0 e metà 1 s. È fondamentalmente una serie casuale di 0 e 1 eseguita facendo approssimare una costante irrazionale particolare come valore di punto fisso in base 2. Questo aiuta a garantire che se l'hasher restituisce valori errati, otteniamo ancora una macchia di 1s e 0s nel nostro output.

(seed<<6) + (seed>>2) è un po 'shuffle del seme in arrivo.

Immaginate che mancasse la costante 0x. Immagina che l'hasher restituisca la costante 0x01000 per quasi tutti gli v passati. Ora, ogni bit del seme viene distribuito sulla successiva iterazione dell'hash, durante il quale è di nuovo distribuito.

Il seed ^= (seed<<6) + (seed>>2)0x00001000 diventa 0x00041400 dopo una iterazione. Quindi 0x00859500. Mentre ripetete l'operazione, qualsiasi bit impostato viene "spalmato" sopra i bit di uscita. Alla fine i bit destro e sinistro entrano in collisione e trasportano spostando il bit impostato da "posizioni pari" a "posizioni dispari".

I bit dipendenti dal valore di un seme di input crescono in modo relativamente rapido e complesso quando l'operazione di combinazione ricorre sull'operazione di semina. L'aggiunta di cause porta, che sparge ancora di più le cose. La costante 0x aggiunge una serie di bit pseudo casuali che rendono noiosi i valori hash occupare più di alcuni bit dello spazio hash dopo essere stati combinati.

'grazie all'addizione asimmetrici (combinando gli hash di "dog" e "god" dà risultati diversi), gestisce valori hash foratura (caratteri mappatura al loro valore ASCII, che implica soltanto girarsi una manciata di bit). Ed è ragionevolmente veloce.

Le combinazioni di hash più lente che sono crittograficamente forti possono essere migliori in altre situazioni. Io, ingenuamente, presumerei che fare i turni sia una combinazione di turni pari e dispari potrebbe essere una buona idea (ma forse l'aggiunta, che sposta anche i bit da bit dispari, rende meno un problema: dopo 3 iterazioni, seme solitario in arrivo i pezzi entrano in collisione e aggiungono e causano un carry).

Lo svantaggio di questo tipo di analisi è che basta un errore per rendere davvero pessima una funzione di hash. Sottolineare tutte le cose buone non aiuta molto. Quindi un'altra cosa che lo rende buono ora è che è ragionevolmente famoso e in un repository open-source, e non ho sentito nessuno dire perché è cattivo.