Java - наиболее эффективный метод сопоставления

Question

Предполагая, что нужно хранить список элементов, но он может храниться в любом типе переменной; какой будет наиболее эффективный тип, если он используется в основном для сопоставления?

Чтобы уточнить, список элементов должен быть содержаться, но форма, в которой она содержится, не имеет значения (перечисление, список, хэш-карта, Arraylist и т. Д.) Этот список элементов будет сопоставляться с регулярно, но не редактируется. Какой был бы наиболее эффективный метод хранения, предполагая, что вам нужно только один раз написать список, но может быть сопоставлен несколько раз в секунду? не

Примечание: Нет многопоточной

Answer 1

A HashSet (and HashMap) O(1) сложность. Также обратите внимание, что вы должны создать достаточно большой HashSet с небольшим loadfactor, что означает, что после проверки hashcode элементы в результирующем ведре также будут найдены очень быстро (в ведре есть последовательный поиск). Оптимально каждое ведро должно содержать не более 1 элемента.

Подробнее о концепции емкости и коэффициента нагрузки в Javadoc можно узнать из HashMap.

Еще быстрее решение было бы, если число элементов составляет не более 64 не состоит в создании Enum для них и использовать EnumSet или EnumMap, который хранит элементы в long и использует простой и очень быстрый битовые операции, чтобы проверить, если элемент находится в наборе или карте (операция содержит только простой битмасс-тест).

Если вы решите пойти с HashSet и не с Enum подходом, знают, что HashSet использует hashCode() и equals() методы элементов. Вы можете подумать о том, чтобы переопределить их, чтобы обеспечить более быструю реализацию, зная внутренние элементы, которые вы хотите сохранить.
Тривиальная оптимизация переопределения hashCode() может быть, например, кэшем один раз вычисленный хеш-код в самом элементе, если он не изменяется (и последующие вызовы hashCode() должны просто вернуть кешированное значение).

Answer 2

Из вашего описания, кажется, что порядок не имеет значения. Если это так, используйте Set. Стандартная реализация Java - это HashSet.

Answer 3

Наиболее эффективным для повторного поиска будет почти наверняка будет EnumSet

... Наборы Enum представлены внутренне как битовые векторы. Это представление чрезвычайно компактно и эффективно. Пространство и время работы этого класса должны быть достаточно хорошими, чтобы позволить использовать его как высококачественную, типичную альтернативу традиционным «бит-флагам» на основе int. Даже массовые операции (такие как containsAll и retainAll) должны выполняться очень быстро, если их аргумент также является перечислением.

...

Реализация Примечания: Все основные операции выполняются в постоянная время. Они, скорее всего, (хотя и не гарантированы) будут намного быстрее, чем их аналоги HashSet. Даже массовые операции выполняются в постоянное время, если их аргумент также является набором перечислений.