Warum verwendet man offenes Hashing?
Hi,
ich bin zwar in der Lage, beide Arten Hashing und verschiedene Kollisionsbehandlungen von Hand anzuwenden, aber um zu begründen, wann offenes Hashing besser ist als geschlossenes fehlt mir noch der Realbezug zu Beispielen mit riesen Mengen von Elementen, großen Tabellen usw.
Ich weiß, dass bei dynamischen Anwendungen immer offenes gewählt wird, da die Anzahl Elemente nicht von vornherein bei diesen klar ist. Ich weiß auch, dass der Belegungsgrad der Tabelle bei geschlossenem 60% nicht überschreiten sollte. Ich nehme an, wir wollen bei geschlossenem Hashing keine großen Mengen von Elementen haben, da wir dass bei dynamischen Anwendungen aber vorher nicht wissen, nehmen wir zur Vorsicht offenes (Annahme richtig?). Aber warum kann geschlossenes Hashing mit vielen Elementen nicht umgehen? Würde dann der Aufwand viel zu groß werden, wenn dementsprechend mehr Kollisionen auftreten? Fällt jemandem noch eine Begründung ein, so diese überhaupt zutrifft?
Ich weiß außerdem, dass wir bei geschlossenem Hashing bevorzugen, später keine oder wenige Elemente wieder löschen zu müssen. Warum ist der Aufwand bei offenem Hashing da geringer?
Danke für eure Hilfe schon mal im Vorraus
1 Antwort
(Ich nehme hier an, dass "Geschlossenes Hashing" schlicht nur "Nicht-offenes Hashing" meint, wenn ihr eine andere Definition habt, dann könnte die Antwort anders lauten.)
Geschlossenes Hashing ermöglicht es, schnell den passenden Platz für ein Element zu finden, da die Adresse feststeht.
Man muss aber Möglichkeiten finden, mit Kollisionen umzugehen. Das sürfte dadurch geschehen, dass am entsprechendem Platz eine Datenstruktur liegt, die die Elemente dort verwaltet.
So, das Problem ist nun, dass eine solche Datenstruktur selbst auf verschiedenste Weise ineffizient sein kann. Am effizientesten wäre es vielleicht, wenn man viele Elemente hat, eine Datenstruktur dort zu verwenden, die auch mit Hashes arbeitet.
Das lohnt sich aber nur bei vielen Einträgen in einem Platz, das sollte ja aber eher nicht vorkommen.
Also verwendet man lieber die bereits existierende Hash-Struktur nur mit neuem Hash. Das wäre dnan offenes Hashing.
Das offene Hashing hat aber das Problem, dass die Adressberechnung umständlicher werden kann, insbesondere, wenn die Datenstruktur sehr voll ist.
Welche Datenstruktur nun besser geeignet ist, hängt von mehreren Faktoren ab, nicht nur von der Zahl der Elemente. Und oftmals gibt es noch andere Möglichkeiten, mit Problemen umzugehen, beispielsweise Rehashing oder dergleichen.
Eine große Zahl an Elementen macht es aber natürlich wahrscheinlicher, dass einzelne Plätze komplett gefüllt werden und man das behandeln muss (ob da offenes Hashing besser ist, müsste man jeweils einzeln prüfen).
Ich weiß außerdem, dass wir bei geschlossenem Hashing bevorzugen, später keine oder wenige Elemente wieder löschen zu müssen. Warum ist der Aufwand bei offenem Hashing da geringer?
Wenn man es passend implementiert, sollten da keine großen Unterschiede bestehen.