Using ArrayList or HashMap for better speed

Question

I need a 'List' or 'Map',... of object A. This list will be added from another ArrayList. Object A is considered to be equal to another when id parameter of A equals.

My problem is I only want add an object that does not exist in my List. I wonder between the two alternatives for implementation. Using ArrayList or HashMap

1. ArrayList:

for (A a: source) {if (! (a in ArrayList)) addToArrayList();}

2. HashMap <id, A>

for (A a: source) {hasmap.put (a.id, a)}

Which will give better speed to add a large number (over 1000 objects, or bigger number of object) Is there a better pattern for my problem???

Answer 1

The ArrayList has O(n) performance for every search, so for n searches its performance is O(n^2).

The HashMap has O(1) performance for every search (on average), so for n searches its performance will be O(n).

While the HashMap will be slower at first and take more memory, it will be faster for large values of n.

The reason the ArrayList has O(n) performance is that every item must be checked for every insertion to make sure it is not already in the list. We will do n insertions, so it is O(n^2) for the whole operation.

The reason the HashMap has O(1) performance is that the hashing algorithm takes the same time for every key and then the lookup to find the key also takes constant time. There can be occasions when the hash table exceeds its load factor and needs to be reallocated, and that it why it is constant on avarage.

So finally, to answer your question, my advice is to use the HashMap.

Answer 2

First, I'm going to go out on a limb and state that these are two completely different data structures. A List deals with a linear representation of elements, and a Map deals with key-pair values.

My gut feeling is that you're attempting to choose between a List and a Set.

If you wish to only enter unique elements, or to put it more succinctly, if you only care about unique values, then a Set of some kind is your best bet - probably HashSet if you don't care about ordering. It provides O(1) time for the basic operations, such as add, remove, contains, and size.

^{(Interestingly enough, HashSet is backed by a HashMap, but provides an interface similar to ArrayList.)}