🔑 Розділ 10 · Питання #28

Як правильно підібрати початкову capacity для HashMap

Якщо конструктор викликається без параметрів (new HashMap<>()), за замовчуванням обирається місткість 16 із порогом розширення 12 ($16 \times 0.75$). Якщо заздалегідь відомо, що...

🔑 HashMap equals hashCode 📄 Вихідний Markdown

🟢 Junior Level

Початкова місткість (Initial Capacity) — це розмір внутрішнього масиву бакетів, який резервується в пам’яті під час створення HashMap.

Якщо конструктор викликається без параметрів (new HashMap<>()), за замовчуванням обирається місткість 16 із порогом розширення 12 ($16 \times 0.75$). Якщо заздалегідь відомо, що в мапу буде додано, наприклад, 1 000 елементів, створення HashMap за замовчуванням призведе до 7 послідовних ресайзів ($16 \to 32 \to 64 \to 128 \to 256 \to 512 \to 1024 \to 2048$), кожен з яких вимагає виділення нового масиву й копіювання всіх наявних елементів.

Золоте правило розрахунку

Щоб додати $N$ елементів без жодного ресайзу, початкову місткість обчислюють з урахуванням коефіцієнта завантаження loadFactor (типово $0.75$):

\[\text{capacity} = \left\lceil \frac{\text{очікувана кількість}}{0.75} \right\rceil = \text{очікувана кількість} \times \frac{4}{3}\] 
import java.util.HashMap;
import java.util.Map;

public class InitialCapacityDemo {
    public static void main(String[] args) {
        int expectedSize = 100;

        // Розрахунок вручну: 100 / 0.75 = 133.33 -> округлюємо вгору до 134
        int capacity = (int) Math.ceil(expectedSize / 0.75f);
        Map<String, Integer> map = new HashMap<>(capacity);

        // Починаючи з Java 19 — сучасний офіційний спосіб:
        Map<String, Integer> modernMap = HashMap.newHashMap(expectedSize);
    }
}

Аналогія: Якщо ви чекаєте на банкет 100 гостей, ви не замовляєте спочатку столик на 16 місць, а потім 7 разів поспіль не змінюєте залу на все більшу й більшу в міру прибуття гостей. Ви одразу бронюєте залу на 134+ місць, щоб усім вистачило простору з комфортом.

🟡 Middle Level

Чому наївний виклик new HashMap<>(1000) призводить до ресайзу?

Поширена помилка на співбесідах — вважати, що виклик new HashMap<>(1000) запобіжить ресайзу для 1000 елементів:

  1. Ви передали 1000. Метод tableSizeFor(1000) округлює це число до найближчого степеня двійки вгору $\to$ 1024.
  2. Поріг розширення розраховується як: \(\text{threshold} = 1024 \times 0.75 = 768\)
  3. Ви починаєте наповнювати мапу елементами.
  4. Під час додавання 769-го елемента умова ++size > threshold ($769 > 768$) стає істинною!
  5. Відбувається високовартісний ресайз таблиці з 1024 до 2048 бакетів.

Правильний розрахунок для 1000 елементів:

\(\text{initialCapacity} = (int) \left(\frac{1000}{0.75f}\right) + 1 = 1334\)

  • tableSizeFor(1334) округлює вгору до степеня двійки $\to$ 2048.
  • Поріг: $\text{threshold} = 2048 \times 0.75 = 1536$.
  • Усі 1000 елементів гарантовано вміщуються в таблицю без ресайзу ($1000 \le 1536$).

Офіційний API: фабричні методи Java 19+

Починаючи з Java 19 (JDK 19), розробникам більше не потрібно вручну виконувати ділення на 0.75f. До стандартної бібліотеки було додано статичні фабричні методи:

// Створює HashMap із місткістю, достатньою для 10 000 елементів без ресайзу:
Map<String, Order> orders = HashMap.newHashMap(10_000);

// Аналогічно для зв'язаних мап та множин:
Map<String, Order> linkedOrders = LinkedHashMap.newLinkedHashMap(10_000);
Set<String> uniqueTags = HashSet.newHashSet(10_000);

Усередині OpenJDK метод HashMap.newHashMap реалізований саме через формулу ділення:

static int calculateHashMapCapacity(int numMappings) {
    return (int) Math.ceil(numMappings / (double) DEFAULT_LOAD_FACTOR);
}

🔴 Senior Level

Вплив завищеної місткості на продуктивність (Over-allocation Overhead)

Існує спокуса завжди задавати місткість «з величезним запасом» (наприклад, new HashMap<>(1_000_000) під 100 елементів). Це породжує серйозні негативні наслідки:

  1. Витрати Heap Memory: Масив посилань table на 1 000 000 комірок за увімкненого прапорця UseCompressedOops миттєво алокує 4 МБ пам’яті під порожні посилання null (або 8 МБ без стиснення покажчиків) ще до вставки даних.
  2. Деградація швидкості ітерації: Складність обходу map.keySet(), map.values() та map.entrySet() становить $O(\text{capacity} + \text{size})$. Ітератор змушений послідовно перебирати весь масив table.length. При capacity = 1_000_000 та size = 10 ітератор виконає 999 990 порожніх перевірок комірок пам’яті на null, що спричинить тисячі апаратних промахів кешу CPU (L1/L2/L3 Cache Misses).
  3. Навантаження на збирач сміття (GC Pressure): Великі масиви посилань вимагають від GC сканування Card Table під час відстеження міжрегіональних покажчиків (G1 / ZGC), що збільшує час пауз на фазах розмітки.

