Warum nutzt man für die Buckets einer Hashtable nicht Trees?
-
Also ein Array von Trees (z.B. std::set). Was würde dagegen sprechen?
Dafür würde sprechen, das man damit den Worst-Case von O(n) umgeht.
Die Implementierungen von denen ich immer gehört habe nutzen ein Array von Listen.
-
Der Overhead den der Tree erzeugt ist es nicht wert. In den meisten Fällen wirst du nämlich nur ein Objekt haben pro Hash-Eintrag.
MfG SideWinder
-
Wenns zu voll wird in der Tabelle, beziehungsweise wenn es schwer wird die Größe im vorhinein abzuschätzen, insbesondere bei Indizies auf Festplatten, greift man auch auf dynamisches Hashing zurück.
http://www.informatik.uni-jena.de/dbis/lehre/ws2010/dbsem/Ausarbeitungen/a_DynamischesHashing.pdf
-
Gegen Bäumchen als Buckets spricht hauptsächlich der Implementierungs-Overhead.
http://en.wikipedia.org/wiki/Hash_table#Separate_chaining_with_other_structures
Mein Favorite ist aber immer noch closed-hashing. Also nicht ein Array aus Listen sondern einfach nur ein Array. Kannst du auch im Wikipedia-Artikel nachlesen.
@SideWinder
Im nicht degenerierten Fall besteht fast jeder Bucket-Baum aus genau einem Element. In dem Fall beschränkt sich der Overhead auf einen zusätzlichen (unbenutzten) Zeiger ("Left" & "Right" vs. nur "Next"). Den Key-Vergleich spart man sich in der Listen-Variante ja nicht. Und ob das erste Element das man vergleicht die Root-Node eines binären Baums ist, oder das erste Element einer Liste, sollte egal sein, so lange danach sofort abgebrochen werden kann weil nix mehr da ist.
-
bucket schrieb:
Also ein Array von Trees (z.B. std::set). Was würde dagegen sprechen?
Dafür würde sprechen, das man damit den Worst-Case von O(n) umgeht.
Die Implementierungen von denen ich immer gehört habe nutzen ein Array von Listen.
1. was wuerde gegen ein array an sich sprechen, hast ein 1:1 mapping, worst case O(1)
2. was wuerde gegen ein array von arrays von arrays sprechen?
-
@rapso
1 Speicherverbrauch
2 Speicherverbrauch
-
hustbaer schrieb:
@rapso
1 Speicherverbrauch
2 Speicherverbrauch
faehrst du oft in die grundschule um dann in die klasse zu rufen?
gibt trotzdem keinen lolli fuer dich
-
Was wäre mit einer Hashtable mit höherem maximalen Loadfaktor und Bucket-Bäumen? Kann doch schneller sein - je nachdem wie viel Rehashing man sich spart.
-
Auf eine spezielle Anwendung hin getrimmt kann fast jede Lösung Sinn machen. Je nach Anwendung halt.