HashSet vs ArrayList

Question

So, I have my own class class, which will have a set of other custom classes. Therefore, it will look something like this:

public class Class { private Set<Student> students; // other methods } 

Now I will add and remove many students for students, and I will also change many of the private fields of a student already studying.

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

Answer 1

What data structure should I use to best implement it? Since I will change the property of Student objects in set student (thereby changing the hash codes), should I use an ArrayList instead?

If the hash codes for given elements may change, you should NOT use a HashSet . (If you do this, the data structure will break and the elements in the set may disappear.)

But I doubt that you should use ArrayList too, because if hashcode() sensitive to changes in the object, most likely there will be equals(Object) . This means that contains(...) and similar methods cannot find objects.

I think you should use the Map type and use the "student ID" as the key.

(You can also override hashcode and equals so that equality means that two objects have the same identifier, but this makes equals(Object) useless for other purposes.)

Answer 2

When it comes to the behavior of ArrayList and HashSet , these are completely different classes.

Arraylist

• ArrayList Does not check for duplicates.
• get() O(1)

• contains() O(n) , but you have full control over the order of the records.

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

• Unsafe thread and to ensure thread safety you should use Collections.synchronizedList(...)

Hashset

• HashSet guarantees that there will be no duplicates.

• Gives you the O(1) contains() method, but does not preserve order.

    add contains next notes HashSet O(1) O(1) O(h/n) h is the table 

• Insecure thread and to ensure thread safety you should use Collections.synchronizedSet(...)

Answer 3

It depends. Since you are talking about a student, there must be something like id or rollno that is unique. If so, then override the hashcode method and implement the hash code based on their identifiers. Then there is no effect on the hash code by changing any of the other student properties.

The choice of Set or List is entirely up to your requirements. Read this link and it will explain the difference between Set and list
What is the difference between Set and List?

And if you use objects in Set, you can try to override both hashcode and the equals method so that control over uniqueness is in your hands.

Answer 4

For a hash collection such as a HashSet , the key must be immutable . Hashset uses hashing internally to determine the bucket for storing the object. Also, when retrieving an object, it will use a hash to search for an object's bucket. If you change the object after saving, it can change the hash code of the object, and Set cannot get the correct object. If you need to modify an object even after adding it to the collection, then using a hashed collection is not a good choice. Rather, switch to Arraylist , but note that with Arraylist you will lose the advantage to quickly get the desired student, as it can be with Set.

Answer 5

You should not use Set when the equals object methods change. If you identify students with a stable unique identification number, and equals just checks that identifier, then using Set is fine.

Note that the HashSet will use hashCode for indexing and comparison, and hashCode must include exactly those fields that are used to define equals .

Answer 6

The javadoc for Set says

Note. Great care should be taken if mutable objects are used as set items. The behavior of the set is not specified if the value of the object changes in a way that affects equal comparisons, while the object is an element in the set. A special case of this prohibition is that it is unacceptable for the set to contain itself as an element.

So, if you are going to use a HashSet , if you create hashCode() and equals() based on inmutable fields, then you will not have this problem. For example, using a unique studentID for each instance.

Answer 7

From your requirement, I thought the best structure should be a Map. In fact, the basic structure uses the map structure inside, and you also need to take care of overriding the equals method for a better search. Both the recruitment and the arraylist to find the target object need to adopt some search algorithm, so that it is not as efficient as you expected (especially in a very large collection situation). Even the map will spend some space, but if your identifier is a kind of primitive type, you can consider the primitive type of map implementation in the Trove library ,

Answer 8

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

Definitely, if you are going to change the values ​​used by the hash code or equal, it is not possible to use a HashMap or HashSet.

You say you want to remove and add a lot. The question is whether you want to do this selectively or randomly (based on the index). If you add, delete one by one, then by far the best choice is LinkedList. If you accidentally access objects, then an ArrayList is much more efficient.