HashSet is not sensitive to content of array?

Question

how can I make this code work such that when I change the content of the array, HashSet considers a different hashcode for it? Right now it prints "true". I want it to print true if and only if the elements are exactly the same.

HashSet<int[][]> x = new HashSet<int[][]>();
int a[][] = {{1, 2}, {3, 4}};
x.add(a);
a[0][0] = 2;
a[0][1] = 1;
System.out.println(x.contains(a));

Answer 1

Unfortunately, we need to comply with the directive not to mix arrays and collections as far as possible while programming in Java. But in this particular case, I am not sure why you don't like the default behavior. What you are effectively doing is

1. add an object a to a set (no matter a is an array)
2. check if that same object (which has the same reference a) is in the set.

There is no way the contains check is going to be false in this case. And more importantly, don't you want this to be true?

As a Java novice (not implying that you are), I would have been more surprised with the following:

    HashSet<int[][]> x = new HashSet<>();
    int a[][] = {{1, 2}, {3, 4}};
    x.add(a);
    int[][] b = {{1, 2}, {3, 4}};
    System.out.println(x.contains(a));
    System.out.println(x.contains(b));

which prints

true
false

This is where the complication with respect to hashCode implementation of arrays in Java becomes evident. You try to reason that clearly b is same as a, and yet the set says it contains a and does not contain b.

Answer 2

The root cause of your problem is the semantics of equals(Object) and hashCode() for array objects as specified by the Java Language Specification, and the javadocs for java.lang.Object.

Basically:

• The equals(Object) method for an array type is specified to have the same semantics as the == operator.
• The hashCode() for an array type is specified to return the identity hashcode value for the object.

This means that two distinct arrays are never equal according to the equals object. It also means that assigning one of the elements of an array will never make the array equal to another.

The semantics of HashSet are defined in terms of equals(Object). That means that the answer to your question:

HashSet is not sensitive to content of array?

... is, correct: HashSet is not sensitive to the content of an array.

---

Your example

Now lets look at your example:

HashSet<int[][]> x = new HashSet<int[][]>();
int a[][] = {{1, 2}, {3, 4}};
x.add(a);
a[0][0] = 2;
a[0][1] = 1;
System.out.println(x.contains(a));

This returns true because the array that you put into the HashSet is the same array that you tested for. As explained above, the content of the array is irrelevant. HashSet relies on the equals(Object) method, and for an array type that tests object identity; i.e. if the array objects are the same object.

---

"The contract" ...

But suppose that you did this:

HashSet<List<Integer>> x = new HashSet<List<Integer>>();
List<Integer> a = new ArrayList<>();
a.append(1);
a.append(2);
x.add(a);
a.set(0, 3);
System.out.println(x.contains(a));

what is going to happen now?

Answer: BAD THINGS!

The problem is that equals(Object) and hashCode() for ArrayList are sensitive to the content of the array. But what we have done here is to "violate the contract" of how you are supposed to deal with objects in a HashSet. You are not supposed to modify an object that is a member of a hash set in such a way that its hashCode value changes.

If you violate the contract for equals / hashcode while an object is in a HashSet (or is the key of a HashMap or Hashtable), then the object is liable to get lost in the data structure.

As a general rule, it is a bad idea to use mutable objects as hash keys.

^{This is the point that various comments have made been making. It is a very important point ... though it is not actually the fundamental problem with your example, as you wrote it.}

---

Fixing your example

So how can we make your example work; i.e. do what (I think) you are really trying to do here?

This is for a simplified version with a 1-D array:

public List<Integer> makeSealedList(Integer ... values) {
    return Collections.immutableList(Arrays.asList(values.clone()));
}

HashSet<List<Integer>> x = new HashSet<List<Integer>>();
List<Integer> a = makeSealedList(1, 2);
List<Integer> b = makeSealedList(1, 2);
List<Integer> c = makeSealedList(3, 2);
x.add(a);

System.out.println(x.contains(a));   // prints true
System.out.println(x.contains(b));   // prints true
System.out.println(x.contains(c));   // prints false

But note that this only works for "constant arrays", and I have deliberately encapsulated them to ensure that our lists are constant.

