2
Ich las über das Interview dieser Person "bei einer bekannten Suchfirma".Muss eine Ausgabe der Hash-Funktion kleiner als die Anzahl der Buckets sein?
http://asserttrue.blogspot.com/2009/05/one-of-toughest-job-interview-questions.html
Er wurde eine Frage gestellt, die ihn dazu brachte, eine Hash-Tabelle implementiert. Er sagte, die folgenden:
HASH = INITIAL_VALUE;
FOR EACH (CHAR IN WORD) {
HASH *= MAGIC_NUMBER
HASH ^= CHAR
HASH %= BOUNDS
}
RETURN HASH
I erklärt, dass die Hash-Tabellenarray Länge prime sein sollte, und die Grenzen Zahl kleiner als die Tischlänge, aber coprime auf die Tischlänge.
Warum sollte die BOUNDS-Nummer kleiner als die Anzahl der Buckets sein? Was bewirkt die Koprime gegenüber der Tischlänge? Sollte es nicht ein Nebeneinander der BOUNDS sein?
Danke für die Eingabe Tom. Ich hatte das Gefühl, dass er falsch lag, aber ich musste StackOverflow fragen, ob es nicht ich selbst war, dem es an Wissen fehlte. – Unknown
"BOUNDS sollte die Anzahl der Buckets sein oder die letzten paar Buckets werden zu wenig genutzt", denken Sie, dass dies vielleicht eine Art spezieller Trick ist, wenn die Hashtabelle in der Größe verändert werden muss? – Unknown
Ich stimme völlig zu, dass% BOUNDS völlig fehl am Platz ist. Der Hash einer gegebenen Eingabe sollte * unabhängig * davon sein, für was dieser Hash verwendet wird. Du kannst es als Schlüssel in einer Tabelle verwenden, du kannst es in einem Bogen binden, du kannst es zu \ dev \ null leiten. Die Hash-Funktion sollte glücklicherweise unwissend sein. – leoger