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.


Log in to reply