Use HashSet over ArrayList to Convey Intention?

Question

Imagine that I need to create a Collection of elements, where order could or could not matter. Effectively all I plan on doing is using the iterator. I notice most of my colleagues using an ArrayList vs LinkedHashSet/HashSet. My question is, if I know that these elements should be unique, should I be using a Set or a List? Effectively it doesn't really make a difference, but doesn't Set more effectively convey that the elements are unique?

I find this to be an interesting question for large enterprise applications for a few reasons: 1) If you can't guarantee the quality of code overall, using a Set can be dangerous. Why? Because equals() & hashcode might be incorrectly overridden and thus using a Set could cause some really nasty issues. 2) Using a List is more resilient to future changes. If duplicates for whatever reason become possible, no need for concern.

Essentially it boils down to: If I know I should expect unique elements, should I favor Set over List in all cases?

Edit: I suppose I'm also asking: Should Set be used to ensure that no duplicates are added, or can it also be used for the sole purpose of illustrating that no duplicates exist for ease of understanding?

Answer 1

Set if preferable as it will enforce uniqueness and shows you where you are wrong.

You may have some issues when methods are incorrectly overriden but the right choice is not to pray and avoid calling them. Detect bugs and fix them!

Edit : And yes it's clearer when you see a Set, uniques values are needed and even better : unique values are enforced. Never guess/trust about usage of your code ;)

Answer 2

1) is totally bogus. Don't work around bugs, fix them. Therefore, use any Set implementation if order doesn't matter, or SortedSet if order does matter. If elements don't have to be unique(and you should determine that now, and it usually should not ever change), feel free to use a List.

Answer 3

If you need to think in unique elements, use Set. But if you don't trust your users to properly implement equals/hashCode, then I suggest you document that if there is something wrong with the iteration, check your equals/hashCode! But it really depends on the use-case of the data model.

Answer 4

Consider readability of code as well.

If you expect and want a unique set, then use a "SET" data structure, things will be much more clear in the long run. And thus, this will also promote better coding.

Answer 5

Using a Set implementation over a List implementation could degrade performance. When inserting an element in a Set, you need to check that it isn't a duplicate. If you are planning just to use the iterator, use the simplest implementation possible (ArrayList).

I don't think that is a good idea to use a Set just to convey information. If you are adding the items yourself and you can guarantee that no duplicates will be added, it is pointless to use a Set. Use a proper name to convey information about the collection. Also, it is a good idea to expose it through the Collection interface, especially if the callers of your class just need to iterate through the collection.

Answer 6

I don't think either choice should be considered to convey intention - your method ought to be declared to return simply a Collection with an appropriate generic parameter, both for flexibility and because as you've said, consumers of it should be able to just iterate over it without worrying what type it is. This gives the added advantage that if requirements change later, or it turns out that for whatever reason your initial choice was wrong, you need to change the code in just a single place (the initial constructor call).

The intention should rather be specified in the documentation of the method, which should detail whether the collection's iterator will return elements in any particular order, and whether duplicate elements will appear.

And I also agree with the above posts that say your reasoning around point 1) is off - if there are classes with incorrect implementations of equals and/or hashcode that you want to put into a set, you fix them and then use a Set!

Answer 7

Someone said that HashSet offers constant time performance on add, remove, contains and size.

The actual statement in the JavaDocs is "This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets."

This means you might get slow addition times when adding something to the set if its got a poorly implemented hashCode method.

The following code demonstrates what can happen dependent upon your hashCode implementation.

public void testHashSetAddition() {
    for(int mod=10; mod <= 100; mod=mod+10 ) {
        Set s = new HashSet();
        long start = new Date().getTime();
        for(int i=0; i<100000; i++) {
            s.add(new Foo(i % mod));
        }
        long end = new Date().getTime();
        System.out.println("Mod: " + mod + " - " + (end - start) + "ms");
    }
}

class Foo {
    private int hc;
    public Foo(int i) {
        this.hc = i;
    }
    public int hashCode() {
        return hc;
    }
}

The timing results were:

Mod: 10 - 22683ms
Mod: 20 - 14200ms
Mod: 30 - 10486ms
Mod: 40 - 8562ms
Mod: 50 - 7761ms
Mod: 60 - 6740ms
Mod: 70 - 5778ms
Mod: 80 - 5268ms
Mod: 90 - 4716ms
Mod: 100 - 3966ms

Then, doing exactly the same test for an ArrayList:

public void testAddingToArrayList() {
    for(int mod=100; mod >= 10; mod=mod-10 ) {
        List l = new ArrayList();
        long start = new Date().getTime();
        for(int i=0; i<100000; i++) {
            l.add(new Foo(i % mod));
        }
        long end = new Date().getTime();
        System.out.println("Mod: " + mod + " - " + (end - start) + "ms");
    }
}

Gives:

Mod: 100 - 50ms
Mod: 90 - 30ms
Mod: 80 - 40ms
Mod: 70 - 30ms
Mod: 60 - 30ms
Mod: 50 - 40ms
Mod: 40 - 20ms
Mod: 30 - 30ms
Mod: 20 - 30ms
Mod: 10 - 30ms