AuD Übung Hashverfahren (05)

Hashtabellen und Offenes Verfahren

In dieser Übung soll eine Hashtabelle mit zugehörigen Operationen einfügen, entfernen, und suchen erstellt werden. Es wird das offene Hashverfahren betrachtet.

Aufgabe 1. Welche Vor- und Nachteile haben offene Hashverfahren gegenüber verketteten Verfahren?

• Es sollen die Überläufer innerhalb der Tabelle gespeichert werden
• Es sollen Datensätze durch die Hashtabelle referenziert (nicht eingebettet) werden:

data : {
  name : string,
  year : float,
  id : int
}

Aufgabe 2. Die Datensätze werden durch die Klasse Data implementiert. Implementiere die Klasse Data.

cHVibGljIGNsYXNzIERhdGEgewogIFN0cmluZyBuYW1lOwogIGludCB5ZWFyOwogIGludCBpZDsKICBwdWJsaWMgRGF0YSAoU3RyaW5nIF9uYW1lLGludCBfeWVhcixpbnQgX2lkKSB7CiAgICB0aGlzLm5hbWU9X25hbWU7CiAgICB0aGlzLnllYXI9X3llYXI7CiAgICB0aGlzLmlkPV9pZDsKICB9CiAgcHVibGljIFN0cmluZyBuYW1lICgpIHsKICAgIHJldHVybiB0aGlzLm5hbWU7CiAgfQogIHB1YmxpYyBpbnQgeWVhciAoKSB7CiAgICByZXR1cm4gdGhpcy55ZWFyOwogIH0KICBwdWJsaWMgaW50IGlkICgpIHsKICAgIHJldHVybiB0aGlzLmlkOwogIH0KfQ==

Aufgabe 3. Wähle eine geeignete Größe N der Hashtabelle. Wir erwarten bis zu 20 Einträge.?

Aufgabe 4. Erzeuge eine Klasse HashO. Bei der Initialisierung muss ein Array vom Datentyp Data der Größe N erzeugt werden. Die Methoden insert, remove, und search sowie print sollen implementiert werden. Die print Funktion soll die aktuelle Tabelle ausgeben. Weiterhin wird die Hilfsmethode probe benötigt die die Sondierung für 1. die Suche eines freien Platzes und 2. die Suche nach einem Schlüssel ermöglicht und den Tabellenindex als Ergebnis liefert. Der Schlüssel ist das id Feld (eindeutig).

VEJB

• Als Hahsfunktion soll der Klassier k mod N verwendet werden
• Probe bekommt als Startindex denjenigen den die Hashfunktion herausgibt und wo Kollision festgestellt wird
• Die Hahstabelle ist vom Datentyp Data T[]. Die insert Funktion muss ein neues Objekt von Data instantiieren.
• Freie Tabellenplätze werden mit null belegt.
• Frei gewordene Tabellenplätze hier auch! D.h. aber auch dass die Suche bis (N-1) Sondierungen erfordert da wir nicht wissen ob es beim Auffinden eines freien Platzes noch folgende Überläufer gibt.

Aufgabe 5. Implementiere zwei Sondierungsfunktionen: Linear und quadratisch (siehe Vorlesung). Wähle als Tabellengröße N=10 aus um die Tests zu vereinfachen. Es sollen die Belegungen und der erforderliche Suchaufwand (Suche und Einfügen) für beide untersucht werden. Notiere die Ergebnisse. Die Sondierungsfunktion wird bei der Erzeugung der Hahstabelle via probeNum ausgewählt.

Testfälle:

{name:"Henry",year:1988,id:100}
{name:"Lars",year:1988,id:42}
{name:"Birgit",year:1988,id:5}
{name:"Nobody",year:1990,id:333}
{name:"Lisa",year:1992,id:19}
{name:"Karl",year:1990,id:666}
{name:"Udo",year:1981,id:202}
{name:"Margit",year:1982,id:36}