Реиндексация (rehashing) и эвакуация данных в мапах Golang

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

---

1. Инкрементальный rehashing

Go не создает вторую мапу и не копирует все элементы сразу. Вместо этого:

• Мапа продолжает использовать старые бакеты, но постепенно перемещает элементы в новые бакеты.
• Этот процесс выполняется по мере обращения к мапе (например, при вставке, поиске или удалении элементов).

---

2. Как это работает?

1. Инициализация расширения:
   • Когда мапа заполняется, Go выделяет память для новых бакетов (обычно в 2 раза больше, чем старые).
   • Мапа переходит в состояние «эвакуации».
2. Постепенная эвакуация:
   • При каждой операции с мапой (вставка, поиск, удаление) Go перемещает несколько элементов из старых бакетов в новые.
   • Например, при вставке нового элемента Go может переместить 1-2 элемента из старых бакетов.
3. Завершение эвакуации:
   • Когда все элементы перемещены, старые бакеты освобождаются.
   • Мапа полностью переходит на использование новых бакетов.

---

3. Пример процесса

Предположим, у нас есть мапа с 8 бакетами, и она начинает расширяться до 16 бакетов.

1. Начальное состояние:
   • Количество бакетов: 8.
   • Элементы распределены по старым бакетам.
2. Расширение:
   • Go выделяет память для 16 новых бакетов.
   • Мапа переходит в состояние «эвакуации».
3. Эвакуация:
   • При каждой операции с мапой Go перемещает несколько элементов из старых бакетов в новые.
   • Например:
     • При вставке нового элемента Go перемещает 1 элемент из старого бакета.
     • При поиске элемента Go может переместить 2 элемента.
4. Завершение:
   • Когда все элементы перемещены, старые бакеты освобождаются.
   • Мапа теперь использует 16 бакетов.

---

4. Преимущества инкрементального подхода

• Минимизация задержек: Эвакуация выполняется постепенно, что позволяет избежать резкого увеличения времени выполнения операций.
• Экономия памяти: Go не создает полную копию мапы, что уменьшает нагрузку на память.
• Параллельная работа: Мапа остается доступной для операций даже во время эвакуации.

Итог

• Во время эвакуации данных Go не создает вторую мапу. Вместо этого он постепенно перемещает элементы из старых бакетов в новые.
• Это позволяет минимизировать задержки и нагрузку на память.
• Мапа остается доступной для операций даже во время эвакуации.