Comparing objects in HashSet

Question

I'm making a 2D game that has a stars in it. I decided to create constructor in class named Star that gives random coordinates.

public Star(){
    super(0,0);
    x = randomX.nextInt(maxX - minX + 1);
    y = randomY.nextInt(maxX - minY + 1);
}

Then, in other class I put them in HashSet

Set<Star> star = new HashSet<>();

public Set<Star> generateStars(){
    while (star.size() < numberOfStars){
            star.add(new Star());
    }
    return star;
}

Of course, I have render and tick methods but I think it's not worth to paste them. My lecturer told me that there can be same stars and to prevent that I should use identity function using hashcodes. Can someone help me figure that out ? I imagine that this function should check if the hashcodes are the same and if it's the case it should return only one value that way we will add 1 object instead of 2 into the HashSet. Am I right ?

Answer 1

Overriding the hashCode() method alone in your Star class will not work you will have to override the equals() method.

See the following code where we don't override the equals() method:

class Star {
    int x, y;

    public Star(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

public class Main {
    public static void main(String[] args) {
        Star s1 = new Star(0, 0);
        Star s3 = new Star(0, 0);
        Star s2 = new Star(31, -31*31);
        Set<Star> set = new HashSet<>();
        set.add(s1);
        set.add(s2);
        System.out.println(set.size());
    }
}

This will print 3 (instead of 2 what you might expect).

The reason for this is that the add method of java.util.Set compares 2 objects based on equals() method and not based on hashCode() method.

In the above code for the Star class, if you add the equals() method the output will be 2 now. For your reference the you can override the equals() method as follows:

@Override
public boolean equals(Object startObject) {
    if (this == startObject) return true;
    if (startObject == null || getClass() != startObject.getClass()) return false;
    Star star = (Star) startObject;
    return x == star.x &&
            y == star.y;
}

So why do you need to add hashCode()?

1. As you are using HashSet the add method behind the scene will call the equals() method and will also call hashCode() to decide the bucket in which the new object should be put. To maintain the contract of hashCode() and equals() Both should be overridden.
2. When ever you override equals(), it is recommended to override hashCode() also. (Vice-versa is also true). See this link for details.

Contract for hashCode() and equals(): If for two objects say o1 and o2, o1.equals(o2) is true then hash of o1 and o2 should be same.

Make sure that you understand this properly, from the above statement it is not implied that if the hash of 2 objects are same, then o1.equals(o2) should return true. It can be possible that for 2 objects, their hash is same but the o1.equals(o2) returns false

See here, what Object's hashCode() method guarantees.

See this link to get more detailed information about this topic.

Answer 2

In java, when adding an object to a HashSet, the add method uses the 'equals' method, which is part of the Object class (however you can override it) in order to determine if the set already contains the object you are trying to add, see : https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html

However, if you are overriding the equals method then you should also override the hashCode method, this is very well explained in the following post : Why do I need to override the equals and hashCode methods in Java?

If you are going to follow this advice, I would also advise using ApacheCommonsLang EqualsBuilder and HashCodeBuilder if your lecturer allows it as they provide a solid implementation based on the rules laid out in the book 'Effective Java' by Joshua Bloch

To override the equals method in your Star class, you want to think about the criteria that make two star objects equal. From your example this might be that both of them have the same x and y co-ordinates.

Answer 3

you can override hashCode() method from Object. So, in your Star class, add:

@Override
public int hashCode() {
    in hash = .... //make your hash code about the coordinates of your star.
    return hash;
}

so, when you place a new star with the same co-ordiante in the hash map, it will overwrite the previous start with the same co-ordiantes if already present in the map.

Answer 4

You have to implement hashCode and equals. the code should be like this:

  public static class Star {
    int x, y;
    public Star(int x, int y) {
      this.x = x;
      this.y = y;
    }

    @Override
    public int hashCode() {
      return x * 1000 + y;
    }

    @Override
    public boolean equals(Object obj) {
      if (obj instanceof Star) {
        Star s = (Star) obj;
        return this.x == s.x && this.y == s.y;
      }

      return false;
    }

  }

  public static void main(String args[]) throws Exception {
    HashSet<Star> set = new HashSet<Star>();
    set.add(new Star(1, 1));
    set.add(new Star(1, 1));

    System.out.println(set.size());
  }

note: choose the suitable hashcode function for you. I assumed here that y should always be less than 1000.

Answer 5

If you are using eclipse as your editor just right-click on the editor pane, go-to source then generate hashcode() and equals() pick the parameters you would like to consider. You will get an autogenerated function.