Как в map происходит увеличение (rehash)?

В C# при увеличении размера словаря (Dictionary<TKey, TValue>) происходит операция rehash — перераспределение элементов по новой, большей внутренней структуре.

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

Это необходимо, чтобы сохранить эффективность операций поиска, вставки и удаления.

Примерно процесс выглядит так:

1. Создаётся новый массив большего размера.
2. Для каждого элемента из старого массива вычисляется новый индекс с учётом нового размера.
3. Элементы копируются в новый массив по новым индексам.

Это затратная операция по времени, поэтому её стараются минимизировать, заранее задавая подходящий начальный размер словаря, если известен ожидаемый объём данных.