golang的string、map、sclie

强某某 · · 507 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

slice

切片的原理

  • 切⽚ ( slice ) 是Go中⼀种⽐较特殊的数据结构,这种数据结构更便于使⽤和管理数据集合。
  • 切⽚是围绕动态数组的概念构建的,与数组相⽐切⽚的⻓度是不固定的,可以追加元素,在追加时可能使切⽚的容量增⼤。
  • Go中的切⽚作为函数参数不是地址传递
func Demo(slice []int) {
 slice = append(slice, 6, 6, 6)
 fmt.Println("函数中结果:", slice)
}
func main() {
 //定义⼀个切⽚
 slice := []int{1, 2, 3, 4, 5}
 Demo(slice)
 fmt.Println("定义中结果:", slice)
}

结果

函数中结果: [1 2 3 4 5 6 6 6]
定义中结果: [1 2 3 4 5]

在上⾯代码中并没有将切⽚(slice)的修改结果在主调函数中显示。

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

下⾯就开始详细理解下 slice,理解后会对开发出⾼效的程序⾮常有帮助。

//定义⼀个切⽚
var slice []int
//unsafe.Sizeof功能:计算⼀个数据在内存中占的字节⼤⼩
size := unsafe.Sizeof(slice)
fmt.Println(slice)
//⽆论切⽚是否有数据 计算结果都为:24

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

Go语⾔中切⽚数据结构在源码包src的 /runtime/slice.go⾥⾯:

//path:Go SDK/src/runtime/slice.go
type slice struct {
 array unsafe.Pointer
 len int
 cap int
}
1.jpg

切片的源码

在创建切⽚时,可以根据源码进⾏分析

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

会被编译器翻译为 runtime.makeslice,并执⾏如下函数:

func makeslice(et *_type, len, cap int) slice {
 maxElements := maxSliceCap(et.size)
 //判断len是否满⾜条件
 if len < 0 || uintptr(len) > maxElements {
 panic(errorString("makeslice: len out of range"))
 }
 //判断cap是否满⾜条件
 if cap < len || uintptr(cap) > maxElements {
 panic(errorString("makeslice: cap out of range"))
 }
 //根据cap⼤⼩,通过mallocgc创建内存空间
 p := mallocgc(et.size*uintptr(cap), et, true)
 //将地址作为其中⼀个结构体成员返回
 return slice{p, len, cap}
}

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

var slice *[]int = new([]int)

会编译为:

func newobject(typ *_type) unsafe.Pointer {
 //创建内存空间 并返回指针
 return mallocgc(typ.size, typ, true)
}

string

string 数据结构

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

type stringStruct struct {
 str unsafe.Pointer
 len int
}

其数据结构很简单:

  • stringStruct.str:字符串的⾸地址;
  • stringStruct.len:字符串的⻓度;

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

string操作

  • 声明
var str string
str = "Hello World"

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

// 跟据字符串地址构建string
func gostringnocopy(str *byte) string {
 // 先构造stringStruct
 ss := stringStruct{str: unsafe.Pointer(str), len: findnull(str)}
 // 再将stringStruct转换成string
 s := *(*string)(unsafe.Pointer(&ss)) 
 return s
}

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

[]byte转string

func GetStringBySlice(s []byte) string {
 return string(s)
}

需要注意的是这种转换需要⼀次内存拷⻉。
转换过程如下:

  1. 跟据切⽚的⻓度申请内存空间,假设内存地址为p,切⽚⻓度为len(b);
  2. 构建string(string.str = p;string.len = len;)
  3. 拷⻉数据(切⽚中数据拷⻉到新申请的内存空间)


    2.jpg

string转[]byte

func GetSliceByString(str string) []byte {
 return []byte(str)
}

string转换成byte切⽚,也需要⼀次内存拷⻉,其过程如下:

  • 申请切⽚内存空间
  • 将string拷⻉到切⽚
3.jpg

字符串拼接

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

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

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

字符串拼接伪代码如下:

// 字符串拼接
func concatstrings(a []string) string {
 length := 0 // 拼接后总的字符串⻓度
 for _, str := range a {
 length += length(str)
 }
 s, b := rawstring(length) // ⽣成指定⼤⼩的字符串,返回⼀个string和切⽚,⼆者共享内
存空间
 for _, str := range a {
 copy(b, str) // string⽆法修改,只能通过切⽚修改
 b = b[len(str):]
 }
 return s
}

因为string是⽆法直接修改的,所以这⾥使⽤rawstring()⽅法初始化⼀个指定⼤⼩的string,同时返回⼀
个切⽚,⼆者共享同⼀块内存空间,后⾯向切⽚中拷⻉数据,也就间接修改了string。

rawstring()源代码如下:

// ⽣成⼀个新的string,返回的string和切⽚共享相同的空间
func rawstring(size int) (s string, b []byte) {
 p := mallocgc(uintptr(size), nil, false)
 stringStructOf(&s).str = p
 stringStructOf(&s).len = size
 *(*slice)(unsafe.Pointer(&b)) = slice{p, size, size}
 return
}

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

像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的结构
type hmap struct {
count int //map中的元素个数,必须放在 struct的第⼀个位置,因为 内置的len函数会
从这⾥读取
flags uint8
B uint8 // 说明包含2^B个bucket
noverflow uint16 // 溢出的bucket的个数
hash0 uint32 // hash种⼦
buckets unsafe.Pointer // buckets的数组指针
oldbuckets unsafe.Pointer // 结构扩容的时候⽤于复制的buckets数组
nevacuate uintptr // 搬迁进度(已经搬迁的buckets数量)
extra *mapextra
}
  • bucket的数据结构
type bmap struct {
// tophash generally contains the top byte of the hash value
// for each key in this bucket. If tophash[0] < minTopHash,
// tophash[0] is a bucket evacuation state instead.
tophash [bucketCnt]uint8 //tophash 是 hash 值的⾼ 8 位
// Followed by bucketCnt keys and then bucketCnt values.
// NOTE: packing all the keys together and then all the values together
makes the
// code a bit more complicated than alternating key/value/key/value/...
but it allows
// us to eliminate padding which would be needed for, e.g.,
map[int64]int8.
// Followed by an overflow pointer.
}

注意: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

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:强某某

查看原文:golang的string、map、sclie

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

507 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传