Necesito una estructura de datos que admita la inserción y eliminación FAST de pares (clave, valor), así como "obtener clave aleatoria", que hace lo mismo que random.choice (dict.keys ()) para un diccionario. He buscado en Internet, y la mayoría de las personas parecen estar satisfechas con el enfoque random.choice (dict.keys ()), a pesar de que es un tiempo lineal.

Soy consciente de que implementar esto más rápido esposible:

Podría usar una tabla hash de cambio de tamaño. Si mantengo que la proporción de claves a ranuras está entre 1 y 2, entonces puedo elegir índices aleatorios hasta que llegue a una casilla que no esté vacía. Sólo miro de 1 a 2 teclas, en espera.Puedo obtener estas operaciones en el peor de los casos garantizado O (log n) usando un árbol AVL, aumentando con rango.

Sin embargo, ¿hay alguna forma fácil de obtener esto en Python? Parece que debería haber!