Java Collections – HashSet vs. ArrayList

arraylistcollectionshashsetjavaset

So I have a custom class Class that will have a set of another custom class Students. So it will look something like this:

public class Class {
    private Set<Student> students;

    // other methods
}

Now I will be adding and removing many students to the set students and i will also be changing many of the private fields of a student already in the set of students.

QUESTION: What data structure should I use to best implement this? Since I will be changing the property of the Student objects in set student (thereby changing the hashcodes) should I use an ArrayList instead?

Best Answer

When its comes to the behavior of ArrayList and HashSet they are completely different classes.

ArrayList

  • ArrayList Does not validate duplicates.
  • get() is O(1)

  • contains() is O(n) but you have fully control over the order of the entries.

                          get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(1)      O(1)

  • Not thread safe and to make it thread safe you have to use Collections.synchronizedList(...)

HashSet

  • HashSet ensures there are no duplicates.

  • Gives you an O(1) contains() method but doesn't preserve order.

                          add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is the table
  • Not thread safe and to make it thread safe you have to use Collections.synchronizedSet(...)
Related Question