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
Срез — это ссылка на часть массива. В памяти это структура с тремя полями: указатель на первый элемент в слайсе, длина слайса и емкость слайса. Длина — это верхняя граница операции над индексом. Например, 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]
Копия функции используется для копирования данных между слайсами, которые могут быть двумя слайсами, указывающими на один и тот же базовый массив. Количество копируемых элементов ограничено значениями 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.
Расширение
Расширение создаст новую таблицу в два раза больше исходной.После того, как старое ведро будет перемещено в новую таблицу, старое ведро не будет удалено из старого ведра, но будет добавлена отметка об удалении.
Именно потому, что эта работа выполняется постепенно, часть данных находится в старой таблице, а часть — в новой, что влияет на логику обработки операций вставки, удаления и поиска в хеш-таблице. Старая корзина освобождается только после того, как все корзины перемещены из старой таблицы в новую.