Rehashing

[Thisor]

Hey, ich habe eine allgemeine Frage über das Hashing. Habe leider nichts im Suchfunktion gefunden:
Was genau ist Rehashing?
Man unterscheidet hier zwischen offenes und geschlossenes Hashing. Wenn es bei einem geschlossenen Hashing kolossiert, kann man ja wie zb durch linerae Sondierung es "rehashen"..?
In meinem Skript steht allerdings "Dynamische Anwendung: offenes Hashing. Zu lange Ketten : Re-Organisation."
Diese Aussage verwirrt mich, heißt das jetzt, dass wenn die Kette zu lang ist, man rehashing anwendet? Und hat Rehashing hat schlussendlich nichts mit Lineare Sondierung zu tun?

mfg

 

[Meniskusschaden]

Ich glaube, Rehashing bedeutet lediglich, dass die Hashtabelle neu aufgebaut wird. Es könnte beispielsweise nötig werden, eine Hashtabelle mit größerer Behälteranzahl zu bilden, wenn die ursprüngliche Tabelle so voll ist, so dass es zu viele Kollisionen gibt.

 

[Kababär]

Also ich verstehe das so:
Hast du eine Hashtabelle und schreibst dort brav Werte rein, wird diese Tabelle irgendwann voll und du musst (bei geschlossenem Hashing, denn du willst ja keine Kollisionen haben bzw Kollsionen auflösen) die Tabelle erweitern, um wieder mehr Werte in deine Tabelle aufnehmen zu können (was du eventuell nicht willst, weil freier Platz reserviert, nicht genutzt und somit verschenkt wird) oder du verwendet eine alternative Hashfunktion, mit der du die Werte in die Tabelle bringst (Rehashing).
Nachteil bei Variante 2 (Rehashing) ist, dass sich die Hashwerte der bereits gespeicherten Daten ändern und du eben nochmal alles berechnen musst.

 

[Thisor]

@Kababär aber laut Variante2 lege ich eine komplett neue Hashfunktion an..
Was hat dann z.B. Lineare Sondierung damit zu tun? Ich habe es immer so aufgefasst, dass wenn bei einem geschlossenen Hashfunktion ein Bucket überläuft, das es so zu einem Kollision führt. Um dieses Problem(Kollision) zu lösen, muss man es rehashen -> durch Sondierung. Aber wenn ich hier daneben lege, dann hat ja die Sondierung nicht´s mit rehashen zu tun..?

 

[Meniskusschaden]

Ich glaube, was @Kababär als Variante 2 beschreibt ist kein Rehashing sondern Doppel-Hashing, also die Kollisionsbehandlung mithilfe einer alternativen Hashfunktion.
Folgender Ausschnitt aus der Oracle-Dokumentation zur HashMap https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html ist vielleicht ganz aufschlussreich:

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

Bei offenem Hashing möchte man vielleicht auch rehashen, damit die Hash-Tabelle nicht zu einer Ansammlung von Listen mit entsprechendem Laufzeitverhalten degeneriert. Das nur als Ergänzung zu folgender Aussage:

Hast du eine Hashtabelle und schreibst dort brav Werte rein, wird diese Tabelle irgendwann voll und du musst (bei geschlossenem Hashing, denn du willst ja keine Kollisionen haben bzw Kollsionen auflösen) die Tabelle erweitern, ...

 

[Kababär]

Wenn du ein geschlossens Hashing (jedes Bucket darf nur einen Eintrag haben) hast und füllst deine Tabelle auf und hast Werte, die nun nicht mehr abgebildet werden, erstellst du eine neue Hashfunktion und beginnst von vorne (rehashen).
Lineare Sondierung bedeutet in erste Linie erstmal nur, dass du eine einzige Hashfunktion hast.
Bei beispielsweise quadrierter Sondierung kannst du evtl. mehr Werte auf die gleiche Tabelle abbilden.

Das große Problem sehe ich darin, eine Funktion zu finden, die alle Werte abbildet. In der Praxis ist es deswegen oft üblicher, einfach die Tabelle zu erweitern oder eine Menge von Hash-Funktionen zu definieren.

Edit: Nein ich meine kein Doppel-Hashing. Doppel-Hashing wäre:
Du hast zwei Hashfunktionen. Benutze eine solange wie du keine Kollision bekommst. Verwende die andere Funktion, wenn eine Kollision auftritt.
Was ich meine: Du hast eine Funktion (lineares Sondieren). Verwende nur diese Funktion. Kann dieser Wert nicht auf die Tabelle abgebildet werden, suche eine andere Funktion. Entferne alle Werte aus der Tabelle. Verwende die neue Funktion.
Können Werte nicht mehr abgebildet werden, suche neue Funktion die sich von den bisherigen unterscheidet. Entferne alle Werte und verwende wieder die neue Funktion, etc.
Löschen, einfügen, löschen, einfügen. Bis alle Werte abgebildet sind.

Bei offenem Hashing möchte man vielleicht auch rehashen, damit die Hash-Tabelle nicht zu einer Ansammlung von Listen mit entsprechendem Laufzeitverhalten degeneriert.

Sicher, wenn ein Bucket nur eine begrenzte Anzahl von Werten erhalten soll.

 

[Thisor]

Also ist mit "Re-Organisation" tatsächlich rehashen gemeint

 

[Kababär]

Ja ich würde das auch als Synonym ansehen.

 

[Meniskusschaden]

Was ich meine: Du hast eine Funktion (lineares Sondieren). Verwende nur diese Funktion. Kann dieser Wert nicht auf die Tabelle abgebildet werden, suche eine andere Funktion. Entferne alle Werte aus der Tabelle. Verwende die neue Funktion.

Ja, das würde ich dann auch als eine Form von Rehashing ansehen. Allerdings frage ich mich, ob sie eine große praktische Relevanz hat, denn das kann doch fast nur ein Trial- and Error-Verfahren sein, in der Hoffnung, dass die neue Funktion die konkreten Elemente besser streut, als die alte. Könnte vielleicht sinnvoll sein, wenn es bereits bei niedrigem Füllstand viele Kollisionen gab.

 

[Thallius]

Wofür benutzt man so etwas eigentlich? Ich kenne Hashing nur im Zusammenhang mit security and privacy.

 

[Meniskusschaden]

Man benutzt es für Datenstrukturen, wie beispielsweise die oben genannte HashMap. Die Position des Speicherplatzes wird mit der Hashfunktion direkt aus dem Schlüsselbegriff errechnet. Vorteile sind die guten Laufzeiten beim Einfügen, Ändern und Löschen, Nachteile die schlechten Laufzeiten beim Sortieren oder Iterieren über alle Elemente, sowie die nötige Kollisisonsbehandlung.