Go内置数据结构

绝地灬酷狼 2022-11-15 11:51 231阅读 0赞

### 文章目录 ###

*  Go内置数据结构
 *   *  数组
     *  切片slice
     *  映射map
     *  字符串

# Go内置数据结构 #

Go中有四大内置的数据结构：

*  数组
 *  切片slice
 *  映射map
 *  字符串

## 数组 ##

数组是一种很常见的数据结构，就是一系列相同类型的数据集合。计算机会为其分配一块连续的内存来保存数组中的元素，通过数组元素的索引访问数组元素，时间复杂度是O(1)

和Java不太相同，在go语言中，相同类型但是数组容量不同，也被视为不同的数组类型，只有两个条件都相同才是同一类型。

[1]int != [2]int

go语言底层中，数组类型的定义如下：

// Array contains Type fields specific to array types.
    type Array struct {
        
    	Elem  *Type // element type (数组元素类型)
    	Bound int64 // number of elements; <0 if unknown yet（数组容量）
    }

实际使用中，数组初始化：

var array [1]int
    var array = [4]int{
        1,2,3,4}
    var array [...]int{
        1,2,3}   // 编译器自动推导数组容量

实际走的底层初始化：

func NewArray(elem *Type, bound int64) *Type {
        
    	if bound < 0 {
        
    		Fatalf("NewArray: invalid bound %v", bound)
    	}
    	t := New(TARRAY)
    	t.Extra = &Array{
        Elem: elem, Bound: bound}
    	t.SetNotInHeap(elem.NotInHeap())
    	return t
    }

所以数组类型t是通过数组容量和数组元素类型一起决定的，并且当前数组是否应该在堆栈中初始化也在编译期就确定了。

第二个需要注意的是go在编译期可以对数组进行简单的越界检查，如果索引是常量的话，但是如果索引是变量的话，例如arr\[i\]，是检查不了的，但是在运行期如果i越界了，会抛出panic，程序异常中断，类似于java的runtimeException

访问数组的索引是非整数时，报错 “non-integer array index %v”；
    访问数组的索引是负数时，报错 “invalid array index %v (index must be non-negative)"；
    访问数组的索引越界时，报错 “invalid array index %v (out of bounds for %d-element array)"；

第三个需要注意的问题是，数组是赋值问题，函数传递数组是传递数组的拷贝，所以如果传递的数组比较大的话，内存拷贝的开销也会比较大，这时建议传递数组的头指针，但是这样函数对数组的操作会对数组造成改变

var array4 = testArray(arr4)	// 数组是值类型，在函数中传递的是数组的拷贝，所以不会修改到原数组，如果数组较大，数组拷贝开销大
    	fmt.Println(array4)		// [2 3 4]
    	fmt.Println(arr4)		// [1 2 3]
    	fmt.Println("=======================")
    	testArray2(&arr4)
    	fmt.Println(arr4)		// [2 3 4] 传递指针可以修改原数组并且效率高
    
    
    func testArray(array [3]int) [3]int {
        
    	for index,val := range(array){
        
    		val = val + 1
    		array[index] = val
    	}
    	return array
    }
    
    func testArray2(arrayPoint *[3]int) {
        
    	for index,val := range(arrayPoint){
        
    		val = val + 1
    		arrayPoint[index] = val
    	}
    }

## 切片slice ##

切片和数组非常相似，初始化方式也非常相似，切片其实是一种动态数组，可以自动扩容，容量可以发生变化。  
初始化

var sli1 []int
    	var sli3 = make([]int,5,8) // 也可以使用make初始化，5是元素个数，8是总容量

切片底层数据结构：其实底层也是数组，类似于Java的ArrayList

type SliceHeader struct {
        
    	Data uintptr    // 底层数组头指针
    	Len  int        // 切片元素数量
    	Cap  int        // 切片容量
    }

![027b700b31af167d4f4f8c5ae7737941.png][]

切片截取：

// 切片截取
    	fmt.Println(sli2)
    	tmp1 := sli2[:]	   // 切片不指定max，cap取得是底层数组的max
    	fmt.Println(tmp1)  // [1 2 3 4 5 6]
    	// 切片截取操作的是底层数组，底层数组改变，切片会随着改变
    	sli2[0] = 10
    	fmt.Println(sli2)	// [10 2 3 4 5 6]
    	fmt.Println(tmp1)	// [10 2 3 4 5 6]

第一个需要注意的问题就是切片截取后会生成一个新的切片，但是这个切片和原切片底层共用一个数组，所以，底层数组一旦发生改变会影响到两个切片

当切片非常大或者会发生逃逸，那么切片将会在堆上进行分配，当切片比较小且不会逃逸，可直接在栈上进行分配

访问切片元素和访问数组元素方式一样，都是通过下标直接访问

slice[1]

最后需要注意的是切片的追加和扩容

切片的追加使用的是append

sli4 = append(sli4, 4)

底层流程：

*  容量判断，是否需要扩容
    
     *  扩容，返回扩容后的切片数组头指针
 *  元素转移
 *  初始化一个新的切片