Порівняння підходів до створення HashMap

Підхід Ресайзи при $N=1000$ Підсумковий Capacity Пам’ять масиву посилань Швидкість вставки
new HashMap<>() (default) 7 ресайзів 2048 8 КБ Повільно (латентні сплески)
new HashMap<>(1000) (помилковий) 1 ресайз (на 769-му) 2048 8 КБ Середньо (один латентний спайк)
HashMap.newHashMap(1000) 0 ресайзів 2048 8 КБ Максимальна (стабільний latency)
new HashMap<>(100_000) (надлишковий) 0 ресайзів 131 072 512 КБ Швидка вставка / повільна ітерація

4 Tricky Questions

1. Що станеться, якщо створити new HashMap<>(12) і додати рівно 12 елементів? Чи спрацює resize()?

Відповідь: Для 12 елементів — ні, але для 13 — так! Простежимо логіку HotSpot:

  1. Ви передали 12. Метод tableSizeFor(12) округлює 12 вгору до найближчого степеня двійки $\to$ 16.
  2. Поріг розширення розраховується як: \(\text{threshold} = 16 \times 0.75 = 12\)
  3. Вставляємо 11 елементів: size стає 11 ($11 \le 12$).
  4. Вставляємо 12-й елемент: putVal виконує перевірку: if (++size > threshold) resize(); Підставляємо значення: 12 > 12 $\implies$ false. Ресайзу поки немає!
  5. Але якщо ми додамо 13-й елемент: $13 > 12 \implies$ спрацює resize(). Якщо ж вимагалося зберегти рівно 12 елементів із гарантією відсутності ресайзу, new HashMap<>(12) витримує рівно 12 елементів на межі дозволеного. Проте при 13 елементах таблиця розшириться.

2. Чому в старих бібліотеках (Guava) формула виглядала як (int)(expected / 0.75f + 1.0f), а не просто (int)(expected / 0.75f)?

Відповідь: Причина криється в особливостях арифметики чисел із рухомою комою (float) та операції зведення до цілого числа ((int)):

  • У Java приведення (int) floatValue відкидає дробову частину (виконує округлення вниз, floor).
  • Наприклад, для expected = 3: $3 / 0.75 = 4.0$. Однак через похибки представлення float результат ділення може виявитися 3.9999998f.
  • Приведення (int) 3.9999998f дасть 3! У результаті tableSizeFor(3) поверне 4, threshold = 4 * 0.75 = 3. Під час вставки 3-го або 4-го елемента відбудеться ресайз. Додавання + 1.0f або використання Math.ceil() гарантує захист від неточного округлення чисел із рухомою комою.

3. Чи має сенс задавати initialCapacity для колекцій, у яких гарантовано зберігатиметься не більше 3–5 елементів?

Відповідь: Зазвичай ні. Дефолтний розмір 16 комірок вміщує до 12 елементів ($16 \times 0.75$) без жодного ресайзу. Масив на 16 посилань займає лише близько 80 байтів в оперативній пам’яті. Обчислення кастомного capacity заради економії 40 байтів створює непотрібне ускладнення коду без відчутного виграшу. Задавати initialCapacity має сенс тоді, коли очікуваний розмір колекції перевищує стандартний поріг у 12 елементів (десятки, сотні або тисячі записів).

4. Як правильно задати початкову місткість, якщо одночасно змінюється loadFactor (наприклад, передано 0.5f)?

Відповідь: Формула залишається універсальною: \(\text{capacity} = \left\lceil \frac{\text{expectedSize}}{\text{loadFactor}} \right\rceil\) Якщо очікується 100 елементів, а loadFactor = 0.5f: \(\text{capacity} = \left\lceil \frac{100}{0.5f} \right\rceil = 200\) У конструктор передається:

Map<Key, Value> map = new HashMap<>(200, 0.5f);

tableSizeFor(200) округлить місткість до 256. Поріг threshold стане $256 \times 0.5 = 128$, що дозволить гарантовано вмістити 100 елементів без розширення масиву.

🎯 Шпаргалка для інтерв’ю

  • Формула розрахунку місткості: $\text{initialCapacity} = \lceil \text{expectedSize} / 0.75 \rceil$.
  • Помилка new HashMap<>(1000): Округлюється до 1024, поріг стає 768. Ресайз відбудеться на 769-му елементі!
  • Правильне значення для 1000: capacity = 1334 (округлиться до 2048, поріг 1536 $\implies$ без ресайзів).
  • Сучасний стандарт (Java 19+): Використовуйте HashMap.newHashMap(expectedSize) або HashSet.newHashSet(expectedSize).
  • Небезпека завищення: Надлишковий capacity призводить до марнування пам’яті та різкого уповільнення ітерації ($O(\text{capacity} + N)$).
  • Маленькі колекції: При розмірі до 12 елементів дефолтного конструктора new HashMap<>() більш ніж достатньо.

Червоні прапорці (чого уникати)

  • Твердження, що new HashMap<>(1000) вміщує 1000 елементів без ресайзу (поріг буде 768).
  • Думка, що завищення capacity не несе жодних негативних наслідків (сповільнює ітерацію до $O(\text{capacity} + \text{size})$).
  • Спроби змінювати capacity після створення об’єкта (воно фіксується і змінюється лише автоматичним ресайзом).

Пов’язані теми