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

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

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

• Я мог бы использовать изменение размера хэш-таблицу. Если я утверждать, что отношение ключей слотов между 1 и 2, то можно просто выбрать случайные индексы, пока не ударил непустой слот. Я только смотрю на 1 до 2 ключей, в ожидании.
• Я могу получить эти операции в гарантированном худшем случае O (журнал п), используя дерево AVL, дополняя с рангом.

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