How does a HashMap determines the right Key without calling equals()

user_19123115 0
Viewed 91

Here is an example of a Person class that I will use as a key.

It overrides equals() so that it always returns false and hashCode() that always returns 1.

public class Person {
    String name;
    int age;


    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        System.out.println("Equals is called");
        return false;
    }

    @Override
    public int hashCode() {
        System.out.println("Hashcode is called");
        return 1;
    }
}

Now let's use it as a key and randomly fill the map.

public class Main {

    public static void main(String[] args) {

        var person1 = new Person("Mike", 21);
        var person2 = new Person("Alex", 32);
        var person3 = new Person("Andrew", 45);

        Map<Person, String> peopleMap = new HashMap<>();

        peopleMap.put(person3, "SomeValue3");
        peopleMap.put(person2, "SomeValue1");
        peopleMap.put(person1, "SomeValue2");

        System.out.println("Getting a person \n \n");
        System.out.println(peopleMap.get(person3));
    }
}

Here is what I see in a console:

Hashcode is called
Hashcode is called
Equals is called
Hashcode is called
Equals is called
Equals is called

Getting a person 

Hashcode is called
SomeValue3

Questions:

  1. How could it determine the right key if the equals is always false?

  2. How could it get the right key without even calling equals() for getting an object by the key?

  3. If we move adding the person3 object down ( the one we are getting ) so it is in the middle - 1 equals() will be called for the first object. If we move adding to the 3 position, like this:

     peopleMap.put(person2, "SomeValue1");
 peopleMap.put(person1, "SomeValue2");
 peopleMap.put(person3, "SomeValue3");

2 times equals() will be called ( for person2 and person1 ) but none for the key we are getting.

Why is it so? I always thought that map can't store an order, but look like this.

hashcode hashmap equals java
3 Answers

Your equals implementation violates the contract of the method, specifically the first clause in the javadoc:

It is reflexive: for any non-null reference value x, x.equals(x) should return true.

However the HashMap implementation assumes the condition holds and as an optimization will first check if the key object is the same by reference before using equals. You can see this when you look at the source code of HashMap.

https://github.com/openjdk/jdk/blob/0f801fe6fd2fcc181121f9846f6869ca3a03e18a/src/java.base/share/classes/java/util/HashMap.java#L577-L579

    final Node<K,V> getNode(Object key) {
...
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
...

You can also confirm this by stepping through the execution with a debugger.

user_39454730

HashMap maintains an array of buckets under the hood. Each bucket corresponds to a range of hashes. Entries in the buckets are represented as nodes which form either a Linked list or Red-black tree (depending on the number of nodes in the bucket).

You've created a class with a broken hashCode() which instances always produce identical hashes and when you use them as keys they will end up in the same bucket. So basically these objects would cause collisions in the HashMap.

After you've populated the HashMap using instances of Person as keys and invoking get() providing one of the existing keys, this method will internally invoke getNode().

getNode() would find the corresponding bucket (based on the hash of the provided key), and if the contents of this bucket isn't null - i.e. the bucket contains either a list or a tree, it would traverse through the list (tree) checking each node and firstly before invoking equals() (which is useless in this case) it would use the identity comparison on keys.

(k = e.key) == key

And if the keys point to the same object, this comparison is fast and there's no need to resort to comparison using equals() (which might be costful in case of the complex object graph).

That's why even with broken equals/hashCode HashMap is able to identify the required entry, when you're giving exactly the same object as a key.

user_179499450

  1. How could it determine the right key if the equals is always false?

  2. How could it get the right key without even calling an equals for getting an object by the key?

you can refer hashTable internal working for detail information as it is difficult to explain it here. Have tried to explain in short.

  • Every hash-based DataStructure internally follows HashTable.
    Map<Person, String> peopleMap = new HashMap<>();
  • here init_capacity=16 (HashMap) => 16 distinct bucketId's [0-15] , like an array of references, initially value= null.

each slot of array is called as bin/bucket

Java HashTable internally use Singly Linear LinkedList

  • bucketId calculated internally like, bucketId = @Overrided HashCode + some internal calculation

  • your Hashcode() returns everytime 1 implies bucketId = 1 + (say)3 = 4 [everytime].

     peopleMap.put(person3, "SomeValue3");
  1. invokes Hashcode one time => bucketId = 4 is empty initially so JVM do NOT invokes equals() & directly attach data (node)(in simple language).
     peopleMap.put(person2, "SomeValue1");
  1. invokes Hashcode one time => bucketId = 4. Now invokes equals 1 time since to check if person2 value equal to previous added value ie. person3.
     peopleMap.put(person1, "SomeValue2");

3.invokes Hashcode one time => bucketId = 4. Now invokes equals 2 times to check duplicates . ie. 1time for person3, 2ndly for person2.

hence output:

Hashcode is called

Hashcode is called

Equals is called

Hashcode is called

Equals is called

Equals is called

DIAGRAM:

HOPE THIS HELPS :)

user_190259030
Related