Как HashMap находит корзину для ключа и что происходит при коллизиях?

HashMap берёт hashCode() ключа и перемешивает старшие биты с младшими: h ^ (h >>> 16). Длина таблицы всегда степень двойки, поэтому индекс корзины считается быстро: (n - 1) & hash.

В корзине элементы лежат списком. При поиске HashMap сравнивает сначала сохранённый хеш, затем ссылку и equals. Если в корзине больше 8 элементов, а таблица не меньше 64 корзин, список превращается в красно-чёрное дерево.

Когда элементов становится больше ёмкость × loadFactor (по умолчанию 16 × 0,75 = 12), таблица удваивается. Каждый элемент либо остаётся в своей корзине, либо переезжает ровно на старую длину вперёд: решает один бит хеша.

static int hash(Object key) {
    int h;
    return key == null ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

int index = (table.length - 1) & hash(key);