22

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???

Improve this question
6
  • Why dont you test it? Commented Sep 18, 2013 at 2:40
  • 2
    I want to know if have any better pattern for my problem Commented Sep 18, 2013 at 2:43
  • 1
    If you only want to insert items that aren't already in the collection, why not use a Set? Commented Sep 18, 2013 at 2:45
  • 2
    Often, certain programmers spend too much time addressing performance problems that don't yet exist. If your application spends only a fraction of its time accessing your data in this way then, frankly, the implementation of HashMap or ArrayList may not even matter one iota. The only way anybody can say that this detail is important for performance is by profiling your application. Commented Sep 18, 2013 at 3:06
  • 3
    @scottb While I 100% agree with your first sentence, picking the the right data structure (and related, right collection interface) does not fall into category of premature optimizations. Trying to first find and then fix a reason for a big application being slow is often a big task. And that O(n*n) is a bitch when n grows in production use. Commented Sep 18, 2013 at 3:41

2 Answers 2

Reset to default
68

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

And as @Chris Hayes mentioned, Set(HashSet) is a better solution???. I think Set has the same performance with ArrayList??
Set is an interface. HashSet is an implementation that will overall perform better here. TreeSet will perform between the two, but guarantee order on top of uniqueness.
@JohnGaughan nitpick clarification: TreeSet guarantees natural order. LinkedHashSet guarantees insertion order.
I believe the ArrayList considerations are quite inaccurate, from the documentation: "The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation." docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html
@Stefano ... and for each insert the OP wants to ensure it's unique, requiring the whole ArrayList to be traversed.
|
25

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.)

Improve this answer

2 Comments

@Makoto Isn't HashMap is backed by a HashSet?
Bonus: Java has LinkedHashSet which iterates in insertion order like lists.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.