Как технически выглядит процесс рехэширования map — данные переносятся единовременно или постепенно?

Что такое рехэширование?

Рехэширование (rehashing) — это процесс увеличения размера внутреннего массива хеш-таблицы (map) и пересчета хешей для всех существующих элементов с последующим их перемещением в новые корзины. Это необходимо, когда коэффициент загрузки (load factor) превышает заданный порог, чтобы сохранить эффективность операций поиска, вставки и удаления на уровне O(1) в среднем.

Единовременное рехэширование

В большинстве стандартных реализаций (например, HashMap в Java, dict в Python) рехэширование выполняется единовременно. Когда количество элементов превышает порог (обычно 75% от текущей емкости), создается новый массив в два раза больше, и все элементы из старого массива копируются в новый с пересчетом индексов. Это приводит к временной сложности O(n), но происходит редко, поэтому амортизированная сложность вставки остается O(1).

// Псевдокод единовременного рехэширования
function insert(key, value):
    if loadFactor > threshold:
        newCapacity = capacity * 2
        newBuckets = new Array(newCapacity)
        for each entry in oldBuckets:
            newIndex = hash(entry.key) % newCapacity
            newBuckets[newIndex] = entry
        buckets = newBuckets
        capacity = newCapacity
    index = hash(key) % capacity
    buckets[index] = (key, value)

Постепенное рехэширование

Некоторые реализации (например, ConcurrentHashMap в Java или хеш-таблицы в Go) используют постепенное (incremental) рехэширование. В этом случае при превышении порога создается новый массив, но элементы переносятся не сразу, а порциями при каждой последующей операции вставки, поиска или удаления. Это позволяет избежать длительных пауз и подходит для систем, требующих предсказуемого времени отклика (real-time systems).

// Псевдокод постепенного рехэширования
function insert(key, value):
    if rehashingInProgress:
        moveNextBatch() // переносим несколько элементов
    if loadFactor > threshold:
        startRehashing() // создаем новый массив, но не копируем все сразу
    index = hash(key) % currentCapacity
    buckets[index] = (key, value)

function moveNextBatch():
    for i in 0..BATCH_SIZE:
        if oldBuckets not empty:
            entry = oldBuckets.removeNext()
            newIndex = hash(entry.key) % newCapacity
            newBuckets[newIndex] = entry

Вывод

Единовременное рехэширование проще в реализации и подходит для большинства приложений, где допустимы редкие, но короткие задержки. Постепенное рехэширование применяется в высоконагруженных или real-time системах, где важна равномерная производительность без пиковых нагрузок. Выбор стратегии зависит от требований к предсказуемости времени операций.