Fachrat Informatik - Forum

In der aktuellen Übung 8 - Aufgabe 1 soll man eine leere Hashtabelle (Größe: M = 17) mittels Double-Hashing füllen: h1 = (x mod 17) / h2 = (x mod 16) + 1

und die mittleren Zugriffszahlen für erfolgreiche und nicht-erfolgreiche Suche angeben.

Das Füllen ist einfach.

Erfolgreiche Zugriffszahl iist ja noch relativ einfach (1 + 1 + ...) / M.

Aber die nicht-erfolgreiche ist bei 17 Tabellenplätzen ja wohl eine extreme Fleißaufgabe ? Oder gibt es da eine einfachere Lösung ? Ich schau mir doch nicht für 17*16 Möglichkeiten an, wieviele Schlüsselvergleiche jeweils vorgenommen werden müssen ?! Zwar sind manche Tabellenplätze nicht belegt, aber es wäre trotzdem noch eine sehr hohe Zahl an zu untersuchenden Möglichkeiten.

Oder sollen wir uns da ein Programm für schreiben ? Mmm...auch das kostet zu viel Zeit. Zeit. Zeit.

Naja, dann werde ich mich wohl daran setzen müssen...es sei denn, einer kennt ein nützliches Tool, das eben genau das für mich tut

Kann jemand bestätigen, dass die totale Anzahl der Schlüsselvergleiche bei der nicht erfolgreichen Suche eine dreistellige Zahl ist, die mit 2 endet ?

Also Ergebnis: xx2 / (16*17) = ...