boost :: hash_combine vs semplice XOR'ing

Question

Quando si utilizza la libreria Boost, i fuction boost::hash_combine funziona così:

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

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

Qual è il vantaggio di questo approccio vs semplicemente XOR-ing?

Con XOR-ing, si può anche usare la funzione di hash per usare i contenitori non ordinati come chiavi, mentre questo dipende dall'ordine.

Answer 1

Ci sono molti contenitori ordinati come le liste. Se si utilizza XOR, in pratica si dice che lo [0, 1] è lo stesso di [1, 0]. Questo ovviamente non è il caso. È molto più semplice sovrascrivere il metodo per i contenitori non ordinati piuttosto che imporre uno che creerà molte collisioni per quelli ordinati. XOR ha molte altre cattive proprietà. Ad esempio, se hai elementi duplicati, si annulleranno a vicenda.

Alla fine l'idea di un hash deve essere ragionevolmente sicura che non si ottiene lo stesso valore per più elementi. XOR non si adatta a questa proprietà da solo.