Ich benötige eine Datenstruktur, die das SCHNELLE Einfügen und Löschen von (Schlüssel-, Wert-) Paaren sowie das Abrufen eines zufälligen Schlüssels unterstützt. Dies entspricht random.choice (dict.keys ()) für ein Wörterbuch. Ich habe im Internet gesucht und die meisten Leute scheinen mit dem Ansatz random.choice (dict.keys ()) zufrieden zu sein, obwohl es sich um eine lineare Zeit handelt.

Mir ist bewusst, dass dies schneller umgesetzt wirdmöglich:

Ich könnte eine Hash-Tabelle zur Größenänderung verwenden. Wenn ich behaupte, dass das Verhältnis von Schlüsseln zu Slots zwischen 1 und 2 liegt, kann ich einfach Zufallsindizes auswählen, bis ich auf einen nicht leeren Slot treffe. Ich betrachte nur 1 bis 2 Tasten, in Erwartung.Ich kann diese Operationen im garantiert ungünstigsten Fall O (log n) unter Verwendung eines AVL-Baums erhalten, der um den Rang erweitert wird.

Gibt es eine einfache Möglichkeit, dies in Python zu bekommen? Es scheint, als sollte es geben!