Slice, map глубже

Давайте углубимся в темы slice и map в Go, чтобы лучше понять их работу, внутренние механизмы и применимость в реальных проектах.

Углубляемся в Slice

Внутреннее устройство Slice

Под капотом slice хранит три значения:

  1. Указатель на базовый массив: Срез не хранит данные напрямую, а лишь содержит указатель на базовый массив, который фактически хранит элементы.
  2. Длина (len): Количество элементов в срезе.
  3. Ёмкость (cap): Количество элементов, которое может хранить базовый массив, начиная с первого элемента среза. Ёмкость всегда больше или равна длине.
struct {
	array *[]T
	length int
	capacity int
}

Пример:

arr := [5]int{1, 2, 3, 4, 5}
slice := arr[1:4] // slice: [2, 3, 4], len(slice) = 3, cap(slice) = 4

В этом примере срез начинается с индекса 1 массива arr, поэтому он может "видеть" оставшиеся 4 элемента массива. Однако длина среза — это только 3 элемента: [2, 3, 4].

Расширение Slice

Когда вы добавляете элементы в срез с помощью функции append, Go автоматически создаёт новый базовый массив, если текущая ёмкость недостаточна. Этот новый массив будет вдвое больше старого, что позволяет улучшить производительность при многократном добавлении элементов.

Пример:

slice := []int{1, 2, 3}
slice = append(slice, 4, 5, 6)
fmt.Println(slice) // [1, 2, 3, 4, 5, 6]

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

Работа со срезами

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

Пример:

arr := [5]int{1, 2, 3, 4, 5}
slice1 := arr[1:4] // slice1: [2, 3, 4]
slice2 := arr[2:5] // slice2: [3, 4, 5]
slice1[1] = 10     // Изменяем slice1
fmt.Println(arr)    // [1, 2, 10, 4, 5] - изменился массив
fmt.Println(slice2) // [10, 4, 5] - изменился и slice2

Чтобы избежать таких эффектов, можно копировать данные в новый срез с помощью функции copy.

Zero value Slice

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

var slice []int
fmt.Println(slice == nil) // true
slice = append(slice, 1)
fmt.Println(slice) // [1]

Особенность slice при передаче

Когда вы будете активно работать со слайсами, может возникнуть ситуация, которую можно назвать "Заблуждение указателей слайса" (условное название). Часто разработчики ошибочно полагают, что слайсы ведут себя как указатели, и любые изменения, такие как добавление элементов через append, будут видны после возврата из функции. Однако, это не совсем так.

Рассмотрим пример:

func main() {
    aqua := make([]int, 0, 2)
    appendSlice(aqua)
    fmt.Println(aqua) // Ожидаем [1], но будет []
}

func appendSlice(aqua []int) {
    aqua = append(aqua, 1)
}

В этом коде мы создаём слайс aqua и передаём его в функцию appendSlice, которая должна была добавить в него элемент. Однако, когда мы печатаем aqua в main, результат остаётся пустым.

Почему это происходит?

Хотя слайс и содержит указатель на базовый массив, важно помнить, что сам слайс (структура, содержащая указатель, длину и ёмкость) передаётся в функцию по значению. Это означает, что в функции appendSlice мы работаем с копией слайса. Изменения, сделанные в этой копии, не отражаются на оригинальной переменной aqua в main.

В данном случае функция append может вернуть новый слайс, если при добавлении элементов ёмкости исходного базового массива не хватает. Поскольку в функции используется копия слайса, эти изменения не затрагивают исходный слайс в main.

Как это исправить?

Чтобы изменения в слайсе были видны вне функции, нужно передать слайс по указателю. Это позволит функции работать с оригинальной структурой слайса:

func main() {
    aqua := make([]int, 0, 2)
    appendSlice(&aqua)
    fmt.Println(aqua) // Теперь будет [1]
}

func appendSlice(aqua *[]int) {
    *aqua = append(*aqua, 1)
}

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

Хотя слайс содержит указатель на базовый массив, сама структура слайса передаётся по значению. Чтобы изменения были видны вне функции, необходимо передавать слайс по указателю.


Углубляемся в Map

Внутреннее устройство Map

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

Эффективность карты основана на том, что поиск по хеш-таблице обычно выполняется за O(1) — константное время, хотя в случае коллизий время может увеличиться (Примерно будет O(N)).

type hmap struct {
  // ...more code
  count       int
  B           uint 8
  noverflow   uint 16
  hash0       uint 32
  buckets     unsafe.Pointer
  oldbuckets  unsafe.Pointer
}

Инициализация карты

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

Пример:

m := make(map[string]int, 100) // Создаём карту с начальной ёмкостью на 100 элементов

Удаление элементов из карты

Для удаления элементов используется функция delete. Если ключ отсутствует в карте, то ничего страшного не произойдёт — ошибка не будет вызвана.

delete(m, "apple") // Удалим элемент с ключом "apple"

Обход элементов карты

При использовании цикла for range порядок обхода элементов карты не гарантируется. Он будет случайным, и при каждом запуске программы может быть разным.

m := map[string]int{"apple": 1, "banana": 2}
for key, value := range m {
    fmt.Println(key, value)
}

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

Пример сортировки ключей карты:

keys := make([]string, 0, len(m))
for key := range m {
    keys = append(keys, key)
}
sort.Strings(keys) // Сортируем ключи
for _, key := range keys {
    fmt.Println(key, m[key])
}

Карты как нулевые значения

Карта, как и срезы, может иметь значение nil. Это полезно для обработки отсутствия значений, но попытка добавления элементов в nil map приведёт к панике.

var m map[string]int
fmt.Println(m == nil) // true
// m["apple"] = 5 // Это вызовет панику!

Чтобы избежать этого, всегда нужно инициализировать карту перед использованием.

Ограничения ключей и значений

Ключи в картах должны быть сравнимыми типами, то есть типами, для которых возможны операции сравнения (==, !=). Это означает, что срезы и функции не могут быть ключами карты, так как они не сравнимы. Однако строки, числа, структуры и даже интерфейсы могут быть ключами.

Работа с мапами (карта) в Go может быть весьма удобной, однако существуют несколько особенностей, на которые стоит обратить внимание, чтобы избежать распространённых ошибок. В этой статье мы рассмотрим основные аспекты работы с мапами и их эвакуацию.

Эвакуация данных в мапах

Эвакуация - это процесс когда map переносит свои значения из одной области памяти в другую. Это происходит из-за того что число значений в каждом отдельном bucket максимально равно 8.

В тот момент времени, когда среднее количество значений в bucket составляет 6.5, go понимает, что размер map не удовлетворяет необходимому. Начинается процесс расширения map.

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

Заключение

Работа с мапами в Go предоставляет множество возможностей для удобного хранения и извлечения данных. Однако, как и с любой другой структурой данных, важно знать основные правила и избежать распространённых ошибок. Зная о таких моментах, как эвакуация данных, проверка наличия ключей и правильная инициализация мап, вы сможете эффективно использовать эту мощную структуру данных в своих проектах.


Дополнительные материалы