По какому принципу увеличивается количество бакетов?

Принцип увеличения количества бакетов в хеш-структурах (например, HashMap в Java) называется рехешированием (rehashing) или изменением размера (resizing). Он происходит, когда текущее количество элементов превышает определенный порог, называемый порогом нагрузки (load factor).

Алгоритм увеличения:

1. Проверка порога: При добавлении нового элемента проверяется, не превысило ли текущее количество элементов (size) произведение текущей емкости (capacity) на порог нагрузки (load factor).

   // Пример из HashMap
   int newThreshold = (int) (newCapacity * loadFactor);
   

2. Создание нового массива бакетов: Если порог превышен, создается новый массив бакетов, обычно удвоенного размера.

   // Пример из HashMap
   Node<K,V>[] newTab = (Node<K,V>[])new Node[newCapacity];
   

3. Пересчет хешей и перемещение элементов: Все элементы из старого массива бакетов пересчитываются с использованием нового размера массива бакетов. Для каждого элемента вычисляется новый индекс бакета, и элемент помещается в соответствующий бакет нового массива.

   // Пример из HashMap (упрощенный)
   // Для каждого элемента в старом бакете:
   // int newIndex = e.hash & (newCapacity - 1);
   // Перемещение элемента в новыйTab[newIndex]
   

Таким образом, количество бакетов увеличивается нелинейно, а обычно удваивается при каждом рехешировании. Это сделано для того, чтобы сохранить приемлемую производительность операций извлечения и добавления элементов, близкую к O(1) в среднем случае. Чрезмерное количество элементов в одном бакете (вызванное коллизиями хешей) приводит к деградации производительности до O(n) в худшем случае.

Ключевые факторы:

• Начальная емкость (initial capacity): Количество бакетов при создании хеш-структуры.
• Фактор нагрузки (load factor): Максимальное отношение количества элементов к емкости, после достижения которого происходит рехеширование. Типичное значение — 0.75.