Какого размера подкапотный массив HashSet если добавить два значения с hashCode равный 0 и hashCode равный 1000000

Отличный и очень конкретный вопрос, который проверяет глубокое понимание внутренней реализации HashSet (а значит, и HashMap) в Java. Это не просто знание теории, а понимание того, как она применяется на практике.

Краткий ответ

Размер подкапотного массива (который в HashMap называется table) после добавления двух указанных элементов будет равен 16. Никакого расширения массива не произойдет, хотя значения хэш-кодов сильно различаются. Это связано с процессами индексирования и расширения (resize).

Подробное объяснение

HashSet<T> в Java реализован на основе HashMap<T, Object>, где значения элементов HashSet выступают в качестве ключей HashMap, а в качестве значения HashMap используется константа-заглушка PRESENT. Поэтому все вопросы о емкости, хэшах и расширении мы обсуждаем применительно к HashMap.

1. Начальная емкость и порог расширения

По умолчанию конструктор HashSet() создает HashMap с:

• Начальной емкостью (initial capacity) = 16
• Коэффициентом загрузки (load factor) = 0.75
• Порог расширения (resize threshold) = capacity * loadFactor = 16 * 0.75 = 12.

Это означает, что внутренний массив table изначально имеет длину 16. Массив расширится (удвоится) только тогда, когда количество уникальных элементов (size) превысит порог в 12. В нашем случае добавлено всего 2 элемента, поэтому до расширения очень далеко. Размер массива остается 16.

2. Процесс определения индекса в массиве

Ключевой момент — элемент помещается не в ячейку, равную его hashCode(). Этот код может быть любым int, в том числе отрицательным, а размер массива ограничен. Для преобразования хэш-кода в индекс используется следующая логика:

1. Вычисление внутреннего хэша (disturb/hash): Сначала hashCode ключа проходит через вспомогательную функцию hash() (в более старых версиях) или вычисляется непосредственно ((key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) в Java 8+). Цель — "размешать" биты хэш-кода, чтобы младшие биты, которые непосредственно используются для индекса, стали более случайными и уменьшили количество коллизий.
2. Определение индекса: Полученный хэш h преобразуется в индекс i в границах массива длиной n по формуле: i = (n - 1) & h. Операция & (побитовое И) эффективно выполняет взятие остатка от деления на n, но только когда n является степенью двойки (что всегда верно для table).

Применим это к нашему случаю (массив n = 16):

• n - 1 = 15. В двоичном виде: 0000 0000 0000 0000 0000 0000 0000 1111.
• Операция (n - 1) & h отсекает все старшие биты хэша, оставляя только младшие 4 бита (поскольку у 15 единичными являются только 4 младших бита).

Давайте посмотрим, что получится для наших значений (упрощенно, без учета этапа "размешивания", который для наглядности можно опунуть, так как он не изменит сути для этих примеров):

// Размер массива n = 16
int n = 16;
int nMinus1 = n - 1; // 15 (binary ...00001111)

// Для объекта с hashCode = 0
int hash1 = 0;       // binary ...00000000
int index1 = nMinus1 & hash1; // 15 & 0 = 0
// Элемент попадет в bucket с индексом 0.

// Для объекта с hashCode = 1_000_000
int hash2 = 1_000_000; // binary ...000011110100001001000000
int index2 = nMinus1 & hash2;
// Чтобы посчитать: 1_000_000 & 15.
// 1_000_000 % 16 = 0 (поскольку 1_000_000 = 62_500 * 16).
// Следовательно, index2 = 0.
// Элемент также попадет в bucket с индексом 0!

Важное следствие: Несмотря на огромную разницу в hashCode, оба элемента, скорее всего, окажутся в одной и той же ячейке (bucket) массива table с индексом 0 (если только их внутренний хэш после "размешивания" не изменит младшие биты). Они будут храниться в этой ячейке как связанный список (или дерево, если список слишком большой) Node объектов. Это называется коллизией хэш-кодов. Факт коллизии никак не влияет на момент расширения массива.

Итог

• Размер массива (table.length) останется равен 16, так как добавлено всего 2 элемента, что значительно меньше порога расширения (12).
• Разные hashCode не гарантируют попадания в разные ячейки массива. Индекс определяется младшими битами хэша. В данном примере оба элемента, вероятно, попадут в одну ячейку (индекс 0), что приведет к коллизии.
• Расширение массива до 32 произойдет только при добавлении 13-го уникального элемента (если все они имеют разные хэши и индексы). Наличие коллизий (элементов в одном bucket) даже ускоряет достижение порога, так как size растет при каждом новом ключе, независимо от коллизий.