Zeitkomplexität einer Hashtable

[metzgore]

Hallo,

wir nehmen zur Zeit Algorithmen und deren Komplexität durch. Das Thema Hashtables und deren Komplexität verwirrt mich etwas.

Beispiel: Man hat eine Hashtable, die Kollisionen durch Verkettung auflöst. Allgemein wird in der Literatur gesagt, dass die Hashtable dann für das Einfügen eines neuen Datensatzes im worst-case eine Zeit von O(1) benötigt, also konstante Zeit. Das Suchen und Löschen benötigt im worst-case O(n). Das Suchen und Löschen ist mir klar, da im worst-case alles auf eine Position und somit in eine Liste gehasht wird.
Wieso ist aber der worst-case fürs Einfügen O(1)?

Ich habe da zwei Theorien:
Erstens könnte es sein, dann man doppelt-verketteten Listen arbeitet, die ja Einfügungen in O(1) durchführen können.
Es könnte aber auch sein, dass man eine einfach-verkettete Liste hat und den neuen Datensatz immer am Anfang einfügt.

Die Literatur, die ich gelesen habe, spricht immer nur von verketteten Listen, aber nie genau davon, wie das eigentlich genau funktioniert und was da gemacht wird in der Implementierung.

Ist eine meiner beiden Theorien richtig? Oder gibt es da noch andere Wege?

 

[Airbag]

Bei Hashtabellen verwendet man of B+ Bäume als Datenstruktur.
http://de.wikipedia.org/wiki/B+-Baum#Einf.C3.BCgen

Um Nachfolger und Vorgänger eines Blattknoten effizient (d.h. in konstanter Zeit) zu finden, müssen die Blätter in einer doppelt verketteten Liste miteinander verbunden sein. Dieses Feature wird häufig in die Definition des B+-Baumes mit aufgenommen.

Also passt das mit doppelt verketteten Liste durchaus, muss es aber nicht, da auch andere Datenstrukturen verwendet werden können.

 

[Skuzzle]

Ja, deine Theorien stimmen soweit.

Das finden des Platzes in der Hashtabelle passiert in O(1) und das Einfügen in die dortige Liste geht (egal ob doppelt oder einfach verkettet) ebenfalls in O(1). Man kann ja in jedem Fall das neue Element einfach hinten dran hängen. Doppelt-verkettete Listen haben den Vorteil dass sich Elemente dort einfacher löschen lassen (da man ja eine Referenz auf Vor- und Nachfolger hat), sie benötigen dadurch aber auch mehr Platz im Speicher.

Es gibt bei Hashtabellen auch noch eine weitere Methode um mit Kollisionen umzugehen: Wenn der eigentliche Platz des einzufügenden Elementes schon belegt ist, wird mit Hilfe einer weiteren Funktion (Sondierungsfunktion) ein Ausweichplatz berechnet, ist dieser ebenfalls belegt, wird ein weiterer Platz berechnet. Die Variante hat den Vorteil dass sie etwas Platz (man spart sich die Listen in jedem Array-Eintrag) und Overhead beim Einfügen und Entfernen der Elemente in die Liste spart.

Bei den verschiedenen Strategien geht es wie fast überall in der Informatik um Speicher vs. Geschwindigkeit. Die Java Implementierung von HashMap nutzt z.B. Verkettung der Elemente

 

[metzgore]

Bei einfach-verketteten Listen kann das doch aber theoretisch nicht in O(1) passieren, da man ja erstmal die komplette Liste durchgehen muss, um das Ende zu finden und um dann den neuen Datensatz dran zu hängen. Und das wäre wiederum O(n), wenn wieder alles auf eine Position gehasht wird. Oder verstehe ich da was falsch?

Das mit der Sondierung weiß ich schon, trotzdem danke.

 

[Skuzzle]

Bei einfach verketteten Listen kann die Liste ja auch eine Referenz auf das erste und das Letzte Element mitführen. Dann kann man ganz einfach ein neues Element hinten dran hängen und dieses ebenfalls als neues letztes Element der Liste speichern -> O(1) (oder analog als erstes Element)

 

[ice-breaker]

Bei Hashtabellen verwendet man of B+ Bäume als Datenstruktur.
http://de.wikipedia.org/wiki/B+-Baum#Einf.C3.BCgen

nein!
Eine Hashtabelle ist eine Hashtabelle!
Jede Form eines B-Baums ist ein Baum, aber keine Hashtabelle.
Man kann mit beiden z.B. assoziative Datenstrukturen implementieren, trotzdem bleibt ein Baum ein Baum und eine Hashtabelle eine Hashtabelle.

Bei einfach-verketteten Listen kann das doch aber theoretisch nicht in O(1) passieren, da man ja erstmal die komplette Liste durchgehen muss, um das Ende zu finden und um dann den neuen Datensatz dran zu hängen.

das ist von der Implementierung der verketteten Liste abhängig. Man geht i.R. aber nicht von der dir vermuteten naiven Implementierung aus, sondern schon einer verketteten Liste die sowohl einen Zeiger auf das first- als auch last-Element hat. Die Kette muss nicht doppelt verkettet sein um beide Zeiger zu haben

Edit: skuzzle war schneller.

 

[metzgore]

Ok, die Sache mit den zwei Zeigern ergibt natürlich Sinn. Da werd ich mich mal an eine Beispiel-Implementierung machen. Danke Leute!

 

[ice-breaker]

Anzumerken wäre noch, dass beim Speichern eines Wertes in der Hashtabelle eventuell noch auf mögliche Duplikate geprüft werden müsste, also eine Prüfung ob der Wert schon vorhanden ist. Dies ist zwar in der reinen Beschreibung der Hashtabelle nie beschrieben, aber bisher jede Implementierung, die ich gesehen habe, hat diese Prüfung gemacht.
Dann wäre das Speichern eines Wertes eigentlich eine O(n)-Operation mit der Länge n der Überlaufliste des Hashtabelle-Platzes in den gespeichert werden soll.

 

[metzgore]

Dessen bin ich mir bewusst. Aber für mich reicht erstmal eine Version, die Duplikate zulässt.