0 Daumen
60 Aufrufe

Aufgabe

Gegeben eine Hashtabelle der festen Größe 12. Wähle die geeignetste Familie von Hashfunktionen für i= 0, ...,11 aus und markieren Sie sie mit X:

ai (x) =((x mod 11) + i·(9−(x mod 9))) mod 11

bi (x) =((x mod 12) +i·(7− (x mod 7)))mod 12

ci (x) =((x mod 13) +i·(5−(x mod 5))) mod 13

Ansatz:

ich weiß, wie doppeltes Hashing funktioniert, aber hier sind ja gar keine Werte für x vorgeben. Woher kann ich dann erkennen, wlche Hashfunktion am besten geeignet ist? Ich habe leider überhaupt keine Idee für eine Vorgehensweise. Die Lösung ist übrigens ai (x). Aber ich hätte gerne gewusst warum.

Kann mir das bitte jemand erklären?

LG

Marceline, The Vampire Queen

von

1 Antwort

+2 Daumen

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.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...