Golang: Как мапа определяет их какого бакета читать в процессе эвакуации?

В Go мапа использует флаги и метаданные, чтобы отслеживать, из какого бакета (старого или нового) нужно читать данные во время процесса эвакуации (rehashing). Это позволяет мапе корректно работать даже в переходный период, когда часть элементов уже перемещена в новые бакеты, а часть еще осталась в старых.

---

1. Структура мапы во время эвакуации

Во время эвакуации мапа содержит:

• Старые бакеты: Бакеты, которые использовались до расширения.
• Новые бакеты: Бакеты, выделенные после расширения.
• Метаданные: Флаги и указатели, которые помогают определить, где находится элемент.

---

2. Как мапа определяет, откуда читать?

a) Флаг эвакуации:

• Мапа хранит флаг, который указывает, что она находится в состоянии эвакуации.
• Этот флаг активируется, когда начинается процесс расширения.

b) Хэш-функция:

• При поиске элемента мапа вычисляет хэш ключа.
• На основе хэша определяется, в каком бакете должен находиться элемент.

c) Проверка бакета:

• Если мапа находится в состоянии эвакуации, она проверяет, был ли элемент уже перемещен в новый бакет.
  • Если элемент уже перемещен, мапа читает его из нового бакета.
  • Если элемент еще не перемещен, мапа читает его из старого бакета.

d) Постепенная эвакуация:

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

---

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

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

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

Итог

• Во время эвакуации мапа использует флаги и метаданные, чтобы определить, из какого бакета (старого или нового) нужно читать данные.
• Это позволяет мапе корректно работать даже в переходный период, когда часть элементов уже перемещена, а часть еще осталась в старых бакетах.
• Процесс эвакуации выполняется постепенно, что минимизирует задержки и нагрузку на память.