Как HashMap находит место для пары ключ-значение?

HashMap — массив корзин (bucket). При put(key, value):

1. вычисляется key.hashCode(), старшие биты подмешиваются к младшим;
2. индекс корзины — hash & (n - 1), где n — размер массива (степень двойки);
3. если корзина пуста — запись кладётся туда;
4. если нет — это коллизия: идём по записям корзины и сравниваем ключи через equals; совпал — заменяем значение, нет — добавляем запись.

При чтении get(key) путь тот же, поэтому в среднем доступ — O(1).

Коллизии. Записи одной корзины образуют связный список. Если он вырастает до 8 элементов, а таблица не меньше 64 корзин, список превращается в красно-чёрное дерево (treeify) — худший случай становится O(log n) вместо O(n).

Расширение. Когда число записей превышает ёмкость × коэффициент загрузки (по умолчанию 0.75), массив удваивается и записи перераспределяются.

Требование к ключу: равные по equals объекты должны давать одинаковый hashCode, а поля, от которых они зависят, не должны меняться, пока ключ лежит в карте. Иначе запись «потеряется».

Map<String, Integer> stock = new HashMap<>();
stock.put("apple", 10);   // hash("apple") → корзина
stock.get("apple");       // та же корзина → equals → 10