Анализ принципа массива, среза, карты

Go

Array

Массивы (типы значений) используются для хранения данных коллекции.Таких сценариев много.В процессе кодирования мы должны читать или сохранять данные. Конечно, в дополнение к массивам у нас также есть структуры данных, такие как срезы и карты, которые могут помочь нам хранить данные, но массивы являются их основой.

объявление и инициализация

Несколько способов инициализации массива

a := [10]int{ 1, 2, 3, 4 } // 未提供初始化值的元素为默认值 0
b := [...]int{ 1, 2 } // 由初始化列表决定数组⻓度,不能省略 "...",否则就成 slice 了。
c := [10]int{ 2:1, 5:100 } // 按序号初始化元素

Нижний индекс длины массива n должен быть положительной целочисленной константой времени компиляции (или константным выражением). Длина является частью типа, что означает, что «[10]int» и «[20]int» — это два совершенно разных типа массивов.

var a [20]int
var b [10]int
// 这里会报错,不同类型,无法比较
fmt.Println(a == b)

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

func test(x *[4]int) {
  for i := 0; i < len(x); i++ {
    println(x[i])
  }
  x[3] = 300
}

// 取地址传入
a := [10]int{ 1, 2, 3, 4 }
test(&a)

// 也可以⽤ new() 创建数组,返回数组指针。
var a = new([10]int) // 返回指针。
test(a)

Slice

d

Срез — это ссылка на часть массива. В памяти это структура с тремя полями: указатель на первый элемент в слайсе, длина слайса и емкость слайса. Длина — это верхняя граница операции над индексом. Например, i должно быть меньше, чем длина в x[i]. Емкость — это верхняя граница операции деления. Например, j в x[i:j] не может быть больше емкости.

src/pkg/runtime/runtime.h

struct Slice {
  byte* array  // actual data
  uint32 len  // number of elements
  uint32 cap  // allocated number of elements
};

Модификации слайсов — это модификации базового массива.

func main() {
	x := [...]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	s := x[:6]
	s = append(s, 10)
	s[0] = 100
	fmt.Println(x)
	fmt.Println(s)
}

выход

[100 1 2 3 4 5 10 7 8 9]
[100 1 2 3 4 5 10]

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

func main() {
	x := [...]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	s := x[:]
	s = append(s, 10)
	s[0] = 100
	fmt.Println(x)
	fmt.Println(s)
}

выход

[0 1 2 3 4 5 6 7 8 9]
[100 1 2 3 4 5 6 7 8 9 10]

d

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

func main() {
  s1 := []int{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
  s2 := make([]int, 3, 20)
  var n int
  n = copy(s2, s1) // n = 3。不同数组上拷⻉。s2.len == 3,只能拷 3 个元素。
  fmt.Println(n, s2, len(s2), cap(s2)) // [0 1 2], len:3, cap:20
  s3 := s1[4:6] // s3 == [4 5]。s3 和 s1 指向同⼀个底层数组。
  n = copy(s3, s1[1:5]) // n = 2。同⼀数组上拷⻉,且存在重叠区域。
  fmt.Println(n, s1, s3) // [0 1 2 3 1 2 6 7 8 9] [1 2]
}

выход

3 [0 1 2] 3 20
2 [0 1 2 3 1 2 6 7 8 9] [1 2]

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

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

Правила расширения среза

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

  • Если новый размер более чем в 2 раза превышает текущий размер, размер увеличивается до нового размера.
  • В противном случае зациклить следующие операции: если текущий размер меньше 1024, каждый раз увеличивать в 2 раза, иначе каждый раз увеличивать на 1/4 от текущего размера. пока увеличенный размер не превысит или не сравняется с новым размером.

сделать и новый

В Go есть две функции создания структур данных: new и make. Основное отличие состоит в том, что new(T) возвращает *T, а возвращаемый указатель может быть неявно разыменован. А make(T, args) возвращает обычный T. Обычно внутри T есть неявные указатели. Одним словом, new возвращает указатель на обнуленную память, а make возвращает сложную структуру.

Суммировать

  • Когда несколько слайсов указывают на один и тот же базовый массив, изменение одного из слайсов может повлиять на значения других слайсов;
  • Когда срез передается в качестве параметра, он более эффективен, чем массив, поскольку структура среза меньше;
  • Когда срез расширяется, могут произойти изменения в базовом массиве и копиях памяти;
  • Поскольку срез ссылается на массив, это может привести к тому, что пространство массива не будет gc, особенно когда пространство массива велико, а содержимое ссылки на срез мало;

Map

Карты в Go реализованы в виде хеш-таблиц под капотом. В Golang используется реализация HashTable, а для разрешения конфликтов используется метод адресации по цепочке. То есть используйте массив + связанный список для реализации карты.

Карты хранят неупорядоченный набор пар ключ-значение.

Не все ключи можно использовать в качестве типа ключа карты, в качестве типа ключа можно использовать только те типы, которые можно сравнивать. Так, например, срез, функция, тип карты не могут использоваться в качестве ключевого типа карты.

Операция поиска по карте намного быстрее, чем линейный поиск, но примерно в 100 раз медленнее, чем доступ к массивам и срезам с порядковыми номерами.

То, что возвращает карта [ключ], является просто «временной копией значения», и бессмысленно изменять свое собственное состояние, только переназначать значение или использовать указатель для изменения памяти, на которую ссылаются.

В каждом сегменте хранится максимум 8 пар "ключ-значение". Если их больше 8, новый сегмент будет применен и связан с предыдущим сегментом.

Обратите внимание, что деталью является порядок размещения ключей/значений в Bucket.Это чтобы совместить ключи и значения вместе.Почему бы не поставить ключи и соответствующие значения вместе? Если вы сделаете это, структура хранения станет ключ1/значение1/ключ2/значение2... Представьте, что если это такая карта[int64]int8, учитывая выравнивание байтов, это будет тратить много места для хранения. Надо сказать, что по упомянутым выше мелким деталям видно, что Go хорошо продуман в дизайне.

Структуры данных и управление памятью

Определение hashmap находится в src/runtime/hashmap.go, Во-первых, давайте посмотрим на определения hashmap и Bucket:

type hmap struct {
  count     int    // 元素的个数
  flags     uint8  // 状态标志
  B         uint8  // 可以最多容纳 6.5 * 2 ^ B 个元素,6.5为装载因子
  noverflow uint16 // 溢出的个数
  hash0     uint32 // 哈希种子

  buckets    unsafe.Pointer // 桶的地址
  oldbuckets unsafe.Pointer // 旧桶的地址,用于扩容
  nevacuate  uintptr        // 搬迁进度,小于nevacuate的已经搬迁
  overflow *[2]*[]*bmap 
}

Среди них переполнение — указатель на массив с 2 элементами, тип массива — указатель, указывающий на слайс, а элемент слайса — адрес ведра (bmap), эти ведра — переполненные ведра; почему их два? Поскольку карта Go будет расширять емкость при слишком большом количестве конфликтов хэшей, чтобы не полностью перемещать данные, используется инкрементное перемещение. [0] указывает текущий используемый набор сегментов переполнения, а [1] сохраняет старый, когда происходит расширение Набор сегментов переполнения, смысл переполнения состоит в том, чтобы не допустить, чтобы сегменты переполнения были gc.

Расширение

Расширение создаст новую таблицу в два раза больше исходной.После того, как старое ведро будет перемещено в новую таблицу, старое ведро не будет удалено из старого ведра, но будет добавлена ​​отметка об удалении.

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

Базовая реализация карты Голанга