1 | Golang：基础数据结构

小鱼儿 2022-12-11 12:26 91阅读 0赞

三个常用的数据类型的大致实现，有点绕，但是很有收获！

## 切片 Slice ##

### 数据结构 ###

在**64位**架构的机器上，一个切片需要**24字节**的内存：指针字段需要**8字节**，长度和容量字段分别需要**8字节**。

`var slice []int` 创建的数据结构如下：

![切片数据结构][bfb393a96039e61a8e40064721c62bdb.png]

### 使用 ###

对新切片的长度与容量的计算规则如下：

> 对底层数组容量是k的切片`slice[i:j]`来说
> 
>  *  长度: `j - i`
>  *  容量: `k - i`

func showSliceLenAndCap() {
        
    	//创建一个整型切片
    	//其长度和容量都是5个元素
    	slice := []int{
        10, 20, 30, 40, 50}
    	fmt.Println("capacity: ", cap(slice), " length: ", len(slice))
    
    	//创建一个新切片
    	//其长度为2个元素，容量为4个元素
    	newSlice := slice[1:3]
    	fmt.Println("capacity: ", cap(newSlice), " length: ", len(newSlice))
    }

运行结果为：

![切片长度与容量][12f133458b805d7a9ed528bfe0f8d374.png]

其实也很好理解，对`slice[i:j]` 来说，`i` 为新切片的第一个元素，在就切片中的数组下标，`k` 是原数组最大的容量，所以新切片的容量为 `k - i`；对 `j` 来说，可以视为一个前闭后开区间，即 `[i, j)`，也就是不包含原数组中的第 `j` 位，所以长度为 `j - i`。

![新旧切片的联系][dcee3c4234e1e6e5e06bb3d52548da43.png]

当多个切片基于同一个数组时，修改共享部分的数据，在其他切片中也能看见改变。

func showSharedArrayBySlice() {
        
    	slice := []int{
        10, 20, 30, 40, 50}
    	slice1 := slice[0:3]
    	slice2 := slice[1:4]
    
    	slice1[1] = 666
      fmt.Println("slice: ", slice)
    	fmt.Println("slice1: ", slice1)
    	fmt.Println("slice2: ", slice2)
    	fmt.Println(slice2[0])
    }

运行结果为：

![切片共享底层数组][9bfe9a9ad64494b119f536999260e5b1.png]

### 扩容 ###

*  切片扩容使用 append，长度一定改变，但容量未必改变。
 *  append 可能会导致底层数组的值被覆盖，表现为别的共享此底层数组的切片，发现内容被改变。（不一定会发生，前置条件为必须是**共享的底层数组**）
 *  **如何创建一个不共享底层数组的切片**？
    
    > 让新产生的切片的长度、容量相同，第一次 append 的时候，发现容量不够，会进行自动扩容，使用新的底层数组，这样新增的元素，就不会影响其他共享了数组的切片
 *  length 在 1000 以下，扩容时 x2；以上则 x1.25。

下面是上述小点的代码表述：

func showSliceAppend() {
        
    	slice := []int{
        10, 20, 30, 40, 50}
    	slice1 := slice[1:2:2]
    	slice2 := slice[0:3]
    
    	showSliceLenAndCapValue(slice1)
    	showSliceLenAndCapValue(slice2)
    
    	slice1 = append(slice1, 66)
    	slice2 = append(slice2, 77)
    
    	fmt.Println("slice:  ", slice)
    	fmt.Println("slice1: ", slice1)
    	fmt.Println("slice2: ", slice2)
    }
    
    func showSliceLenAndCapValue(slice []int) {
        
    	fmt.Println("capacity: ", cap(slice), " length: ", len(slice))
    }

运行结果如下：

![append slice][]

### 迭代 ###

range 获取到的是一个元素副本。也就是说，range 的两个返回值中的 value 的地址在内存中只有一个。

## 映射 Map ##

关于 Golang 中 map 的实现，有篇非常透彻的[文章][Link 1]。与 Java 中的 HashMap 实现类似，都采用拉链法，但一个很大的不同之处在于，**一个桶只能放8个键值对，超过8个，会放入溢出桶**。

在Go语言里，通过键来索引映射时，即便这个键不存在也总会返回一个值。在这种情况下，返回的是该值对应的类型的零值。

在函数间传递映射并不会制造出该映射的一个副本。实际上，当传递映射给一个函数，并对这个映射做了修改时，所有对这个映射的引用都会察觉到这个修改。

[bfb393a96039e61a8e40064721c62bdb.png]: /images/20221123/4cb542023273409aa4c94212191e26fd.png
[12f133458b805d7a9ed528bfe0f8d374.png]: /images/20221123/2d156755b2c54924a9b21d4bdf079b57.png
[dcee3c4234e1e6e5e06bb3d52548da43.png]: /images/20221123/02bdb3ef32b14f48a86f99e94f107d44.png
[9bfe9a9ad64494b119f536999260e5b1.png]: /images/20221123/f045c3c1eae14283b5fe31ded9551444.png
[append slice]: /images/20221123/900bc881f07e47dbb5ead77482403b1a.png
[Link 1]: https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/