If you want to be able to be able to change an array while it is in the hashset and have the hashset automatically notice the change and rehash the array based on its new ... that is not supported by any of the Java SE collection types. And I don't think it is implementable without a whole bunch of extra infrastructure.

(The practical solution to that would be to remove the "array" from set, update it, and then add it back again.)

Answer 3

Java arrays inherit from Object, and do not override equals() and hashCode(), which means that a HashSet or HashMap of arrays are really "identity" sets/maps, i.e. works similarly to IdentityHashMap.

There is no IdentityHashSet, because it would make little sense, though it can be simulated using IdentityHashMap.

Since arrays don't override equals() and hashCode(), they added equals() and hashCode() helper methods to the Arrays class, to your convenience.

Answer 4

Easiest (but not the best way) to fix your problem is, convert the array to string and store the string the HashSet.

HashSet<String> x = new HashSet<>();
int a[][] = {{1, 2}, {3, 4}};
x.add(Arrays.deepToString(a));
a[0][0] = 2;
a[0][1] = 1;
System.out.println(x.contains(Arrays.deepToString(a)));

The full working code in Codiva.io online compiler IDE.

Solving this issue the right way is actually more difficult and more involved. This will also explain why you haven't got a decent working solution yet.

You need to understand that the different between Pass By Value and Pass By Reference and in Java except for primitives everything is Pass By Reference. So, what you have added to the set is, a reference the the 2D array. So when the value changes, the value of the element (the reference to the array) present in the Set also changes. The second issue is the fact that array is mutable, that would call for more bugs when you use it as the key in HashMap or HashSet.

I posted this blog 10 years ago, when I tried to explain this the beginners. I think this is still relevant.

The TL;DR version is,

Never use a mutable element in a Set, and never as a Key in Map

In your case there is an additional error in your logic. If you see correctly,

Right now it prints "true". I want it to print true if and only if the elements are exactly the same.

In your case, when you insert the array 'a' into the Map, the map has some value, which is,

a[][] = {{1, 2}, {3, 4}}

Contents of the Set is also {{1, 2}, {3, 4}}

Now, you are changing the value of a. The new value is a[][] = {{2, 1},{3, 4}} Simultaneously, you have changed the value that is present in the set. At present, the set also contains {{2, 1},{3, 4}}. So it returns true. Unfortunately, you this is not want you want. The shortest way to explain your code is,

int a[] = {1, 2}
int b[] = a;
a[0] = 3;
System.out.println(Arrays.equals(a, b));

What do you expect the answer to be?

Answer 5

I am agree with @Dici that never use mutable value like arrays in a set and map. This is a nice practice for every programmer. The following answer is just to give an example for those who is learning Java and who want to know how Sets and Maps keep their uniqueness.

Since the HashSet use the HashMap to keep the uniqueness of the entry. And HashMap use hashCode() and equals() to compare the entries. So you have to override them.

If I was you, I will create a new class called Matrix to be the entry. And put them into the HashSet. Here is the code:

public class Matrix {

    @Override
    public int hashCode(){
        int[] hash=new int[2];
        for(int i=0;i<2;i++){
            hash[i]=Arrays.hashCode(matrix[i]);
        }
        return Arrays.hashCode(hash);
    }

    @Override
    public boolean equals(Object o){
        Matrix inM=(Matrix)o;
        for(int i=0;i<2;i++){
            if(!Arrays.equals(inM.matrix[i],this.matrix[i])){
                return false;
            }
        }
        return true;
    }

    //constructor
    public Matrix(int a,int b,int c,int d){
        matrix=new int[2][2];
        matrix[0][0]=a;
        matrix[0][1]=b;
        matrix[1][0]=c;
        matrix[1][1]=d;
    };

    //fields
    private int[][] matrix;
}

Now we insert the Matrix into the HashSet.

/**
 *  MAIN
 */
public static void main(String[] args){
    HashSet<Matrix> hs = new HashSet<Matrix>();
    Matrix m1 = new Matrix(1,2,3,4);
    Matrix m2 = new Matrix(5,6,7,8);

    hs.add(m1);
    System.out.println(hs.contains(m1));
    System.out.println(hs.contains(m2));
}

Then it works well.

//OutPut:
true
false