Python получить случайный ключ в словаре в O (1)

Мне нужна структура данных, которая поддерживает вставку и удаление FAST пар (ключ, значение), а также «получить случайный ключ», который делает то же самое, что и random.choice (dict.keys ()) для словаря. Я искал в Интернете, и большинство людей, похоже, удовлетворены подходом random.choice (dict.keys ()), несмотря на то, что это линейное время.

Я знаю, что реализация этого быстрееpossible:

I could use a resizing hash table. If I maintain that the ratio of keys to slots is between 1 and 2, then I can just choose random indices until I hit a non-empty slot. I only look at 1 to 2 keys, in expectation. I can get these operations in guaranteed worst case O(log n) using an AVL tree, augmenting with rank.

Есть ли простой способ получить это в Python? Кажется, что должно быть!

Ответы на вопрос(4)

Ваш ответ на вопрос