Suchen mit Hashtabellen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | a)In einer Hashtabelle mit Kollisionsauflösung durch Listen und rund 100000 Elementen werden häufig Elemente gesucht. Pro Suche sollen nicht mher als durchschnittleich 3 Schlüsselvergleiche durchgeführt werden. Wie groß sollte die Hashtabelle ausgelegt werden, wenn
- in den meisten Fällen die Suche erfolgreich ist
-in den meisten Fällen die Suche erfolglos ist.
b) Es wird eine offene Adressierung verwendet, unter den gleichen Bedingungen wie im Fall a). Wie groß sollte nun die Hashtabelle sein bei linaerem Sondieren bei erfolgreicher Suche?
c) Wie groß ist die erwartete Vergleichszahl, wenn stattdessen quadratisches Sondieren eingesetzt wird, sonst gleiche Voraussetzungen wie in b)? |
Hallo,
ich versteh bei der Aufgabe nicht, wie ich hier genau vorgehen muss.
Ich weiß nur, dass in einer offen adressierten Hashtabelle mit Lastfaktor [mm] \alpha= \bruch{n}{m} [/mm] < 1 die erwartete Suchdauer einer erfolglosen Suche durch [mm] \bruch{1}{1-\alpha} [/mm] beschränkt ist. Und bei erfolgreicher Suche ist die erwartete Suchdauer bei erfolgreicher Suche beschränkt durch [mm] \bruch{1-ln(1-\alpha)}{\alpha}. [/mm] Das weiß ich aus dem Skript.
Was muss ich genau bei a) tun?
b) die lineare Sondierung besitzt folgende HAshfunktion: h(k,i) =(h'(k) +i) mod m
und c) die quadratische Sondierung h(k,i) = (h'(k)+ c i + d [mm] i^{2})mod [/mm] m, mit c,d konstant
Kann mir bitte jemand helfen und mir erklären, wie ich hier vorzugehen habe?
Danke im Voraus.
fs
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 04:49 Do 08.06.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
