Which is faster in accessing elements from Java collections [closed]

Question

I am trying to understand which is faster in accessing elements from collections in Java like ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap etc.

From this question: Suitable java collection for fast get and fast removal, I got to know that ArrayList takes O(1) and TreeMap as O(log n)

where as this: Map/ArrayList: which one is faster to search for an element shows that ArryList is O(n), HashMap as O(1) and TreeMap as O(log n)

where as this: Why is it faster to process a sorted array than an unsorted array? says that sorted array is faster than unsorted array. As the elements in TreeMap are sorted then can I assume all sorted collections are faster than un-sorted collections?

Please help me in understanding which is faster to use in accessing elements from java collections of list, set, map etc implementations.

Answer 1

Every collection type is suitable for a particular scenario. There is no fastest or best collection.

• If you need fast access to elements using index, ArrayList is your answer.
• If you need fast access to elements using a key, use HashMap.
• If you need fast add and removal of elements, use LinkedList (but it has a very poor index access performance).

and so on.

Answer 2

It depends whether you want to access an element as index based(in case of list) or see if an Object exists in the Collection

If you want to access an element index based,then arraylist is faster as it implements RandomAccess Marker interface and is internally backed by an array.

Sets are internally backed by Map ,so performance of Map and Set is same(Set use a dummy Object as value in key-value pair).I would suggest you to use a HashSet.

The problem that many programmers dont notice is that performance of Hashset or HashMap is best O(1) when the hashing function of Key Object is good,ie. it produces different values for different Objects (though this is not a strict requirement).

NOTE :- If you are Hashing funciton is not good,it degrades to a LinkedList internally and its performance degrades to O(n)

My personal preference is to Use EnumMap or EnumSet.It simply uses the Enum values for its functioning and programmers dont have to worry about the Enum's hashcode/equals function.For rest other cases,use HashSet or HashMap(if you dont have to make it ordered)