CODEWITHSUNDEEP
javahashmapduplicatesconstant-time
user590849
user590849

Reputation: 11765

A java datastructure which has constant access time and allows duplicates

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.

Upvotes: 1

Views: 374

Answers (2)

Donald Raab
Donald Raab

Reputation: 6686

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

Upvotes: 1

Vince
Vince

Reputation: 15146

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;

Upvotes: 1

Related Questions