Creating Java classes usable as keys for a hashmap

Question

I have made a class called Coordinates which simply holds some x and y integers. I want to use this as a key for a HashMap.

However, I noticed that when you create two different instances of Coordinates with the same x and y values, they are used as different keys by the hash map. That is, you can put two entries even though both of them have the same coordinates.

I have overriden equals():

public boolean equals(Object obj) {
    if (!(obj instanceof Coord)) {
        return false;
    }else if (obj == this) {
        return true;
    }
    Coord other = (Coord)obj;
    return (x == other.x && y == other.y);
}

But the HashMap still uses the two instances as if they were different keys. What do I do?

And I know I could use an integer array of two elements instead. But I want to use this class.

@ZouZou oh no, I didn't know that. I see that it returns an integer. What should I return? Surely it is not the sum of the x and y. — Saturn, Dec 20 '14 at 19:28
You need to be consistent. I.e if a equals b then a.hashcode == b.hashcode. See also http://stackoverflow.com/questions/27581/what-issues-should-be-considered-when-overriding-equals-and-hashcode-in-java — Alexis C., Dec 20 '14 at 19:28
I suggest you read the Javadoc for Object which describes what hashCode much do. — Peter Lawrey, Dec 20 '14 at 19:43
This question doesn't show any research effort. Documentation of *equals*: *" Note that it is generally necessary to override the hashCode method whenever this method is overridden..."* — Christian Strempfer, Dec 20 '14 at 20:52

score 6 · Accepted Answer · answered Dec 20 '14 at 19:30

6

You need to override hashCode. Java 7 provides a utility method for this.

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

answered Dec 20 '14 at 19:30

mkobit

43,979
12
156
150

1

An explanation on why it is required would be nice, but thanks for pointing out this utility class, I did not know about it and it provides some useful methods :) – Dici Dec 20 '14 at 19:41
From http://tutorials.jenkov.com/java-collections/hashcode-equals.html *When inserting an object into a hastable you use a key. The hash code of this key is calculated, and used to determine where to store the object internally. When you need to lookup an object in a hashtable you also use a key. The hash code of this key is calculated and used to determine where to search for the object.* – wassgren Dec 20 '14 at 20:21

score 4 · Answer 2 · answered Dec 20 '14 at 19:29

You should also override hashCode() so that two equal instances have the same hashCode(). E.g.:

@Override
public int hashCode() {
    int result = x;
    result = 31 * result + y;
    return result;
}

Note that it is not strictly required for two instances that are not equal to have different hash codes, but the less collisions you have, the better performance you'll get from you HashMap.

score 1 · Answer 3 · answered Dec 20 '14 at 19:33

A hash map uses the hashCode method of objects to determine which bucket to put the object into. If your object doesn't implement hashCode, it inherits the default implementation from Object. From the docs:

As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

As such, each object will appear to be distinct.

Note that different objects may return the same hashCode. That's called a collision. When that happens, then in addition to the hashCode, the hash map implementation will use the equals method to determine if two objects are equal.

Note that most IDE offer to generate the equals and hashCode methods from the fields defined in your class. In fact, IntelliJ encourages to define these two methods at the same time. For good reason. These two methods are intimately related, and whenever you change one of them, or implement one of them, or override one of them, you must review (and most probably change) the other one too.

The methods in this class are 100% generated code (by IntelliJ):

class Coord {
    private int x;
    private int y;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Coord coord = (Coord) o;

        if (x != coord.x) return false;
        if (y != coord.y) return false;

        return true;
    }

    @Override
    public int hashCode() {
        int result = x;
        result = 31 * result + y;
        return result;
    }
}

Dici · Answer 4 · 2014-12-20T19:42:45.813

You probably did not override the hashCode method. Why is that required ? To answer this, you must understand how an hashtable works.

An hashtable is basically an array of linkedlists. Each bucket in the array corresponds to a particular value of hashCode % numberOfBuckets. All the objects with the same hashCode % numberOfBuckets will be stored within a linkedlist in the associated bucket and will be recognized (during the lookup for instance) basing on their equals method. Therefore, the exact specification is a.hashCode() != b.hashCode() => !a.equals(b) which is equivalent to a.equals(b) => a.hashCode() == b.hashCode().

If you use the default implementation of hashCode, which is based on the reference, then two objects that are equal but have a different reference (and so, most probably, a different hashCode) will be stored in a different bucket, resulting in a duplicate key.

Creating Java classes usable as keys for a hashmap

4 Answers4