L'hash < char * > la funzione in STL fornisce 1-1 mapping tra char * e size_t?

Question

Ne ho un paio So che il valore di pair.first non può essere superiore a 1000. So anche che pair.second, la stringa, è sempre di 1 parola. Mai più di 1 parola.
Quindi, per costruire il valore Hash per la coppia sto facendo quanto segue:

pair<int,string> p;
hash<char*> H;
hash_vale = H(p.second)*1000 + p.first;

Penso che questo darà valori univoci purché il valore di hash delle stringhe non sia troppo grande e che H (p. secondo) fornirà 1-1 mapping. Questi presupposti sono validi?

Grazie,

Answer 1

Per definizione, un hash non può essere uno a uno a causa del principio del buco del piccione. Ad esempio, ci sono 2 ^ 32 possibili valori hash, ma stringhe molto più possibili. Quindi devono esserci due stringhe con lo stesso valore di hash.

In secondo luogo, quasi sicuramente stai causando un overflow moltiplicando il valore dell'hash per 1000, poiché un hash dovrebbe usare tutti i 32 bit. Stai molto meglio scartando l'int e poi mescolando gli hash. Boost ha una funzione hash_combine : a + 0x9e3779b9 + (b < < 6) + (b > > 2);