Potrzebuję struktury danych, która obsługuje wstawianie i usuwanie FAST par (klucz, wartość), jak również „get random key”, co robi to samo co random.choice (dict.keys ()) dla słownika. Szukałem w Internecie, a większość ludzi wydaje się być zadowolona z podejścia random.choice (dict.keys ()), mimo że jest to czas liniowy.

Jestem świadomy, że szybsze wdrożenie jestmożliwy:

Mogłabym użyć tabeli mieszania z możliwością zmiany rozmiaru. Jeśli utrzymuję, że stosunek kluczy do slotów wynosi od 1 do 2, to mogę po prostu wybrać losowe indeksy, dopóki nie trafię w niepuste miejsce. Patrzę tylko na 1 do 2 kluczy, w oczekiwaniu.Mogę uzyskać te operacje w gwarantowanym najgorszym przypadku O (log n) za pomocą drzewa AVL, zwiększając je o rangę.

Czy jest jednak łatwy sposób na uzyskanie tego w Pythonie? Wygląda na to, że powinno być!