Структуры данных

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

Базовые структуры данных

slice Срез

Срез — наиболее часто используемая структура данных в Go, представляющая абстракцию и обёртку массива. Основные характеристики:

• Динамический размер: длина среза может динамически увеличиваться
• Семантика ссылок: при передаче среза копируется только структура, а не базовый массив
• Механизм расширения: автоматически расширяется при недостаточной ёмкости

Срез в runtime представляется структурой slice, содержащей указатель на базовый массив, длину и ёмкость.

string Строка

Строка — один из базовых типов данных в Go. Основные характеристики:

• Неизменяемость: после создания строку нельзя изменить
• Кодировка UTF-8: обычно представляет текст в кодировке UTF-8
• Безопасность нулевого значения: нулевое значение строки — пустая строка "", а не nil

Строка в runtime представляется структурой stringStruct, содержащей указатель на байтовый массив и длину.

Структуры данных-контейнеры

map Отображение

map — встроенный контейнер пар ключ-значение в Go, реализованный на основе хэш-таблицы. Основные характеристики:

• Реализация хэш-таблицы: быстрое позиционирование элементов через хэш-функцию
• Автоматическое расширение: автоматически расширяется при превышении коэффициента загрузки
• Не потокобезопасен: для конкурентного чтения/записи требуется дополнительный механизм синхронизации

map в runtime представляется структурой hmap, содержащей массив корзин, хэш-семя, счётчик элементов и т.д.

syncmap Потокобезопасное отображение

sync.Map — потокобезопасное отображение из стандартной библиотеки, подходящее для сценариев с большим количеством чтений и малым количеством записей. Основные характеристики:

• Разделение чтения/записи: использование двух map read и dirty для разделения операций
• Атомарные операции: read map использует атомарные операции без блокировки
• Прогрессивная миграция: при достижении порогового значения счёта miss dirty становится read

sync.Map через компромисс пространства и времени обеспечивает лучшую производительность в определённых сценариях по сравнению с map + mutex.

Структуры данных для конкурентности

channel Канал

channel — типичный представитель идеи CSP в Go, используемый для коммуникации между горутинами. Основные характеристики:

• Коммуникация горутин: передача данных между горутинами через channel
• Механизм синхронизации: канал без буфера может использоваться для синхронизации горутин
• Очередь с блокировкой:底层 реализация — кольцевая очередь с блокировкой

channel в runtime представляется структурой hchan, содержащей кольцевой буфер, очередь ожидания и т.д.

select Мультиплексирование

select может одновременно отслеживать состояние нескольких channel, реализуя мультиплексирование. Основные характеристики:

• Неблокирующий: неблокирующая проверка доступности нескольких channel
• Случайный выбор: при доступности нескольких channel случайно выбирается один для выполнения
• Контроль таймаута: реализация механизма таймаута с помощью time.After

select в runtime представляется структурой scase для каждого ветвления, проверяющей состояние channel через механизм опроса.

Рекомендации по изучению

Рекомендуется изучать в следующем порядке:

1. Сначала изучите slice Срез и string Строка, чтобы понять базовые структуры данных
2. Затем изучите map Отображение, чтобы понять реализацию хэш-таблицы
3. После этого изучите channel Канал, чтобы понять механизм коммуникации горутин
4. Далее изучите select Мультиплексирование, чтобы освоить техники мультиплексирования
5. Наконец изучите syncmap Потокобезопасное отображение, чтобы понять реализацию потокобезопасности