// append(slice, 1, 2, 3)
    ptr, len, cap := slice
    newlen := len + 3
    if newlen > cap {
        
        ptr, len, cap = growslice(slice, newlen)
        newlen = len + 3
    }
    *(ptr+len) = 1
    *(ptr+len+1) = 2
    *(ptr+len+2) = 3
    return makeslice(ptr, newlen, cap)

切片扩容：

func growslice(et *_type, old slice, cap int) slice {
        
    	newcap := old.cap
    	doublecap := newcap + newcap
    	if cap > doublecap {
        
    		newcap = cap
    	} else {
        
    		if old.len < 1024 {
        
    			newcap = doublecap
    		} else {
        
    			for 0 < newcap && newcap < cap {
        
    				newcap += newcap / 4
    			}
    			if newcap <= 0 {
        
    				newcap = cap
    			}
    		}
    	}

在分配内存空间之前需要先确定新的切片容量，运行时根据切片的当前容量选择不同的策略进行扩容：

*  如果期望容量大于当前容量的两倍就会使用期望容量；
 *  如果当前切片的长度小于 1024 就会将容量翻倍；
 *  如果当前切片的长度大于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；

## 映射map ##

哈希是除了数组外最常见的数据结构，数组是元素的序列集合，哈希是键值对映射的结构

哈希表是计算机科学中的最重要数据结构之一，这不仅因为它 O(1) 的读写性能非常优秀，还因为它提供了键值之间的映射。想要实现一个性能优异的哈希表，需要注意两个关键点 —— 哈希函数和冲突解决方法。

完美的哈希函数就是能让结果尽可能均匀的分布，哈希冲突尽可能小

解决哈希冲突的方法：

*  开放地址法
    
     *  开放地址法是在遇到冲突后，继续遍历寻找下一个空的位置
 *  拉链法
    
     *  遇到冲突会选择以链表的形式将冲突的key链接起来

gomap的基本使用：

// 初始化
    	map2 := make(map[string]int)

新增元素

res := make(map[string]interface{
        })
    	res["code"] = 200
    	res["msg"]  = "success"

删除元素

delete(res2,"code")

遍历元素：

for key,value := range res2{
        
    		fmt.Println("key: ",key)
    		fmt.Println("value: ",value)
    	}

Go 语言运行时同时使用了多个数据结构组合表示哈希表，其中 runtime.hmap 是最核心的结构体

type hmap struct {
        
        count        int               /* Map中元素数量 */
        flags        int8              /* 相关标志位 */
        B            int8              /* （1<< B * 6.5）为最多元素的数量 */
        noverflow    int16             /* 溢出桶的数量 */
        hash0        uint32            /* 哈希种子 */
        buckets      unsafe.Pointer    /* 桶指针 */
        oldbuckets   unsafe.Pointer    /* 桶指针（只有扩容的时候才使用，指向旧的桶） */
        nevacuate    uintptr           /* 用于桶搬迁 */
        extra        *mapextra         /* 当key/value非指针时使用 */
    }
    
    type mapextra struct {
        
        overflow      *[]*bmap         /* 溢出桶的指针 */
        oldoverflow   *[]*bmap             
        nextOverflow  *bmap                   
    }
    
    type bmap struct {
        
        tophash  [bucketCnt]uint8      /* bucketCnt=8，一个桶只能存放8对k/v, 低B位用来寻找桶，高8位用来寻找元素 */
    }
    
    /* 当kev/value不为指针时，溢出桶存放到mapextra结构中，overflow存放buckets中的溢出
        桶，oldoverflow存放oldbuckets中的溢出桶，nextOverflow预分配溢出桶空间 */
    type mapextra struct {
        
        overflow        *[]*bmap       /* 以切片形式存放buckets中的每个溢出桶 */
        oldoverflow     *[]*bmap       /*  以切片形式存放oldbuckets中的每个溢出桶*/
        nextOverflow    *bmap
    }

![28c3c186c7a95d0d8ef9091e32192b99.png][]

[源码分析][Link 1]

## 字符串 ##

Go 语言中的字符串只是一个只读的字节数组，下图展示了 “hello” 字符串在内存中的存储方式  
![ee829f6520f814eb2f073099c71c9c88.png][]

所以底层实现也是字节数组和长度两个字段：

type StringHeader struct {
        
    	Data uintptr
    	Len  int
    }

字符串类型转换

func main() {
        
    	str := "1"
    	fmt.Println(strconv.Atoi(str))	// int error
    	fmt.Println(strconv.ParseBool("false"))
    	fmt.Println(strconv.Itoa(1))
    	fmt.Println([]byte("test"))// 字符串转byte数组
    	// 2,byte转为string
    	byte1 := []byte{
        116,101,115,116}
    	fmt.Println(string(byte1[:]))
    }

[027b700b31af167d4f4f8c5ae7737941.png]: /images/20221022/489f42cfac3742c1bb7a1fece1adceb1.png
[28c3c186c7a95d0d8ef9091e32192b99.png]: /images/20221022/35e7f5b8dd6546538ff7631e0e82e86c.png
[Link 1]: https://studygolang.com/articles/25134
[ee829f6520f814eb2f073099c71c9c88.png]: /images/20221022/94fac4730aa54f1a96ba7b15cf216aa7.png