|
Beispiel:
Schlüsselwerte sind Ganzzahlen, die Hash-Tabelle umfaßt 499 Speicherplätze.
Es soll das Divisionsrestverfahren angewendet werden.
Zu speichernde Werte: 3598, 6093.
3598 mod 499 = 105
6093 mod 499 = 105
Der Datensatz 3598 kann zwar am Speicherplatz 105 abgelegt werden, beim Speichern des Satzes 6093 ergibt sich allerdings das Problem, daß der errechnete Speicherplatz nicht mehr frei ist.
Es ist ein Kollisionsverfahren anzuwenden. Das ist eine Methode, um Schlüssel mit gleichem Ergebnis der Hash-Funktion an anderen Stellen abzulegen und wieder zu finden.
Zurück zum Inhaltsverzeichnis
4. 1. Interne Kollisionsauflösung (Lineares Austesten)
Für das Element wird ein Platz innerhalb der Tabelle gesucht, z. B. wird der nächste bzw. übernächste Platz genommen. Der Nachteil dabei ist die Clusterbildung.
Die Tabelle enthält neben dem Datensatz selbst auch die Anzahl der Datensätze, deren berechneter Hashcode dem tatsächlichen Index an dieser Position entspricht (z. B. an Position 4 wird die Anzahl der Sätze gespeichert, für die als Hashcode 4 errechnet wurde).
Man benötigt außerdem einen speziellen Wert, der anzeigt, daü eine Position in der Hash-Tabelle \"frei\" ist, z. B. bei Strings einen Leerstring oder -1 bei Zahlen (Voraussetzung ist natürlich, daß diese Werte nicht als Schlüssel auftreten können).
Der Vorteil gegenüber dem externen Verfahren ist die schnelle Positionierung. Allerdings wird die Kapazität der Hash-Tabelle bei geringer Auslastung schlecht genutzt.
Durch oftmaliges Löschen und Einfügen von Datensätzen kann sich beim internen Verfahren die Anzahl der Zugriffe stark erhöhen.
Beispiel:
Schlüsselwerte sind Zeichenketten.
H(\"Carmen\") = 2, H(\"Renate\") = 6, H(\"Tina\") = 4, H(\"Veronika\") = 2
Kollisionsverfahren: Neuer Hashcode = Alter Hashcode + 3
Wenn Plätze nicht belegt sind, werden die Personen-ID und der berechnete Index auf -1 gesetzt.
tatsächlicher Index berechneter Index Datensatz-ID Anz. Elemente mit diesem Hashcode
1 -1 0
2 2 Carmen 2
3 -1 0
4 4 Tina 1
5 2 Veronika 0
6 6 Renate 1
Suche nach Datensatz \"Veronika\":
. Hashcode errechnen (im Beispiel: 2)
. Vergleiche Suchschlüssel mit gespeicherter Datensatz-ID auf Position 2 und stelle fest, daü \"Veronika\" \"Carmen\"
. Gehe 3 Positionen weiter
. Erneuter Vergleich mit Datensatz-ID auf Position 5, Suche erfolgreich
Beim Löschen des Datensatzes \"Veronika\" ist zu berücksichtigen, daß die Anzahl der Elemente mit Hashcode 2 (nicht 5) um 1 vermindert werden muß (im Beispiel: Anzahl bei \"Carmen\" auf 1 setzen).
Die durchschnittliche Anzahl der Zugriffe beim Suchen nach einem Datensatz, der tatsächlich in der Tabelle existiert, berechnet sich nach folgender Formel:
0,5 + 1 / (2 * (1 - Auslastung))
Beim erfolglosen Suchen:
0,5 + 1 / (2 * (1 - Auslastung) hoch 2)
Beispiele:
Auslastung 50 % 70 % 80 %
durchschn. Zugriffe bei erfolgloser Suche 2,5 6,1 13,0
durchschn. Zugriffe bei erfolgreicher Suche 1,5 2,2 3,0
Zurück zum Inhaltsverzeichnis
4. 2. Externe Kollisionsauflösung
Anstelle der Daten enthält die Hash-Tabelle nur Zeiger auf die eigentlichen Daten. Bei einer Kollision wird eine verkettete Liste aufgebaut.
Vorteile gegenüber dem internen Verfahren:
. Es können auch mehr Sätze gespeichert werden, als eigentlich in der Hash-Tabelle Platz hätten.
. Der Speicherbereich ist nicht fix, daher wird auch bei geringer Auslastung kein Speicherplatz verschwendet.
. Beim Löschen und Einfügen werden einfache Listenoperationen getätigt.
Nachteile gegenüber dem internen Verfahren:
. Der Vorteil des Hashings, die direkte Positionierung, geht teilweise verloren (weil man bei Kollisionen die Liste sequentiell durchlesen muß).
. Bei hoher Auslastung entstehen lange Listen.
Beispiel: Angabe wie oben
Index Anzahl Liste
1 0
2 2 Carmen, Veronika
3 0
4 1 Tina
5 0
6 1 Renate
|
