Java collection insertion: Set vs. List

Question

I'm thinking about filling a collection with a large amount of unique objects. How is the cost of an insert in a Set (say HashSet) compared to an List (say ArrayList)?

My feeling is that duplicate elimination in sets might cause a slight overhead.

Answer 1

You have to compare concrete implementations (for example HashSet with ArrayList), because the abstract interfaces Set/List don't really tell you anything about performance.

Inserting into a HashSet is a pretty cheap operation, as long as the hashCode() of the object to be inserted is sane. It will still be slightly slower than ArrayList, because it's insertion is a simple insertion into an array (assuming you insert in the end and there's still free space; I don't factor in resizing the internal array, because the same cost applies to HashSet as well).