HashSet vs. ArrayList

Question

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?

Answer 1

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

Answer 2

The javadoc for Set says

Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set. A special case of this prohibition is that it is not permissible for a set to contain itself as an element.

So if you are going to use a HashSet if you make hashCode() and equals() based with inmutable fields then you won't have this problem. For example using an unique studentID for each instance.