Структура данных: вставить, удалить, содержать, получить случайный элемент, все в O (1)

Question

Мне дали эту проблему в интервью. Как бы вы ответили?

Разработка структуры данных, которая предлагает следующие операции за время O (1):

• вставить
• удалить
• 1010 * содержит *
• получить случайный элемент

Answer 1

Мы можем использовать хеширование для поддержки операций за Θ (1) времени.

вставка (х) 1) Проверьте, присутствует ли x, выполнив поиск по хеш-карте. 2) Если его нет, вставьте его в конец массива. 3) Добавьте также в хеш-таблицу, x добавляется как ключ, а последний индекс массива - как индекс.

удалить (х) 1) Проверьте, присутствует ли x, выполнив поиск по хеш-карте. 2) Если имеется, найдите его индекс и удалите его из хэш-карты. 3) Поменяйте местами последний элемент с этим элементом в массиве и удалите последний элемент. Обмен сделан, потому что последний элемент может быть удален за O (1) раз. 4) Обновить индекс последнего элемента в хэш-карте.

getRandom () 1) Генерация случайного числа от 0 до последнего индекса. 2) Вернуть элемент массива по случайно сгенерированному индексу.

поиск (х) Выполните поиск х в хэш-карте.

Answer 2

Я думаю, что мы можем использовать двойной список ссылок с хэш-таблицей.ключ будет элементом, а его соответствующее значение будет узлом в двойном списке ссылок.

1. insert (H, E): вставьте узел в двойном списке ссылок и сделайте запись как H [E] = узел;O (1)
2. delete (H, E): получить адрес узла по H (E), перейти к предыдущему этого узла и удалить и присвоить H (E) значение NULL, поэтому O (1)
3. содержит (H, E) и getRandom (H) явно O (1)

Answer 3

В C # 3.0 + .NET Framework 4 общий Dictionary<TKey,TValue> даже лучше, чем Hashtable, потому что вы можете использовать ElementAt() метод расширения *1003* для индексации в базовый динамический массив, где элементы KeyValuePair<TKey,TValue>сохранено:

using System.Linq;

Random _generator = new Random((int)DateTime.Now.Ticks);

Dictionary<string,object> _elements = new Dictionary<string,object>();

....

Public object GetRandom()
{
     return _elements.ElementAt(_generator.Next(_elements.Count)).Value;
}

Однако, насколько я знаю, Hashtable (или его потомство по словарю) не является реальным решением этой проблемы, потому что Put () может быть только амортизирован O (1), не верноO (1), потому что это O (N) на границе динамического изменения размера.

Есть ли реальное решение этой проблемы?Все, о чем я могу подумать, это если вы укажете начальную емкость Dictionary / Hashtable на порядок выше ожидаемой, то вы получите O (1) операций, потому что вам никогда не нужно изменять размер.