Мне нужна структура данных, которая поддерживает FAST-вставку и удаление пар (ключ, значение), а также "получить случайный ключ", что делает то же самое, что и random.choice(dict.keys()) для словаря, Я искал в Интернете, и большинство людей, похоже, удовлетворены методом random.choice(dict.keys()), несмотря на то, что это линейное время.
Я знаю, что выполнение этого быстрее возможно:
- Я мог бы использовать хэш-таблицу изменения размера. Если я утверждаю, что отношение ключей к слотам составляет от 1 до 2, тогда я могу просто выбрать случайные индексы, пока не нахожусь в непустой слот. Я смотрю только на 1 - 2 клавиши, ожидая.
- Я могу получить эти операции в гарантированном наихудшем случае O (log n), используя дерево AVL, дополняя его рангом.
Есть ли простой способ получить это на Python? Кажется, должно быть!