Как алгоритмически рассчитывается бакет для вставки элемента в HashMap

В Java бакет (индекс) для вставки элемента в HashMap рассчитывается по формуле:

int index = (n - 1) & hash

Где:

• n — текущий размер массива бакетов (всегда степень двойки)
• hash — это результат hashCode(), дополнительно обработанный внутренним методом hash() для улучшения распределения:

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

Пример:
Для ключа "test" (hashCode() = 3556498) и n = 16:

1. hash = 3556498 ^ (3556498 >>> 16) = 3556498 ^ 54 = 3556444
2. index = (16 - 1) & 3556444 = 15 & 3556444 = 12

Примечание:

• Если бакет уже занят, используется цепочка (в Java 8 — дерево при коллизиях).
• При null-ключе элемент всегда попадает в бакет 0.