Es gibt zwei grundlegende Methoden zum Implementieren einer Hash-Funktion, die in fast allen Lehrbüchern und CS-Kursen aufgeführt sind:

Teilungsmethode wo wir einfach machenk mod m Im Wesentlichen wird m als Primzahl ausgewählt, die nicht zu nahe an der Potenz von 2 liegt.Multiplikationsmethode Wenn wir k mit einer gut gewählten irrationalen Zahl zwischen 0 und 1 multiplizieren (Knuth schlägt vor, eine Zahl basierend auf dem Goldenen Schnitt zu verwenden), nehmen Sie den Bruchteil des Produkts und verwenden Sie die gewünschte Anzahl höchstwertiger Bits.

In den meisten Lehrbüchern und Kursen werden einige Nachteile für Methode 1 genannt, einschließlich der Tatsache, dass sie teuer ist und die Dinge von m abhängen. Allerdings habe ich noch nie ein Lehrbuch oder einen Kurs gesehen, in dem der einzige Nachteil für Methode 2 erwähnt wurde.

Dies macht Methode 2 wünschenswerter. Darüber hinaus kann die Methode 2 auf modernen Computern sehr effizient ausgeführt werden, wobei die Gleitkomma-Arithmetik insgesamt eliminiert wird. Es sieht also so aus, als wäre Methode 2 zweifelsohne der Gewinner und niemand sollte über Methode 1 sprechen. Aber das ist offensichtlich nicht der Fall. Tatsächlich habe ich noch nie gesehen, wie Methode 2 in praktischen Implementierungen eingesetzt wurde. Es hat also einige Nachteile.

Die Frage ist, was sie sind und warum Methode 1 trotz ihrer Nachteile häufiger angewendet wird.