Ist der Hash Funktion in AWL geben 1-1 Zuordnung zwischen char * und size_t?

Question

Ich habe ein Paar Ich weiß, dass der Wert des pair.first nicht mehr als 1000 sein. Ich weiß auch, dass der pair.second, die Zeichenfolge, ist immer 1 Wort. Nie mehr als 1 Wort.
Also, den Hash-Wert für das Paar zu konstruieren ich folgendes tue:

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

Ich denke, dies so lange, eindeutige Werte geben wird als der Hash-Wert von Strings nicht zu groß ist und dass H (p.second) wird 1-1 Zuordnungen geben. Sind diese Annahmen gültig?

Danke,

Answer 1

Per Definition kann ein Hash nicht eins-zu-eins aufgrund des Schubfachprinzips. I.E., gibt es 2 ^ 32 mögliche Hash-Werte, aber weit mehr möglich Saiten. Es muss also zwei Strings mit dem gleichen Hash-Wert sein.

Zweitens, sind Sie fast sicher verursachen Überlauf von Ihrem Hash-Wert mit 1000 multipliziert wird, da ein Hash sollte alle 32 Bits verwenden. Sie sind viel besser dran, die int-Hashing und dann die Hashes zu mischen. Boost hat eine hash_combine Funktion: a + 0x9e3779b9 + (b << 6) + (b >> 2);