-
【go语言】slice和map
1.数组与动态数组
1.1定长数组
语法：
和c语言相同，Go语言也提供了数组类型的数据结构，数组是具有相同唯一类型的一组已编号且长度固定的数据项序列，这种类型可以是任意的原始类型例如整型、字符串或者自定义类型。
var myArray[size] type
func arr_test() { type people struct { id int age int name string } var myArray1 [10]int var myArray2 [10]float64 var myArray3 [5]people myArray1[1] = 4 myArray2[1] = 16.66 myArray3[1].age = 18 myArray3[1].id = 1111 myArray3[1].name = "zhangsan" fmt.Printf("myArray1[1]:%d,myArray2[1]:%f\n", myArray1[1], myArray2[1]) fmt.Printf("id:%d,age:%d,name:%s\n", myArray3[1].id, myArray3[1].age, myArray3[1].name) } func main() { arr_test() }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
数组还有其他定义方式
var arr = [10]int{1, 2, 3, 4, 5} var ptr_arr = &arr //数组指针 fmt.Printf("ptr_arr:%p,arr[2]:%d\n", ptr_arr, (*ptr_arr)[2]) for index, value := range arr { //遍历数组 fmt.Println("index= ", index, "value= ", value) }- 1
- 2
- 3
- 4
- 5
- 6
数组传参，传递的是数组的拷贝。
1.2slice
slice本质上是一种动态数组，属于是引用类型的变量。
切片高效操作的要点是要降低内存分配的次数，尽量保证append操作（在后续的插入和删除操作中都涉及到这个函数）不会超出cap的容量，降低触发内存分配的次数和每次分配内存大小。
slice的底层
type SliceHeader struct { Data uintptr // 指向底层的的数组指针 Len int // 切片长度 Cap int // 切片最大长度 }- 1
- 2
- 3
- 4
- 5
-
内置的len函数返回切片中有效元素的长度，内置的cap函数返回切片容量大小，容量必须大于或等于切片的长度。
-
如果切片的长度和容量不发生变化时，发生拷贝时，只是拷贝了指向底层的数组指针，并不会复制底层的数据结构。属于是浅拷贝。
切片定义
var identifier []type //比如 var myarray []int- 1
- 2
- 3
使用make()函数来创建切片
var slice1 []type=make([]type,len,cap) //比如 var arr_int []int=make([]int,10,20) //切片存放的类型是int,长度是10，容量是20- 1
- 2
- 3
- 4
len()和cap()函数
切片是可索引的，并且可以由 len() 方法获取长度。
切片提供了计算容量的方法 cap() 可以测量切片最长可以达到多少。
func slice_age() { var numbers = make([]int, 3, 5) fmt.Printf("len=%d,cap=%d,slice=%v", len(numbers), cap(numbers), numbers) } func main() { slice_age() }- 1
- 2
- 3
- 4
- 5
- 6
- 7
1.2.1切片截取
func arr_trunc() { /* 创建切片 */ numbers := []int{0,1,2,3,4,5,6,7,8} printSlice(numbers) /* 打印原始切片 */ fmt.Println("numbers ==", numbers) /* 打印子切片从索引1(包含) 到索引4(不包含)*/ fmt.Println("numbers[1:4] ==", numbers[1:4]) /* 默认下限为 0*/ fmt.Println("numbers[:3] ==", numbers[:3]) /* 默认上限为 len(s)*/ fmt.Println("numbers[4:] ==", numbers[4:]) numbers1 := make([]int,0,5) printSlice(numbers1) /* 打印子切片从索引 0(包含) 到索引 2(不包含) */ number2 := numbers[:2] printSlice(number2) /* 打印子切片从索引 2(包含) 到索引 5(不包含) */ number3 := numbers[2:5] printSlice(number3) } func printSlice(x []int){ fmt.Printf("len=%d cap=%d slice=%v\n",len(x),cap(x),x) } func main() { arr_trunc() }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
1.2.2添加元素
在切片尾部插入
var a []int a = append(a, 1) // 追加1个元素 a = append(a, 1, 2, 3) // 追加多个元素, 手写解包方式 a = append(a, []int{1,2,3}...) // 追加一个切片, 切片需要解包- 1
- 2
- 3
- 4
func append_arr() { var a []int b := []int{10, 11, 12, 13, 14, 15} a = append(a, 1) a = append(a, 1, 2, 3, 4) a = append(a, []int{5, 6, 7, 8, 9}...) a = append(a, b...) fmt.Printf("len:%d,cap:%d,a:%v\n", len(a), cap(a), a) } func main() { append_arr() }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
输出：
len:16,cap:24,a:[1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]
在切片的头部插入
var a = []int{1,2,3} a = append([]int{0}, a...) // 在开头位置添加1个元素 a = append([]int{-3,-2,-1}, a...) // 在开头添加1个切片- 1
- 2
- 3
func append_arr() { a := []int{1, 2, 3} b := []int{10, 11, 12, 13, 14, 15} a = append([]int{0}, a...) a = append([]int{-1, -2, -3}, a...) a = append(b, a...) fmt.Printf("len:%d,cap:%d,a:%v\n", len(a), cap(a), a) }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
输出：
len:13,cap:14,a:[10 11 12 13 14 15 -1 -2 -3 0 1 2 3]
在随机位置插入
var a []int a = append(a[:i], append([]int{x}, a[i:]...)...) // 在第i个位置插入x a = append(a[:i], append([]int{1,2,3}, a[i:]...)...) // 在第i个位置插入切片- 1
- 2
- 3
func append_arr() { a := []int{1, 2, 20, 21, 22} b := []int{10, 11, 12, 13, 14, 15} a = append(a[:2], append([]int{3}, a[2:]...)...) a = append(a[:3], append(b, a[3:]...)...) fmt.Printf("len=%d cap=%d slice=%v\n", len(a), cap(a), a) }- 1
- 2
- 3
- 4
- 5
- 6
- 7
第二个append会生成一个临时变量，将a[ i: ]中的内容拷贝到临时变量中，然后再将临时变量追加到a[ : i ]中。
输出：
len=12 cap=20 slice=[1 2 3 10 11 12 13 14 15 20 21 22]
和copy套用
a = append(a, 0) // 切片扩展1个空间 copy(a[i+1:], a[i:]) // a[i:]向后移动1个位置 a[i] = x // 设置新添加的元素- 1
- 2
- 3
copy(a[4:], a[3:]) a[3] = 5 fmt.Printf("len=%d cap=%d slice=%v\n", len(a), cap(a), a)- 1
- 2
- 3
输出：
len=12 cap=20 slice=[1 2 3 5 10 11 12 13 14 15 20 21]
1.2.3删除元素
删除头位置元素
a = []int{1, 2, 3, ...} a = a[1:] // 删除开头1个元素 a = a[N:] // 删除开头N个元素- 1
- 2
- 3
func del_arr() { a := []int{1, 2, 3, 4, 5} a = append(a[1:]) a = append(a[1:]) fmt.Printf("len=%d,cap=%d,a=%v\n", len(a), cap(a), a) }- 1
- 2
- 3
- 4
- 5
- 6
从中间为删除
a = append(a[:i], a[i+1], ...) a = append(a[:i], a[i+N:], ...) //删除N个元素- 1
- 2
func del_arr() { a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} a = append(a[:3], a[4:]...) a = append(a[:3], a[6:]...) fmt.Printf("len=%d,cap=%d,a=%v\n", len(a), cap(a), a) }- 1
- 2
- 3
- 4
- 5
- 6
输出：
len=7,cap=11,a=[1 2 3 8 9 10 11]
尾部删除
a = a[:len(a)-1] // 删除尾部1个元素 a = a[:len(a)-N] // 删除尾部N个元素- 1
- 2
func del_arr() { a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} a = a[:len(a)-1] a = a[:len(a)-3] fmt.Printf("len=%d,cap=%d,a=%v\n", len(a), cap(a), a) }- 1
- 2
- 3
- 4
- 5
- 6
输出：
len=7,cap=11,a=[1 2 3 4 5 6 7]
2.map
go语言的map本质上是一个hash表。
2.1基本用法
声明
func map_test() { //第一种声明 //test1是一个map，Keys是string,value是int var test1 map[string]int //在使用map前，需要先make，make的作用就是给map分配数据空间 test1 = make(map[string]int, 10) test1["one"] = 1 test1["two"] = 2 test1["three"] = 3 fmt.Println(test1) //map[two:golang three:java one:php] //第二种声明 test2 := make(map[string]string) test2["one"] = "php" test2["two"] = "golang" test2["three"] = "java" fmt.Println(test2) //map[one:php two:golang three:java] //第三种声明 test3 := map[string]int{ "one": 1, "two": 2, "three": 3, } fmt.Println(test3) //map[one:php two:golang three:java] }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
输出：
map[one:1 three:3 two:2]
map[one:php three:java two:golang]
map[one:1 three:3 two:2]map嵌套
func mul_map_test() { language := make(map[string]map[string]string) language["php"] = make(map[string]string, 2) language["php"]["id"] = "1" language["php"]["desc"] = "php是世界上最美的语言" language["golang"] = make(map[string]string, 2) language["golang"]["id"] = "2" language["golang"]["desc"] = "golang抗并发非常good" fmt.Println(language) }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
输出：
map[golang:map[desc:golang抗并发非常good id:2] php:map[desc:php是世界上最美的语言 id:1]]
增删查改
func mul_map_test() { language := make(map[string]map[string]string) language["php"] = make(map[string]string, 2) language["php"]["id"] = "1" language["php"]["desc"] = "php是世界上最美的语言" language["golang"] = make(map[string]string, 2) language["golang"]["id"] = "2" language["golang"]["desc"] = "golang抗并发非常good" //增删查改 value, key := language["php"] //查找是否有php这个子元素value是该值，如果没有就是nil;key是查找的结果，找到就是true,否则就是false if key { fmt.Printf("%v\n", value) } else { fmt.Printf("no") } language["php"]["id"] = "3" //修改了php子元素的id值 language["php"]["nickname"] = "啪啪啪" //增加php元素里的nickname值 fmt.Printf("before del language:%v\n", language) delete(language, "php") //删除了php子元素 fmt.Printf("afterr del language:%v\n", language) }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
输出：
map[desc:php是世界上最美的语言 id:1]
before del language:map[golang:map[desc:golang抗并发非常good id:2] php:map[desc:php是世界上最美的语言 id:3 nickname:啪啪啪]]
afterr del language:map[golang:map[desc:golang抗并发非常good id:2]]2.底层原理
map的数据结构在源码结构中的关键字段如下，在
src/runtime/map.go中type hmap struct { count int // 元素的个数 B uint8 // buckets 数组的长度就是 2^B 个 ，也就是桶的数量 overflow uint16 // 溢出桶的数量 buckets unsafe.Pointer // 2^B个桶对应的数组指针 oldbuckets unsafe.Pointer // 发生扩容时，记录扩容前的buckets数组指针 extra *mapextra //用于保存溢出桶的地址，是一个链表 } type mapextra struct { overflow *[]*bmap //数组指针，数组元素类型为*bmap oldoverflow *[]*bmap nextOverflow *bmap } //在编译期间会产生新的结构体 type bmap struct { tophash [8]uint8 //存储哈希值的高8位 data byte[1] //key value数据:key/key/key/.../value/value/value... overflow *bmap //溢出bucket的地址 } type Map struct { Key *Type // Key type Elem *Type // Val (elem) type Bucket *Type // 哈希桶 Hmap *Type // 底层使用的哈希表元信息 Hiter *Type // 用于遍历哈希表的迭代器 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
在go的map实现中，它的底层结构体是hmap，hmap里维护着若干个bucket数组 (即桶数组)。
Bucket数组中每个元素都是bmap结构，也即每个bucket（桶）都是bmap结构。 每个桶中保存了8个kv对，如果8个满了，又来了一个key落在了这个桶里，会使用overflow连接下一个桶(溢出桶)。
1.获取数据
假设当前B=4,那么桶的数量是2^4=16个，从map中获取k4的value。
获取数据的步骤
- 计算k4的hash值，根据hash值进行下面的步骤
- 低B位确定桶的序号，此时B为4，所以取k4对应哈希值的后4位，也就是0101，0101用十进制表示为5，所以在5号桶）
- 根据k4对应的hash值高8位快速确定是在这个桶的哪个位置
- 对比key完整的hash是否匹配，如果匹配则获取对应value
- 如果都没有找到，就去连接的下一个溢出桶中找
为什么bmp中会维护一个tophash [8]uint8数组保存hash值的高8位？
可以理解为go语言提高效率的一种缓存方式，如果高8位都不满足，那么说明key就一定不存在。
2.插入数据的步骤
- 通过Key的hash值后B位，确定是哪一个桶
- 遍历当前桶，通过key的高8位和hash值，防止key重复，然后找到第一个可以插入的位置，即空位置处存储数据。
- 如果当前桶元素已满，会通过overflow链接创建一个新的桶，来存储数据。
解决哈希冲突：冲突的解决手段是采用线性探测法：在桶 中，从前往后找到第一个空位进行插入。如果8个kv满了，那么当前桶就会连接到下一个溢出桶（bmap）。
扩容
map有扩容有两种，一种是等量扩容，另一种是2倍扩容
相同容量扩容
由于map中不断的put和delete key，桶中可能会出现很多断断续续的空位，这些空位会导致连接的bmap溢出桶很长，导致扫描时间边长。这种扩容实际上是一种整理，把后置位的数据整理到前面。这种情况下，元素会发生重排，但不会换桶。
2倍容量扩容
这种2倍扩容是由于当前桶数组不够用了，发生这种扩容时，元素会重排，可能会发生桶迁移。
由于扩容后，桶的数量发生改变。对应的B值发生改变，变为了2B 。决定key存储的桶位置也会随之发生改变，所以元素会发生重排。
发生扩容的条件
装载因子：
loadFactor:=count / (2^B) 即 装载因子 = map中元素的个数 / map中当前桶的个数
通过计算公式我们可以得知，装载因子是指当前map中，每个桶中的平均元素个数。
扩容条件1：装载因子> 6.5（源码定义）
当平均每个桶中的数据超过了6.5，说明容量快要不足了，所以要扩容。
扩容条件2：溢出桶的数量过多
当 B < 15 时，如果overflow的bucket数量超过 2^B。
当 B >= 15 时，overflow的bucket数量超过 2^15。
简单来讲，新加入key的hash值后B位都一样，使得个别桶一直在插入新数据，进而导致它的溢出桶链条越来越长。如此一来，当map在操作数据时，扫描速度就会变得很慢。及时的扩容，可以对这些元素进行重排，使元素在桶的位置更平均一些。
扩容细节
- hmap当中有一个oldbuckets(指针)，扩容时，会指向原数据。
- 每次对map进行删改操作时，会触发从oldbuckets中迁移数据到bucket中的操作。(并不是一次迁移完成，而是分多次迁移完成)
- 在扩容没有完全迁移完成之前，每次get或者put遍历数据时，都会先遍历oldbuckets，然后再遍历buckets。
注意事项
map是线程不安全的
- 在同一时间点，两个 goroutine 对同一个map进行读写操作是不安全的。
func go_map() { r := make(map[string]int) go func() { for j := 0; j < 15; j++ { r[fmt.Sprintf("map_%d", j)] = j } }() go func() { for j := 0; j < 15; j++ { r[fmt.Sprintf("map_%d", j)] = j } }() fmt.Printf("map:%v", r) } func main() { go_map() }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 在工作中，当我们涉及到对一个map进行并发读写时，一般采用的做法是采用golang中自带的mutex锁
//封装一个线程安全的锁 type safe_map struct { sync.RWMutex m map[string]int } func go_map() { r := safe_map{m: make(map[string]int)} go func() { for j := 0; j < 15; j++ { r.Lock() r.m[fmt.Sprintf("map_%d", j)] = j r.Unlock() } }() go func() { for j := 0; j < 15; j++ { r.Lock() r.m[fmt.Sprintf("map_%d", j)] = j r.Unlock() } }() fmt.Printf("map:%v", r) } func main() { go_map() }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
-
相关阅读:
9.0 堆体系结构概述之GC
【已解决】AttributeError: module ‘numpy‘ has no attribute ‘int‘.
场馆“智慧化”是否有必要？
二、反应式集成-spring
随机过程理论知识（三）
代码比较模板
互联网摸鱼日报（2022-10-28）
Invalid access token: Invalid header string: ‘utf-8‘ codec can‘t decode byte
9年前，我的第一份实习工作
pandas 100题
- 原文地址：https://blog.csdn.net/qq_53893431/article/details/127562326
