Структура данных Java, которая имеет постоянное время доступа и допускает дублирование

Question

HashMap имеет постоянное время доступа, но не допускает дублирование. ArrayList позволяет дублировать, но не имеет постоянного времени доступа.

Есть ли в java структура данных, которая обеспечивает постоянное время доступа и дублирование?

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

Заранее спасибо.

Answer 1

ArrayList#get а также ArrayList#set на самом деле постоянное время, а также несколько других функций. Прочитайте документацию, второй параграф документации класса:

Операции size, isEmpty, get, set, iterator и listIterator выполняются в постоянное время

Ваш следующий вариант будет мультикартой. Это карта, на которой хранятся предметы в виде ключа / коллекции. Коллекция содержит значения, поэтому один ключ сопоставляется с несколькими значениями. Вы можете посмотреть в Apache Common's MultiMap чтобы увидеть, есть ли у них реализация, которая работает для вас. Или вы всегда можете создать свой собственный, просто определив коллекцию в качестве значения:

Map<String, List<String>> multimap;

Answer 2

Вы можете использовать сумку из коллекций GS, мультимножество из Google Guava или сумку из коллекций Apache Commons. Сумка в основном Map<Key, Integer> который ведет себя как коллекция.

Все три библиотеки также имеют Multimaps. Multimap в основном Map<Key, Collection<V>>где вызов, чтобы положить результаты в добавлении к Collection<V> вместо замены значения в этом ключе. Существуют различные типы Multimap (List, Set, Bag и т. Д.).

Примечание: я разработчик на GS Collections