I have 100 000 elements in my collection, it can be an Array/List/Set/Map.
Which is the best approach to search for the element in the collection?
The collection is unordered and unsorted.
Asked
Active
Viewed 852 times
-4
-
2That depends on what collection you are using. Different collections have different time complexity for search – TheLostMind Nov 03 '15 at 05:41
-
2Please refer **Java Collections – Performance (Time Complexity)** on this link http://infotechgems.blogspot.in/2011/11/java-collections-performance-time.html – Dev Nov 03 '15 at 06:09
2 Answers
0
List:
Array List in Java is backed by an underlying array. You can opt for Collections.binarySearch if the array is sorted.
Array:
If the array is sorted, you can use Binary Search. If it is not, you have to use sequential search.
Set and Map:
These are more or less the same. The input is mapped to a hash and a look up is made based on this hash. This is the same whether it is sorted or not.
Pavan Dittakavi
- 3,013
- 5
- 27
- 47
-
2`ArrayList` is a `List` backed by an `Array`. It has constant (`O(1)`) access time to its elements (given the location of course) – TheLostMind Nov 03 '15 at 05:46
-
You probably missed the last line in the OP's question: "The collection is unordered and unsorted." – Erwin Bolwidt Nov 03 '15 at 06:07
0
Hash maps will be ideal in this case as "The collection is unordered and unsorted". Arrays can work more faster if its sorted while maps does not care whether the collections are sorted or not.
Please refer to the link below to know which data structure to use when.
http://www.devx.com/tips/Tip/14639
The performance of Array vs Hash map is given in the following link, Please refer that also.
Hashmap vs Array performance
Hash maps in Java has far less complexity compared to sorting an array and searching a key. The following post discuss about the complexity of hash maps on their look up time.
Is a Java hashmap really O(1)?
