slice

切片的原理

  • 切? ( slice ) 是Go中?种?较特殊的数据结构，这种数据结构更便于使?和管理数据集合。
  • 切?是围绕动态数组的概念构建的，与数组相?切?的?度是不固定的，可以追加元素，在追加时可能使切?的容量增?。
  • Go中的切?作为函数参数不是地址传递

结果

在上?代码中并没有将切?（slice）的修改结果在主调函数中显示。

因为Go语?所有函数参数都是值传递。

下?就开始详细理解下 slice，理解后会对开发出?效的程序?常有帮助。

slice 的数据结构很简单，?个指向真实数据集合地址的指针ptr，slice 的?度 len 和容量 cap 。

Go语?中切?数据结构在源码包src的 /runtime/slice.go??：

1.jpg

切片的源码

在创建切?时，可以根据源码进?分析

var slice []int = make([]int, 10, 20)

会被编译器翻译为 runtime.makeslice，并执?如下函数：

如果创建切?是基于新建内存空间

会编译为：

string

string 数据结构

源码包src/runtime/string.go：stringStruct定义了string的数据结构：

其数据结构很简单：

  • stringStruct.str：字符串的?地址；
  • stringStruct.len：字符串的?度；

string数据结构跟切?有些类似，只不过切?还有?个表示容量的成员，事实上string和切?，准确的说
是byte切?经常发?转换。

string操作

  • 声明

字符串构建过程是先跟据字符串构建stringStruct，再转换成string。转换的源码如下：

string在runtime包中就是stringStruct，对外呈现叫做string。

[]byte转string

需要注意的是这种转换需要?次内存拷?。
转换过程如下：

  1. 跟据切?的?度申请内存空间，假设内存地址为p，切??度为len(b)；
  2. 构建string（string.str = p；string.len = len；）

  3. 拷?数据(切?中数据拷?到新申请的内存空间)


    2.jpg

string转[]byte

string转换成byte切?，也需要?次内存拷?，其过程如下：

  • 申请切?内存空间
  • 将string拷?到切?

3.jpg

字符串拼接

str := "Str1" + "Str2" + "Str3"

即便有?常多的字符串需要拼接，性能上也有?较好的保证，因为新字符串的内存空间是?次分配完成
的，所以性能消耗主要在拷?数据上。

?个拼接语句的字符串编译时都会被存放到?个切?中，拼接过程需要遍历两次切?，第?次遍历获取
总的字符串?度，据此申请内存，第?次遍历会把字符串逐个拷?过去。

字符串拼接伪代码如下：

因为string是?法直接修改的，所以这?使?rawstring()?法初始化?个指定??的string，同时返回?
个切?，?者共享同?块内存空间，后?向切?中拷?数据，也就间接修改了string。

rawstring()源代码如下：

为什么字符串不允许修改？

像C++语?中的string，其本身拥有内存空间，修改string是?持的。但Go的实现中，string不包含内存
空间，只有?个内存的指针，这样做的好处是string变得?常轻量，可以很?便的进?传递?不?担?
内存拷?。
因为string通常指向字符串字?量，?字符串字?量存储位置是只读段，?不是堆或栈上，所以才有了
string不可修改的约定。

[]byte转换成string?定会拷?内存吗？

byte切?转换成string的场景很多，为了性能上的考虑，有时候只是临时需要字符串的场景下，byte切
?转换成string时并不会拷?内存，?是直接返回?个string，这个string的指针(string.str)指向切?的
内存。
?如，编译器会识别如下临时场景：

  • 使?m[string(b)]来查找map（map是string为key，临时把切?b转成string）；
  • 字符串拼接，如"<" + "string(b)" + ">"；
  • 字符串?较：string(b) == "foo"

因为是临时把byte切?转换成string，也就避免了因byte切?同容改成?导致string引?失败的情况，所
以此时可以不必拷?内存新建?个string。

string和[]byte如何取舍

string和[]byte都可以表示字符串，但因数据结构不同，其衍?出来的?法也不同，要跟据实际应?场景
来选择。

string 擅?的场景：

  • 需要字符串?较的场景；
  • 不需要nil字符串的场景；

[]byte擅?的场景：

  • 修改字符串的场景，尤其是修改粒度为1个字节；
  • 函数返回值，需要?nil表示含义的场景；
  • 需要切?操作的场景；

虽然看起来string适?的场景不如[]byte多，但因为string直观，在实际应?中还是?量存在，在偏底层
的实现中[]byte使?更多。

map

map原理

go语?中的map是?种内建引?类型

map存储时key不可重复，?顺序，排序的话可以将key排序，然后取出对应value。只有可以?较
的类型才可以作key，value则?限制。

go中的map采?的是哈希map

给定key后，会通过哈希算法计算?个哈希值，低B位(这?是?写的B，2^B表示当前map中
bucket的数量)代表的是存在map中的哪?个bucket，?8位则是了存在bucket中的?个uint[8]数
组中，?8位所在的数组indec可?来寻找对应key的index。

map可抽象为bucket结构体组成的结构体，bucket数量?开始是固定的，后期不够?之后会进?
扩容，bucket内部含有数组，bucket内部数组存储的即为key和value，为8组数据，存储?式为
key0，key1，key2…value0，value1，value2…形式，?不是key和value顺次存储，这样是为了
防?key和vaule?度不?致时需要额外padding。key和value存储在同?个数组中。

map的结构体

  • bucket的结构
  • bucket的数据结构

注意：bucket中不?有tophash数组，??存储的是key通过hash函数算出来的哈希值的?8位。
数组?度为8，对应了存储key和value的字节数组的index…注意后???注释，hmap并?只有?
个tophash，?是后?紧跟8组kv对和?个overflow的指针，这样才能使overflow成为?个链表的
结构。但是这两个结构体并不是显示定义的，?是直接通过指针运算进?访问的。

kv的存储形式为”key0key1key2key3…key7val1val2val3…val7″，这样做的好处是：在key和value
的?度不同的时候，节省padding空间。如上?的例?，在map[int64]int8中，4个相邻的int8可
以存储在同?个内存单元中。如果使?kv交错存储的话，每个int8都会被padding占?单独的内存
单元（为了提?寻址速度）。

map中key查找的流程

?个完整的map中key查找的流程:

  • 根据传?的key?对应的hash函数算出哈希值
  • 取哈希值的低B位定为到是哪?个bucket

  • 定位到bucket之后，取哈希值的?8位，和bucket中的uint[8]数组中存储的?8位进??对，
    完全匹配根据数组的inidex在key，value字节数组中查找对应的key，若匹配上则返回key，
    value，若没有完全匹配则继续?对?8位的值，当前bucket的?8位数组全部?对完，若有
    溢出bucket则继续?对，若全部?对完未发现则当前map不含有此key


    4.jpg

5.jpg