Что такое Bucket в HashMap — пример ответа на собеседовании Android Разработчик

Что такое Bucket в HashMap

«Что такое Bucket в HashMap» — вопрос из категории Алгоритмы и структуры данных, который задают на 23% собеседований Android Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Тип вопроса: Алгоритмы и структуры данных Вероятность: 23% Категория: Android Разработчик

Ответ

Bucket в HashMap — это элемент внутреннего массива (таблицы), который хранит узлы (ноды) с данными. При коллизии (одинаковый hashCode) элементы добавляются в один bucket как связанный список (или дерево, если элементов много).

Пример:

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 1);  // hash("key1") → индекс bucket
map.put("key2", 2);  // если hash совпадает, добавляется в тот же bucket

Особенности:

По умолчанию bucket’ы — это Node<K,V>[] table.
При достижении TREEIFY_THRESHOLD (8) список преобразуется в красно-черное дерево для оптимизации поиска.
Размер bucket’ов влияет на производительность: меньше коллизий → быстрее доступ.