Es ist nicht trivial, die Güte bzw. Performance zweier Hash-Funktionen zu vergleichen. Wie performant und kollisionsfrei Eingangswerte in einen Tabellen-Index umgewandelt werden, hängt in erster Linie davon ab, in welcher Reihenfolge die Eingangswerte eintreffen - und die ist i.A. rein zufällig.
Mit der passenden Reihenfolge der Eingangswerte kann man jede Hash-Funktion zum "Sieger" machen. Selbiges gilt übrigens auch für Sortierverfahren.
Was soll eine Hash-Funktion leisten ? Sie soll bestimmte Eingangswerte x einem Tabellen-Index [0,1,...,m-1] (m = Tabellenlänge) zuordnen.
h(x) -> {0,1,2,...,m-1}
Um die Wertemenge von h(x) auf die Länge der Tabelle einzugrenzen, verwendet man am Ende der des Hash-Algorithmus g(x) in der Regel die Funktion mod().
h(x) = g(x) mod m
Angenommen, man verwendet eine Hash-Tabelle mit 8 Einträgen (Index 0 bis 7) und eine beliebige Hash-Funktion g(x)
h(x) = g(x) mod m
Dann macht es streng genommen keinen Sinn, m < 8 oder m > 8 zu wählen. Im ersten Fall werden die höchsten Indizies der Tabelle nie beschreiben, im zweiten Fall erzeugt die Hash-Funktion nicht existente (zu grosse) Indizes.
Unter diesem Aspekt fällt ci schon mal aus, denn mit mod 13 am Ende werden Indizes mit dem Wert 12 erzeugt, dazu bräuchte die Tabelle dann 13 Einträge.
Streng genommen fällt auch ai aus, denn dieser Algorithmus erzeugt niemals den letzten Index mit dem Wert 11. Die Tabelle mit der Länge 12 wird also nicht optimal ausgenutzt.
Das leistet nur Algorithmus bi. Eventuell fällt der aber durch, weil
- m eine Primzahl sein sollte
- h2(x) (ohne Multiplikation mit i) teilerfremd zu m sein sollte
Das ist nur bei ai der Fall. Bei bi ist m keine Primzahl und für h( x=1,i = 0) ist h2 = 6, also nicht teilferfremd zu 12.
Das alles ist meiner Ansicht nach ein Streit um des Kaisers Bart und einer Frage der Definition. Welche Uhr geht genauer, eine Rolex oder eine Uhr, die steht ? Die stehende, denn diese zeigt zweimal am Tag exakt die richtige Zeit an, die Rolex nie, denn die liegt immer um ein Epsilon daneben.
