Get an Object from a collection without looping in java

Question

I need to repeatedly (hundred of thousands of times) retrieve an element (different each time) from a Collection which contains dozens of thousand of Objects.

What is the quickest way to do this retrieval operation? At the moment my Collection is a List and I iterate on it until I have found the element, but is there a quicker way? Using a Map maybe? I was thinking to do:

• Putting the Objects in a Map, with the key being the id field of the Object, and the Object itself being the value.
• Then doing get(id) on the Map should be much faster than looping through a List.
• If that is a correct way to do it, should I use a HashMap or TreeMap? - my objects have no particular ordering.

Any advice on the matter would be appreciated!

Last note: if an external library provides a tool to answer this I'd take it gladly!

Answer 1

As per the documentation of the Tree Map (emphasis my own):

The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

In your case, you state that the items have no particular order and it does not seem that you are after any particular order, but rather just be able to retrieve data as fast as possible.

HashMaps provide constant read time but do not guarantee order, so I think that you should go with HashMaps:

This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time. This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

As a side note, the memory footprint of this can get quite high quite fast, so it might also be a good idea to look into a database approach and maybe use a cache like mechanism to handle more frequently used information.