Eu preciso de uma estrutura de dados que suporte a inserção FAST e exclusão de pares (chave, valor), bem como "obter chave aleatória", que faz o mesmo que random.choice (dict.keys ()) para um dicionário. Eu pesquisei na internet, e a maioria das pessoas parece estar satisfeita com a abordagem random.choice (dict.keys ()), apesar de ser tempo linear.

Estou ciente de que implementar isso mais rápido épossível:

Eu poderia usar uma tabela de redimensionamento de hash. Se eu mantiver que a proporção de chaves para slots é entre 1 e 2, então eu posso apenas escolher índices aleatórios até atingir um slot não vazio. Eu só olho para 1 a 2 chaves, na expectativa.Eu posso obter essas operações no pior caso garantido O (log n) usando uma árvore AVL, aumentando com a classificação.

Existe alguma maneira fácil de obter isso em Python? Parece que deveria haver!