AuD Übung Hashverfahren (05)

Ziel dieser Übung ist Implentierung und Unersuchung des ADT Hashtabelle mit zugehörigen Operationen.

Ausgabe : 5.12.2025

Abgabe : 14.12.2025

Es dürfen keine Standard Java Packages verwendet werden mit Ausnahme von System und String.

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?

Lösung.

Vorteile: Optimale Ausnutzung der Tabelle, kein zusätzlicher Speicherbedarf, homogenes Verfahren (Verketteung ist heterogen/gemischt Tabelle + Liste)
Nachteile: Sondierung bei Kollision erforderlich, Suche ist aufwendiger, Elemente können nicht vollständig entfernt werden (Platzhalter in einer Kette erforderlich), erhöhte Anzahl von Testungen von Einträgen bei Suche (da auch nicht zur "Kette" gehörnede Einträge untersucht werden müssen)

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.

Datensatz Klasse (websh0)

import java.lang.*;
import uj.lang.*;

public class Data {
  public Data (String name,int year,int id) {
  }
  public String name () {
    return "";
  }
  public int year () {
    return 0;
  }
  public int id () {
    return 0;
  }
}

Lösung.

aW1wb3J0IGphdmEubGFuZy4qOwppbXBvcnQgdWoubGFuZy4qOwoKcHVibGljIGNsYXNzIERhdGEgewogIFN0cmluZyBuYW1lOwogIGludCB5ZWFyOwogIGludCBpZDsKICBwdWJsaWMgRGF0YSAoU3RyaW5nIF9uYW1lLGludCBfeWVhcixpbnQgX2lkKSB7CiAgICB0aGlzLm5hbWU9X25hbWU7CiAgICB0aGlzLnllYXI9X3llYXI7CiAgICB0aGlzLmlkPV9pZDsKICB9CiAgcHVibGljIFN0cmluZyBuYW1lICgpIHsKICAgIHJldHVybiB0aGlzLm5hbWU7CiAgfQogIHB1YmxpYyBpbnQgeWVhciAoKSB7CiAgICByZXR1cm4gdGhpcy55ZWFyOwogIH0KICBwdWJsaWMgaW50IGlkICgpIHsKICAgIHJldHVybiB0aGlzLmlkOwogIH0KfQ==

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

Lösung.

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).

Offene Hashtabelle (websh0)

import java.lang.*;
import uj.lang.*;

public class HashO {
  public HashO (int N,int probeNum) {
  }
  public int hash (int key) {
    return 0;
  }
  public int probe1 (int start, int key) {
    // wenn key == -1 dann Suche nach freien Platz
    return 0;
  }
  public int probe2 (int start, int key) {
    // wenn key == -1 dann Suche nach freien Platz
    return 0;
  }
  public void insert(Data d) {
    return;
  }
  public void remove(int id) {
    return;
  }
  public Data search(int id) {
    return null;
  }
  public void print() {
    return;
  }
}

Lösung.

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}

Test (websh0)

import java.lang.*;
import uj.lang.*;

public class Test {
  public static void main() {
  }
}

Lösung.

VEJB

Test Hash. Ausführung von make (Linux, Mac) oder makew (Windows) und run. (websh0)

Type help or hit TAB for a list of commands.

Hilfe

Created by the NoteBook Compiler Ver. 1.41.2 (c) Dr. Stefan Bosse (Fri Dec 05 2025 14:42:53 GMT+0100 (Central European Standard Time))