Случайное получение элементов в HashMap или HashSet без зацикливания

Question

У меня есть примерно 420 000 элементов, которые мне нужно легко хранить в каком-либо наборе или списке.Ограничения, однако, заключаются в том, что мне нужно иметь возможность выбирать случайный элемент и что он должен быть быстрым.

Изначально я использовал ArrayList и LinkedList, однако с таким количеством элементов это было очень медленно.Когда я его профилировал, я увидел, что метод equals() в объекте, который я хранил, вызывался примерно 21 миллион раз за очень короткий период времени.

Далее я попробовал HashSet.То, что я получаю в производительности, я теряю в функциональности: я не могу выбрать случайный элемент.HashSet поддерживается HashMap, который поддерживается массивом HashMap.Entry объектов.Однако, когда я попытался раскрыть их, мне помешала сумасшедшая приватность и приватность пакета всей Java Collections Framework (даже копирование и вставка класса не работали, JCF очень «использует то, что у нас есть, или сверните свои собственные»).«).

Каков наилучший способ случайного выбора элемента, хранящегося в HashSet или HashMap?Из-за размера коллекции я бы предпочел не использовать циклы.

ВАЖНОЕ РЕДАКТИРОВАНИЕ: Я забыл действительно важную деталь: как именно я использую коллекцию.Я заполняю всю коллекцию в начале стола.Во время программы я выбираю и удаляю случайный элемент, затем выбираю и удаляю еще несколько известных элементов, затем повторяю.Постоянный поиск и изменение - вот что вызывает медлительность

Answer 1

Нет причины, по которой ArrayList или LinkedList необходимо было бы позвонить equals() ... хотя вы не хотите здесь LinkedList, так как вы хотите быстрый произвольный доступ с помощью индекс.

Значение ArrayList должно быть идеальным - создать его с соответствующей емкостью, добавить в него все элементы, а затем вы можете просто несколько раз выбрать случайное число в соответствующем диапазоне и вызвать get(index), чтобы получить соответствующее значение .

HashMap и HashSet просто не подходят для этого.

Answer 2

Если вы не позвоните contains() (что будет вызывать equals() много раз), вы можете использовать ArrayList.get(randomNumber), и это будет O (1)

Вы не можете сделать это сHashMap - хранит объекты внутри себя в массиве, где индекс = хэш-код для объекта.Даже если бы у вас была эта таблица, вам нужно было бы угадать, какие корзины содержат объекты.Так что HashMap не является опцией для произвольного доступа.

Answer 3

Если ALL , вам нужно получить большую коллекцию значений и выбрать случайную, тогда ArrayList (буквально) идеально подходит для ваших нужд. Вы не станете значительно быстрее (если не перейдете непосредственно к примитивному массиву, где вы потеряете преимущества абстракции.)

Если это слишком медленно для вас, это потому, что вы используете и другие операции. Если вы обновите свой вопрос ВСЕМИ операциями, которые должна обслуживать коллекция, вы получите лучший ответ.

Answer 4

Если предположить, что вызовы equals() вызваны тем, что вы сортируете дубликаты с помощью contains(), вы можете оставить как HashSet (для быстрого поиска, если он уже есть), так и ArrayList (длябыстрый произвольный доступ).Или, если операции не чередуются, сначала создайте HashSet, затем извлеките его данные с помощью toArray() или преобразуйте его в ArrayList с помощью конструктора последнего.

Если ваши проблемыиз-за remove() вызова ArrayList, не используйте его и вместо этого:

1. , если вы удалите не последний элемент, просто замените (на set()) удаленный элемент на последний;
2. уменьшить размер списка на 1.

Это, конечно, испортит порядок элементов, но, видимо, вам это не нужно, судя по описанию.Или вы пропустили еще одну важную деталь?