Итак, я столкнулся с проблемой создания набора с помощью функции getRandomElement ().Достаточно просто на первый взгляд.Но чем больше я думаю об этом, тем меньше думаю, что это можно сделать за O (1) временной сложности.Не было заданного требования к постоянному времени, но все основные функциональные возможности наборов находятся в постоянном времени, поэтому я чувствую, что подразумевается, что это также должно выполняться в постоянное время.
Цель набора -функция хеширования для уменьшения коллизий.Теперь возникает проблема: если вы просто генерируете случайные целые числа и пытаетесь выбрать индекс, используя это случайное целое число, вы, скорее всего, столкнетесь с «пустым» слотом в вашем наборе .... в этом случае вы должны сгенерировать новое случайное числои попробуй еще раз.По сути, чем лучше ваша хеш-функция, тем хуже ваш getRandomElement будет работать с этим подходом.
Итак, я подумал ... хорошо, почему бы не хранить индексы после каждой вставки?Затем сгенерируйте случайное число и выберите индекс из этой коллекции индексов.Я подумал, что это хорошая идея, но потом возникает проблема удаления элементов.Мы также должны были бы удалить соответствующий индекс из нашего списка индексов, а также удалить сам элемент из нашего Set.Как мы можем найти правильный индекс для удаления быстрее, чем линейное время ???
В любом случае, получение случайного элемента из набора ЧУВСТВУЕТ, как это может быть сделано за лучшее, чем линейное время.Кстати, я обрабатываю столкновения цепочкой.Я не хочу тратить время на попытки сделать то, что математически невозможно, но я также не математик и не хочу расставаться с тем, что на самом деле возможно.