8

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.

Community
  • 1
  • 1
Chaitanya
  • 15,403
  • 35
  • 96
  • 137
  • 1
    The javadoc of each collection explains the complexity of every operation in the collection. Read it. – JB Nizet Nov 30 '13 at 13:02
  • 1
    You can assume whatever you want, but that doesn't make it true. Just because **a** sorted **array** was faster than an unsorted one in **this particular instance** doesn't mean **all** sorted **collections** are faster than all unsorted collections in **all usage patterns**. – meriton Nov 30 '13 at 13:03
  • 2
    If there were a single data structure that was always better than all others, the Java API would implement only that data structure. It offers several data structures because different data structures are optimized for different purposes. – meriton Nov 30 '13 at 13:05
  • If more than one collection meets your functional requirements, and the access performance matters, time your program with each appropriate collection. – Patricia Shanahan Nov 30 '13 at 13:09

2 Answers2

25

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.

Mohammad Dehghan
  • 17,853
  • 3
  • 55
  • 72
4

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)

Kumar Abhinav
  • 6,565
  • 2
  • 24
  • 35