A java datastructure which has constant access time and allows duplicates

Question

A HashMap has constant access time but does not allow duplicates. An ArrayList allows duplicates but does not have constant access time.

Is there a data structure in java which allows constant access time and allows duplicates?

I know I could make my own HashMap which allows duplicates, but I want to use an already existing data structure.

Thank you in advance.

Answer 1

You could use a Bag from Eclipse Collections, a Multiset from Google Guava, or a Bag from Apache Commons Collections. A Bag is basically a Map<Key, Integer> which behaves like a Collection.

All three libraries have Multimaps as well. A Multimap is basically a Map<Key, Collection<V>>, where a call to put results in adding to the Collection<V> instead of replacing the value at that key. There are different types of Multimap (List, Set, Bag, etc.).

Note: I am a committer for Eclipse Collections

Answer 2

ArrayList#get and ArrayList#set are actually constant time, as well as a few other functions. Read the documentation, second paragraph of the class documentation:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time

Your next option would be a multimap. This is a map that stores items in a key/collection manner. The collection holds the values, so a single key map to multiple values. You can look into Apache Common's MultiMap to see if they have an implementation that works for you. Or you could always create your own, simply by defining a collection as the value:

Map<String, List<String>> multimap;