Baum Hashtables?

Question

Die durchschnittliche Hashtable-Komplexität ist O (1) und die Worst-Case-Komplexität ist O (n). Die durchschnittliche Komplexität von Balanced Tree ist O (logn), die Worst-Case-Komplexität ist O (logn). Sind die meisten Datenbanken mit "Tree" anstelle von "Bucket" -Hashtables entworfen? Dies würde den durchschnittlichen Fall O (1) und den schlechtesten Fall O (logn) ergeben, richtig?

Answer 1

Hashtables ... Worst Case Komplexität ist O (n).

, dass für viele „getrennte Chaining“ aka „offene Hashing“ Implementierungen wahr ist, aber einige solche Implementierungen (zum Beispiel Java) verwenden ausgeglichene Bäume von kollidierenden Elemente, Worst-Case-Komplexität zu reduzieren O (log n). Für "closed hashing" -Implementierungen kann der Worst-Case-Fall sogar schlechter sein als O (n): Alles hängt davon ab, wie aufeinanderfolgende Buckets für die Sondierung nach Kollisionen ausgewählt werden und wann die Anzahl der Buckets erhöht wird.

Sind die meisten Datenbanken mit "tree" anstelle von "bucket" -Hashtables entworfen?

Was eine "Datenbank" ausmacht, ist vertretbar. Eine Umfrage unpraktisch machen. Und was Sie mit Ihrer Frage meinen, ist unklar - vielleicht wollen Sie die getrennte Verkettung mit Bäumen mit geschlossenem Hashing vergleichen? Ich kann die gängige Praxis unter "Datenbanken" nicht kommentieren, werde aber darauf hinweisen, dass das Beste in einer bestimmten Situation sehr stark von der Größe der gespeicherten Schlüssel und Werte und ihrer Kollisionsanfälligkeit abhängt. Zur Veranschaulichung des Kontrasts verwenden Python "dict" s (Wörterbücher, was der Python-Begriff für Hash-Tabellen ist) geschlossenes Hashing, während der C++ - Standard eine separate Verkettung effektiv vorschreibt, aber Programmierer beider Sprachen sich relativ selten über diese Implementierungsentscheidungen beschweren.