How does the HashMap data structure determine key equality when inserting and searching for elements?

In Java, the HashMap data structure uses the hashCode() and equals() methods to determine key equality when inserting and searching for elements.

• When inserting a key, HashMap first computes the hash code of the key using the hashCode() method. This hash code is used to determine the index of the bucket in the array.
• If there are already elements in the bucket (collision), HashMap iterates through them and compares the keys using the equals() method.
• If the equals() method returns true for an existing key, the value is updated; otherwise, a new element is added.

It is important that:

• The hashCode() method is overridden so that equal objects have the same hash code.
• The equals() method correctly compares objects based on the notion of equality.

Example:

class Key {
    private int id;

    @Override
    public int hashCode() {
        return Integer.hashCode(id);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Key other = (Key) obj;
        return this.id == other.id;
    }
}

HashMap<Key, String> map = new HashMap<>();
map.put(new Key(1), "value1");
String val = map.get(new Key(1)); // returns "value1"