HashSet does not seem to realize that two objects are the same.

Question

I'm trying to use HashSet to store objects of a class that I created, but apparently the same objects seem to have two different hashes, which is why the contains method does not realize that the object is already in the HashSet. This leads to my program running out of heap memory.

I don't think I'm doing anything wrong, but I wanted a second opinion anyway. I've done similar operations before which all worked fine, which makes this particularly annoying. I'd appreciate any help.

Here's my code

move1 = new Move(t,s);
if(move1.hashCode()==new Move(t,s).hashCode())
    System.out.println("match");
move2 = new Move(s,t);
moves.add(move1); 
moves.add(move2);
if(moves.contains(new Move(t,s)))
    System.out.println("match found");

Here's the Move class:

public class Move {
    private int move1;
    private int move2;

    Move(int m1, int m2)
    {
        move1 = m1;
        move2 = m2;
    }

    public String toString()
    {
         return String.valueOf(move1)+" "+String.valueOf(move2);
    }
}

Here's the output I get

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.HashMap.addEntry(HashMap.java:797)
    at java.util.HashMap.put(HashMap.java:431)
    at java.util.HashSet.add(HashSet.java:194)
    at makeMove.<init>(makeMove.java:33)

Rodrick

Retagged, since the exception is a side-effect of the problem. – Stableman

Answer 1

You need to override the Object#hashCode() method in the Move class to let it return the same hashCode() value for the state of the Move instance. Don't forget to override Object#equals() as well.

See also:

• Overriding equals and hashCode in Java

---

Hint: if you're using an IDE like Eclipse, you can also just autogenerate them. Rightclick somewhere the Move class, choose Source > Generate hashCode() and equals(). Here is how it look like then:

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + move1;
    result = prime * result + move2;
    return result;
}

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Move other = (Move) obj;
    if (move1 != other.move1)
        return false;
    if (move2 != other.move2)
        return false;
    return true;
}

Forewoman

Thanks for the heads up. Especially for the Eclipse tip. – Rodrick

This is all documented in the Javadoc for HashSet. That's what it's there for! – Stableman

Answer 2

HashSet will determine equality based on calling hashCode() and equals(). You have not implemented these, so you'll inherite them from Object. The hashCode and equals methods of Object is just based on whether the references are equal.

That's why if(move1.hashCode()==new Move(t,s).hashCode()) is false. move1 is a different instance than the instance created by calling new Move(t,s).hashCode()

You'll need to implement hashCode and equals in your Move class.

e.g.(though perhaps non-optimal, and you might want a null safe equals - have your IDE generate them if it can)

public int hashCode() {
    return move1 ^ move2 +;
}

public boolean equals(Object o) {
  if(!other instanceof Move) 
      return false;

  Move other = (Move)o;

  return other.move1 == move1 && other.move2 == move2;
}

Ehlers

Answer 3

You have to override equals() and hashCode().

This may be an option.

import static java.lang.System.out;
public class Move {
    private int move1;
    private int move2;

    Move(int m1, int m2) {
        move1 = m1;
        move2 = m2;
    }

    public String toString() {
         return String.valueOf(move1)+" "+String.valueOf(move2);
    }

    public int hashCode() {
        return move1 * 31 + move2 * 31;
    }
    public boolean equals( Object other ) {
        if( this == other ) { return true; }
        if( other instanceof Move ) {
            Move m2 = ( Move ) other;
            return this.move1 == m2.move1 && this.move2 == m2.move2;
        }
        return false;
    }

    public static void main( String  [] args ) {
        out.println( new Move(2,3).equals( new Move(2,3)));
        out.println( new Move(1,1).hashCode() == new Move(1,1).hashCode()  );
    }
}

You have to define if the order of the move is relevant ( 1,2 isequals to 2,1 or not )

For more information:

What issues should be considered when overriding equals and hashCode in Java?

Shalom

Your hashcode isn't quite right. You shouldn't be multiplying both numbers by 31 and then adding. You should multipy move1 by 31, then multiply the result by 31 and add move2. – Celtic

@Celtic wrong, there's absolutely no requirement to follow any particular algorithm to create the hash code (see docs.oracle.com/en/java/javase/13/docs/api/java.base/java/lang/…) The fact the way you describe is more popular is completely irrelevant to the correctness of the outcome. You could use any other number and any other operation and order as long as it conforms to the above specification. I understand where are you coming from though, but there's a difference between that and saying my example is "not quite right", and "I shouldn't do it" that way – Shalom

By that logic it's correct to make all your hashCode() functions return 1. Sure, you can do what you want, but there's a reason it's generally done with a particular strategy in mind: Because it provides more varied bucketing, which is the point of hashing in the first place. Your code example makes both numbers multiples of 31, which means their sum is also a multiple of 31, and that can cause every item to hash into the same bucket. – Celtic