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

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?

If the hashcodes for the set elements are liable to change, then you should NOT be using a HashSet. (If you do, the data structure will break, and elements in the set are liable to go missing.)

But I doubt you should be using ArrayList either, because if hashcode() is sensitive to changes to the object, then equals(Object) will most likely be too. And that means that contains(...) and similar methods won't be able to find objects.

I think you should be using a Map type, and using a "student identifier" as the key.

(You could also override hashcode and equals so that equality means that two objects have the same id. But that makes equals(Object) useless for other purposes.)

Answer 3

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.

Answer 4

If you have duplicate data in your code then you should use ArrayList otherwise you can use hashset as shown below So, if your code don't need the duplicate values then use Set instead of list because the set will give much better performance (O(n) vs O(n^2) for the list), and that's normal because avoiding duplicates is the very purpose of a set.

ArrayList

public static void main(String[] args) {

ArrayList arr =new ArrayList();
arr.add("Hello");
arr.add("is");
arr.add("Hello");
System.out.println(arr);  //As we are using Arraylist therefore 
                          //the duplicate elements are allowed therefore
                          //"Hello" is not removed in the output

}

HashSet

public static void main(String[] args) {

HashSet arr =new HashSet();
arr.add("Hello");
arr.add("is");
arr.add("Hello");
System.out.println(arr);  //As we are using Hashset therefore 
                          //the duplicate elements removed therefore
                          //"Hello" is removed in the output

}

Answer 5

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?

Definitely if you are gonna to change values used by hashCode or equals it is not possible to use HashMap or HashSet.

You are saying that you want to remove and add a lot. The question is if you want to do it sequntially or randomly(based on index). If you add, remove sequentially then definitely the best choice is LinkedList. If you access objects randomly then ArrayList is much more efficient.

Answer 6

You should not use a Set when the results of objects' equals methods will change. If you're identifying students by a stable unique ID number, and equals just checks that ID, then using a Set is fine.

Note that HashSet will use hashCode for indexing and comparison, and hashCode should incorporate exactly those fields that are used to determine equals.