Как работает HashMap при вставке новой пары ключ-значение, если элемент с таким ключом еще не существует и equals для ключа не совпадает с другими?

При вставке новой пары ключ-значение в HashMap, если такого ключа ещё нет и метод equals для ключа не совпадает с другими, происходит следующее:

1. Вычисляется хеш-код ключа с помощью метода hashCode().
2. На основе хеш-кода определяется индекс (бакет) в внутреннем массиве.
3. Поскольку в этом бакете нет элементов с таким ключом (equals не совпадает), новая пара просто добавляется в этот бакет.

Таким образом, вставка происходит быстро — без обхода существующих элементов с совпадающим ключом. Если бакет пуст, элемент помещается напрямую.

Примерно так:

int hash = key.hashCode();
int index = (array.length - 1) & hash;
// если в array[index] нет элементов с таким ключом
array[index] = new Node(key, value);