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()
}

数组还有其他定义方式

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.2slice

slice本质上是一种动态数组，属于是引用类型的变量。

切片高效操作的要点是要降低内存分配的次数，尽量保证append操作（在后续的插入和删除操作中都涉及到这个函数）不会超出cap的容量，降低触发内存分配的次数和每次分配内存大小。

slice的底层

type SliceHeader struct {
    Data uintptr   // 指向底层的的数组指针
    Len  int	   // 切片长度
    Cap  int	   // 切片最大长度
}

• 内置的len函数返回切片中有效元素的长度，内置的cap函数返回切片容量大小，容量必须大于或等于切片的长度。

• 如果切片的长度和容量不发生变化时，发生拷贝时，只是拷贝了指向底层的数组指针，并不会复制底层的数据结构。属于是浅拷贝。

切片定义

var identifier []type
//比如
var myarray []int

使用make()函数来创建切片

var slice1 []type=make([]type,len,cap)
//比如
var arr_int []int=make([]int,10,20)
//切片存放的类型是int,长度是10，容量是20

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.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.2添加元素

在切片尾部插入

var a []int
a = append(a, 1)               // 追加1个元素
a = append(a, 1, 2, 3)         // 追加多个元素, 手写解包方式
a = append(a, []int{1,2,3}...) // 追加一个切片, 切片需要解包

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()
}

输出：

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个切片

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)
}

输出：

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个位置插入切片

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)
}

第二个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             // 设置新添加的元素

copy(a[4:], a[3:])
a[3] = 5
fmt.Printf("len=%d cap=%d slice=%v\n", len(a), cap(a), a)

输出：

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个元素

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)
}

从中间为删除

a = append(a[:i], a[i 1], ...)
a = append(a[:i], a[i N:], ...)	//删除N个元素

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)
}

输出：

len=7,cap=11,a=[1 2 3 8 9 10 11]

尾部删除

a = a[:len(a)-1]   // 删除尾部1个元素
a = a[:len(a)-N]   // 删除尾部N个元素

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)
}

输出：

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]
}

输出：

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)
}

输出：

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)
}

输出：

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 // 用于遍历哈希表的迭代器
}

在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()
}

• 在工作中，当我们涉及到对一个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()
}

这篇好文章是转载于：学新通技术网