HashSet vs ArrayList Speed? Insert vs Lookup ( Java )

Question

Looking at this question it made me curious as to which to use, Hashset vs ArrayList. The Hashset seems to have a better lookup and ArrayList has a better insert (for many many objects). So I my question is, since I can't insert using an ArrayList, then search through it using a HashSet, I'm going to have to pick one or the other. Would inserting with an ArrayList, converting to a HashSet to do the lookups, be SLOWER overall than to just insert into a HashSet then lookup? Or just stick with the ArrayList, although the lookup is worse, the inserting makes up for it?

Answer 1

It very much depends on the size of the collection and the way you use it. I.e. you can reuse the same HashSet for copying and this would save you time. Or you can keep them up-to-date.

Creating a HashSet copy for each element lookup will always be slower.

You can also utilize LinkedHashSet which has quick insertion and a HashSet's look up speed at cost of a little worse memory consumption and O(N) index(int) operation.

Answer 2

You must decide for your specific application which tradeoff pays off better. Do you first insert everything, then spend the rest of the time looking up, maybe occasionally adding a few more? Use HashSet. Do you have a lot of duplicates, which you must suppress? Another strong point for HashSet. Do you insert a lot all the time and only do an occasional lookup? Then use ArrayList. And so on, there are many more combinations and in some cases you'll have to benchmark it to see.

Answer 3

It's totally depends on your use case. If you implement the hashCode method correctly, the insert operation of HashSet is also an O(1) operation. If you don't need randomly access the elements(using index), and you don't want duplicates, HashSet would be a better choice.