Java HashSet contains duplicates if contained element is modified

To add to @EJP's answer, what will happen in practice if you mutate objects in a HashSet to make them duplicates (in the sense of the equals / hashcode contract) is that the hash table data structure will break.

• Depending on the exact details of the mutation, and the state of the hash table, one or both of the instances will become invisible to lookup (e.g. contains and other operations). Either it is on the wrong hash chain, or because the other instance appears before it on the hash chain. And it is hard to predict which instance will be visible ... and whether it will remain visible.

• If you iterate the set, both instances will still be present ... in violation of the Set contract.

Of course, this is very broken from the application perspective.

You can avoid this problem by either:

• using an immutable type for your set elements,
• making a copy of the objects as you put them into the set and / or pull them out of the set,
• writing your code so that it "knows" not to change the objects for the duration ...

From the perspective of correctness and robustness, the first option is clearly best.

Incidentally, it would be really difficult to "fix" this in a general way. There is no pervasive mechanism in Java for knowing ... or being notified ... that some element has changed. You can implement such a mechanism on a class by class basis, but it has to be coded explicitly (and it won't be cheap). Even if you did have such a mechanism, what would you do? Clearly one of the objects should now be removed from the set ... but which one?

You are correct and I don't think there is any way to protect against the case you discuss. All of collections which use hashing and equals are subject to this problem. The collection has no notification that the object has changed since it was added to the collection. I think the solution you outline is good.

If you are so concerned with this issue, perhaps you need to rethink your data structures. You could use immutable objects for instance. With immutable objects you would not have this problem.

HashSet is not aware of its member's properties changing after the object has been added. If this is a problem for you, then you may want to consider making GraphEdge immutable. For example:

GraphEdge edge4 = edge2.changeName("new_name");

In the case where GraphEdge is immutable, changing a value result in returning a new instance rather changing the existing instance.

method that can be used to print the elements of a LinkedList of String objects, without any duplicate elements. The method takes a LinkedList object as an input, and then creates a new HashSet object. The method then iterates through the elements of the input LinkedList, and adds each element to the HashSet. Since a HashSet does not allow duplicate elements, this ensures that only unique elements are added to the HashSet.

Then, the method iterates through the HashSet and prints each element to the console, separated by a space. Unlike the printList method, this method does not add any newlines before or after the list of elements. It simply prints the string "Non-duplicates are: " followed by the elements of the HashSet.

   public static void printSetList(LinkedList<String> list) {
    Set<String> hashSet = new HashSet<>();
    for (String v : list) {
        hashSet.add(v);
    }
    System.out.print("Non-duplicates are: ");
    for (String v : hashSet) {
        System.out.print(v + " ");
    }
}

Objects.hashCode is meant to be used to generate a hascode using parameter objects. You are using it as part of the hascode calculation.

Try replacing your implementation of hashCode with the following:

public int hashCode()
{
    return Objects.hashCode(this.id, this.name);
}

You will need to do the unique detection a the time you iterate your list. Making a new HashSet might not seem the right way to go, but why not try this... And maybe not use a HashSet to start with...

public class TestIterator {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();

        list.add("1");
        list.add("1");
        list.add("2");
        list.add("3");

        for (String s : new UniqueIterator<String>(list)) {
            System.out.println(s);
        }
    }
}

public class UniqueIterator<T> implements Iterable<T> {
    private Set<T> hashSet = new HashSet<T>();

    public UniqueIterator(Iterable<T> iterable) {
        for (T t : iterable) {
            hashSet.add(t);
        }
    }

    public Iterator<T> iterator() {
        return hashSet.iterator();
    }
}