How does HashMap work when inserting a new key-value pair if an element with the same key does not exist and equals for the key does not match others?

When inserting a new key-value pair into a HashMap, if such a key does not yet exist and the equals method for the key does not match others, the following occurs:

1. The hash code of the key is computed using the hashCode() method.
2. Based on the hash code, an index (bucket) in the internal array is determined.
3. Since there are no elements with such a key in this bucket (equals does not match), the new pair is simply added to this bucket.

Thus, the insertion happens quickly — without traversing existing elements with a matching key. If the bucket is empty, the element is placed directly.

Approximately like this:

int hash = key.hashCode();
int index = (array.length - 1) & hash;
// if there are no elements with such a key in array[index]
array[index] = new Node(key, value);