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
– Saturn, Commented Dec 20, 2014 at 19:28
You need to be consistent. I.e if a equals b then a.hashcode == b.hashcode. See also stackoverflow.com/questions/27581/… — Alexis C.
– Alexis C., Commented Dec 20, 2014 at 19:28
I suggest you read the Javadoc for Object which describes what hashCode much do. — Peter Lawrey
– Peter Lawrey, Commented Dec 20, 2014 at 19:43

mkobit · Accepted Answer · 2014-12-20 19:30:44Z

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, 2014 at 19:30

mkobit

47.8k12 gold badges162 silver badges159 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Dici Over a year ago

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 :)

wassgren Over a year ago

From 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.

Mureinik · Accepted Answer · 2014-12-20 19:29:55Z

4

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.

answered Dec 20, 2014 at 19:29

Mureinik

316k54 gold badges400 silver badges405 bronze badges

Comments

janos · Accepted Answer · 2014-12-20 19:33:26Z

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 · Accepted Answer · 2014-12-20 19:42:45Z

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.

Collectives™ on Stack Overflow

Creating Java classes usable as keys for a hashmap

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related