Map/ArrayList: which one is faster to search for an element
java
Solution
1) Yes. Searching an `ArrayList` is O(n) on average. The performance of key lookups in a Map depends on the specific implementation. You could write an implementation of `Map` that is O(n) or worse if you really wanted to, but all the implementations in the standard library are faster than O(n).
2) Yes. `HashMap` is O(1) on average for simple key lookups. `TreeMap` is O(log(n)).
`Class HashMap<K,V>`
This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.
`Class TreeMap<K,V>`
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.
3) The space requirements will be O(n) in both cases. I'd guess the `TreeMap` requires slightly more space, but only by a constant factor.
Problem
I have a gigantic data set which I've to store into a collection and need to find whethere any duplicates in there or not. The data size could be more than 1 million. I know I can store more element in `ArrayList` comapre to a `Map`. My questions are: - is searching key in a `Map` faster than searching in sorted `ArrayList`? - is searching Key in `HashMap` is faster than `TreeMap`? - Only in terms of space required to store `n` elements, which would be more efficient between a `TreeMap` and a `HashMap` implementation?