Peculiar HashMap Behavior

Question

I was reviewing one of Oracle’s Java Certification Practice Exams when I came across the follow question:

Given:

class MyKeys {
    Integer key;
    MyKeys(Integer k) {
        key = k;
    }
    public boolean equals(Object o) {
        return ((MyKeys) o).key == this.key;
    }
}

And this code snippet:

Map m = new HashMap();
MyKeys m1 = new MyKeys(1);
MyKeys m2 = new MyKeys(2);
MyKeys m3 = new MyKeys(1);
MyKeys m4 = new MyKeys(new Integer(2));
m.put(m1, "car");
m.put(m2, "boat");
m.put(m3, "plane");
m.put(m4, "bus");
System.out.print(m.size());

What is the result?

A) 2

B) 3

C) 4

D) Compilation fails

My guess was B because m1 and m3 are equal due to their key references being the same. To my surprise, the answer is actually C. Does put() do something that I am missing? Why wouldn’t "plane" replace "car"? Thank you!

Answer 1

With given definition of class i.e

class MyKeys {
    Integer key;
    MyKeys(Integer k) {
        key = k;
    }
    public boolean equals(Object o) {
        return ((MyKeys) o).key == this.key;
    }
}

It will result ans = 4, it has only equal method, if you add definition of hashcode then it will result ans=3

class MyKeys {
    Integer key;
    MyKeys(Integer k) {
        this.key = k;
    }

    @Override
    public boolean equals(Object o) {
        return ((MyKeys) o).key == this.key;
    }

    @Override
    public int hashCode(){
        return key*key;
    }
}

Contract of equal and hashcode:

If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result. If you only override equals() and not hashCode() your class violates this contract.

The problem you will have is with collections where unicity of elements is calculated according to both .equals() and .hashCode(), for instance keys in a HashMap. If you have two objects which are .equals(), but have different hash codes, you lose!

Answer 2

If we keep this simple, since this is for a Java Certification.

Notice that MyKeys doesn't override hashCode, you know there will be something about it. And I usually try to remember only one thing about Object.hashCode

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

Or in short, every instance will have a distinct hashcode. Meaning that with this code, every new MyKeys will add a new pair in the map.

In reality, this is a bit more complex since the method still return an integer, so the risk of collision is still present (integer doesn't provide infinite amount of values). You can see a bit more about this here.

---

This explain why the answer is that the map will have a size of 4. Each key inserted is a different instance.

Answer 3

As answered by others, the ans will be 4, reason being not overriding hashcode method.

For a more clear reason, whenever an object is added in hash map, the hashcode of the key is generated, which decides the location of the entry set. The 2 objects m1 and m3 will have different hash codes as the hashcode method is not overridden (usual hashcode behaviour). Different hash code will not create any collision and a new entry is made.

On the contrary, the equals methods is called only after the hashcode method produces the same result, i.e., same hash code.

In case of m2 and m4 also, the 2 objects have different hash codes, hence 2 different entries, with no calling done to the equals method.

Hence, in cases of hashing, it is necessary to overload hashcode method, along with equals.

Answer 4

It will be more clear when we see the implementation of put method of HashMap.

// here hash(key) method is call to calculate hash.
// and in putVal() method use int hash to find right bucket in map for the object.
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

In your code you @Override only equals method.

class MyKeys {
    Integer key;
    MyKeys(Integer k) {
        key = k;
    }
    public boolean equals(Object o) {
        return ((MyKeys) o).key == this.key;
    }
}

To achieve output you need to override both hashCode() and equals() method.