整理下Go语言提供的数据结构
一、顺序数据结构
1.1. 数组
语言自带。值得一提的是调函数的时候如果传数组是值传递(复制整个数组)，这点和java差别很大
func set(arr [3]int){
arr[0]=453532
}
func setPointer(arr *[3]int){
arr[0]=453532
}
func Test(t *testing.T) {
arr:=[...]int{1,2,3}
set(arr)
fmt.Println(arr) // [1 2 3]
setPointer(&arr)
fmt.Println(arr) //[453532 2 3]
}
1.2. 动态数组
可以把slice理解成java的ArrayList
但遗憾的是他没有ArrayList好用。
坑
把slice当ArrayList用存在的坑：
-
slice是个view，调别的函数append修改后，原先slice的内容没变！（见下图）
image.png
https://blog.csdn.net/weixin_40762352/article/details/79576616
解法：
a.自己封装一个ArrayList
b.调别的函数时，让函数返回slice，类似于a=append(a,1)
c.传slice的指针（自己改成引用传递）
- for range对数组元素进行修改时，改的是复制后的新对象，原对象不变
https://my.oschina.net/xuleo/blog/1624683
https://www.cnblogs.com/kaifoon/p/9757830.html
- for range时想新增/delete元素有问题，应该用fori
https://my.oschina.net/solate/blog/2998311
https://dinolai.com/notes/golang/golang-delete-slice-item-in-range-problem.html
构造slice
http://www.cheat-sheets.org/saved-copy/go-lang-cheat-sheet-master.20181212/golang_refcard.pdf
make([]T,len) 不传cap时，cap等于len
-
零值是nil
image.png
Q: ans:=make([]bool,n) 默认值？
A:
func Test(t *testing.T) {
ages:=make([]bool,2)
AssertTrue(!ages[0],t)
AssertTrue(!ages[1],t)
}
实现原理：cap是啥? slice的肚子里有什么？
-
cap是干嘛的?
扩展的时候，比如s2:=s1[3:5] 不能超过cap
image.png
append时候如果cap不够，能动态扩容（自动开个新array，拷贝过去）
实现原理: slice 怎么扩容
https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-array-and-slice/#325-%E6%8B%B7%E8%B4%9D%E5%88%87%E7%89%87
https://segmentfault.com/a/1190000017341615
https://juejin.cn/post/6844903812331732999#heading-2
- 有没有缩容设计
java ArrayList提供了缩容方法，但没有自动缩容机制
go没缩容机制，也没提供这样的api。如有必要，可以用copy
Go 本身没有切片缩容后，底层数组不会被释放掉。删除次数多了，会占用很多内存。
可以用copy的方法，创建新的切片和底层数组。并把原来的切片置nil。
https://cloud.tencent.com/developer/article/1720270
判断内容相等
可以用reflect.DeepEqual
https://golang.org/pkg/reflect/#DeepEqual
打印slice
fmt.Printf("len=%d cap=%d slice=%v\n",len(x),cap(x),x)
https://www.runoob.com/go/go-slice.html
append
http://shouce.jb51.net/gopl-zh/ch4/ch4-02.html
concatenate two slices
https://stackoverflow.com/questions/16248241/concatenate-two-slices-in-go
append([]int{1,2}, []int{3,4}...)
- 那要是 append nil... 呢?
正常，不会panic, 相当于没append:
func main() {
a := make([]int, 1)
var b []int
a = append(a, b...)
a = append(a, nil...)
fmt.Println(a) // [0]
}
copy slice
使用copy函数
https://www.geeksforgeeks.org/how-to-copy-one-slice-into-another-slice-in-golang/
但是注意创建的新slice长度提前要设置好，The builtin copy(dst, src) copies min(len(dst), len(src)) elements.
https://stackoverflow.com/questions/30182538/why-cant-i-duplicate-a-slice-with-copy
arr := []int{1, 2, 3}
tmp := make([]int, len(arr))
copy(tmp, arr)
fmt.Println(tmp)
fmt.Println(arr)Output (as expected):
[1 2 3]
[1 2 3]
1.3. Queue
1.3.1. 无界队列 (unbounded)
非并发安全
slice就能当queue用。
另外bytes.buffer可以当byte类型的queue,其实内部就是[]byte
https://www.kancloud.cn/digest/batu-go/153538
并发安全的无界队列
chan 是有界队列，go 团队不愿意在标准库里加入无界队列
可以自己封装，思路是在两个chan之间加个中转 slice，单协程操作该slice 避免并发问题。见 https://blog.zeromake.com/pages/ultimete-channel/
1.3.2. 有界 (bounded)
非并发安全
没有给单线程用的，需要自己拿slice封装
并发安全的有界阻塞队列：channel
channel是有界阻塞队列，倒是可以写入的时候判断，以实现有界非阻塞
https://www.coder.work/article/24623
默认是 unbuffered chan, 队列长度0。可以在 make 时设置队列长度
原理
Q: channel肚子里是啥，内部实现原理？
A:channel是个指针(chan是引用类型），指向的struct runtime.hchan，是个有锁的环形队列
https://draveness.me/golang/docs/part3-runtime/ch06-concurrency/golang-channel/
13 | Channel：另辟蹊径，解决并发问题
理论上可以实现 lock-free queue, 但是 golang 官方的 issue 一直没进展。作为替代，社区有实现 lock-free queue 的库
见 https://draveness.me/golang/docs/part3-runtime/ch06-concurrency/golang-channel/
https://github.com/golang/go/issues/8899#issuecomment-269321360
特殊用法
Q: channel的所有方法都是阻塞方法，想非阻塞咋办？
A: 用select+default自己封装非阻塞方法:
见effective go p102
Q: 会 panic 的情况?
总共有 3 种：
- close 为 nil 的 chan；
- send 已经 close 的 chan；
- close 已经 close 的 chan。
Q: 如何用 chan 做全体广播?
a. 自己写个消费者去消费chan，然后广播通知所有订阅者
b. 利用close
https://www.cnblogs.com/faithfu/p/12068414.html
1.4. Deque
非并发安全
go 的slice 不好实现"从左侧 enque", 要找其他数据结构。
java有两种实现，链表和环形队列
Go的list包下有个链表，API很不deque，但是能凑合用
ring包下的环没法动态扩容，API也比较沙雕，没法拿来当deque
https://github.com/polaris1119/The-Golang-Standard-Library-by-Example/blob/master/chapter03/03.3.md
鉴于自带链表的API不好用，自己写了一个：
https://github.com/seeflood/Copy-Paste-Data-Structures/tree/master/src/main/go/io/github/seeflood/copy-paste-ds/deque
并发安全
chan 就是，内部是有锁环形队列
1.5. PriorityQueue
https://books.studygolang.com/The-Golang-Standard-Library-by-Example/chapter03/03.3.html
标准库有，API设计的很不好用，想用得实现一堆接口。想用IntHeap都得自己写（标准库里没有IntHeap）；
heap包下面的unit test代码里有个IntHeap，因此一个偷懒的做法是：想用IntHeap的时候可以去heap包下面的unit test代码里把IntHeap复制粘贴到自己的项目
鉴于API过于难用，自己封装了个SliceHeap
1.6. 临时对象池 sync.Pool
sync.Pool 数据类型用来保存一组可独立访问的临时对象。请注意这里加粗的“临时”这两个字，它说明了 sync.Pool 这个数据类型的特点，也就是说，它池化的对象会在未来的某个时候被毫无预兆地移除掉。而且，如果没有别的对象引用这个被移除的对象的话，这个被移除的对象就会被垃圾回收掉。
实现的有问题，有需要还是找三方库：
详见 https://time.geekbang.org/column/article/301716
- 连接池
一般不用 sync.Pool
事实上，我们很少会使用 sync.Pool 去池化连接对象，原因就在于，sync.Pool 会无通知地在某个时候就把连接移除垃圾回收掉了，而我们的场景是需要长久保持这个连接，所以，我们一般会使用其它方法来池化连接
可以自己用队列实现(用 channel 或者 slice），或者用三方库
- 协程池 worker pool
标准库没有，要用三方库
二、Map
2.1. hashmap
自带的map就是
http://shouce.jb51.net/gopl-zh/ch4/ch4-03.html
2.1.1. 创建
Q: 用var a map[xxx]xxx这样声明时，会创建新的map吗？
实测不会，只生成nil；别的写法都会创建新map
func Test(t *testing.T) {
var ages map[string]int
if ages == nil {
fmt.Println("var map[string]int==nil")
}
ages = make(map[string]int)
if ages == nil {
fmt.Println("make(map[string]int)==nil")
}
ages=map[string]int{}
if ages == nil {
fmt.Println("map[string]int{}==nil")
}
}
打印结果:
var map[string]int==nil
https://books.studygolang.com/gopl-zh/ch4/ch4-03.html
-
nil的map(没初始化的map)能读能删不能写
image.png
slice用惯了可能会懒得写初始化，直接
var s []int
s = append(s, 1)
这样反正append能写nil slice。但是map必须先初始化才能写！
2.1.2. get与containsKey
age, ok := ages["bob"]
if !ok { /* "bob" is not a key in this map; age == 0. */ }
不加第二个变量ok也不会panic:
2.1.3. 遍历
for range
m := map[string]int{
"hello": 100,
"world": 200,
}
for key, value := range m {
fmt.Println(key, value)
}
Q: 如果 map 是 nil, 会 panic 么
不会
package main
import "fmt"
func main() {
var m map[string]string
for k, _ := range m {
fmt.Printf("k :%v\n",k)
}
fmt.Println("end")
}
Q: 能否在for range的过程中添加/删除元素?
A:
https://stackoverflow.com/questions/23229975/is-it-safe-to-remove-selected-keys-from-map-within-a-range-loop
删除可以，删掉的不会被遍历到；添加虽然可以，但是加进去的可能会在当次循环被遍历到、也可能不会，有不确定性。
2.1.4. 判断两个map相等
How to test the equivalence of maps in Golang?
https://www.geeksforgeeks.org/comparing-maps-in-golang/
reflect.DeepEqual(a, b)
2.1.5. golang中如何判断两个struct相等
https://www.geeksforgeeks.org/structure-equality-in-golang/
==和DeeplyEqual()都行，肚子里的值一样就算相等，不是java那种比较指向的内存对象相等
golang里的map用==比较两个key相等，因此实际上是比较struct肚子里的值。如果确实想比较两个key是“同一个”，可以用指针当key
https://stackoverflow.com/questions/29748003/map-with-function-pointer-as-key-in-go
2.1.6. 能否自定义map中元素判等的逻辑？
不能，map用==判断key相等的
https://juejin.cn/post/6844903923166232589#heading-8
2.1.7. 想用<key1,key2,value>式的双key map？
https://stackoverflow.com/questions/30529970/golang-map-with-multiple-keys-per-value
key放struct里就行
缺点是：如果修改 struct 肚子里的值，就没法再从 map 里取到原来对应的 value 了。
type mapKey struct {
key int
}
func main() {
var m = make(map[mapKey]string)
var key = mapKey{10}
m[key] = "hello"
fmt.Printf("m[key]=%s\n", m[key])
// 修改key的字段的值后再次查询map，无法获取刚才add进去的值
key.key = 100
fmt.Printf("再次查询m[key]=%s\n", m[key])
}
2.1.8. 内部实现
golang中的map是一个 指针，指向的struct是个哈希表
https://blog.csdn.net/K346K346/article/details/109559718
https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/
https://zjykzk.github.io/post/cs/golang/map/
https://guidao.github.io/go_map.html
Q: 如何处理哈希碰撞
用拉链法来解决哈希碰撞的问题。哈希表的每个桶都只能存储 8 个键值对，一旦当前哈希的某个桶超出 8 个，新的键值对就会存储到哈希的溢出桶中。
（个人理解，本质上是分块链表?)
Q: 如何扩容
随着键值对数量的增加，溢出桶的数量和哈希的装载因子也会逐渐升高，超过一定范围就会触发扩容，扩容会将桶的数量翻倍
具体来说，在以下两种情况发生时触发哈希的扩容：
- 装载因子已经超过 6.5；
- 哈希使用了太多溢出桶；
2.2. ordered map (例如 TreeMap/SkipListMap 这样的平衡搜索树类的数据结构)
搜了下好像标准库没有
社区有
2.3. LRUCache
2.4. ConcurrentHashMap
a. 通过改变线程模型，让单线程操作map
b. 用读写锁自己封装一个
c. 用第三方的实现，分片加锁
比如 https://github.com/orcaman/concurrent-map
d. 应对特殊场景的 sync.Map
不常用，特殊场景会比 map+RWMutex 的方式性能好；缺点是会丢失类型信息，方法传参、返回结果都是 interface{}
https://www.jianshu.com/p/a2831dfa0a91
https://studygolang.com/articles/18070
https://colobu.com/2017/07/11/dive-into-sync-Map/
-
内部原理
image.png
俩 map，有一个仅用于读的 read map，相当于读缓存
read map 有性能优势是因为 value 是个 holder，holder 里能基于 cas 修改value
新增 kv 会写进 dirty map （会加互斥锁，不是读写锁），达到一定条件( 缓存 miss 率太高、达到一定的值）后，会将dirty数据提升为read
https://tonybai.com/2020/11/10/understand-sync-map-inside-through-examples/
https://time.geekbang.org/column/article/301174
2.5. 其他并发安全的数据结构
除了sync.Map和sync.Pool，GO就没啥并发安全数据结构了。见讨论：
https://groups.google.com/g/golang-china/c/JdbR_CGo3ao/m/Uct3hj2wKCsJ
三、Set
3.1. hashset
没有，只能拿map模拟
https://stackoverflow.com/questions/34018908/golang-why-dont-we-have-a-set-datastructure
实现时注意，map[interface{}]struct{}比map[interface{}]bool好在空结构体不占用空间：
https://geektutu.com/post/hpg-empty-struct.html
3.2. bitset/bitmap
标准库没有。开源的有个github.com/willf/bitset
见https://blog.cyeam.com/golang/2017/01/18/go-optimize-bitset
我也实现了个
https://github.com/seeflood/Copy-Paste-Data-Structures/blob/master/src/main/go/io/github/seeflood/copy-paste-ds/set/BitSet.go
实现方法参考https://books.studygolang.com/gopl-zh/ch6/ch6-05.html
另外，分块bitmap(Roaring bitmap)有个开源的go实现
https://github.com/RoaringBitmap/roaring
四、字符串相关
4.1. string
http://shouce.jb51.net/gopl-zh/ch3/ch3-05.html
https://blog.golang.org/strings
4.1.1. 默认是按字节访问
In Go, a string is in effect a read-only slice of bytes
也就是说string是只读的[]byte(也就是说string不可变），虽然你的字符串可能是UTF-8编码，但是语言提供的很多API(比如len(string)、随机访问字符s[1]等)不管你啥编码，统一按字节访问字符串……
那想按字符访问字符串怎么办？
求长度
关于求字符串长度，替代len(string)可以用utf8.RuneCountInString(s)，但是这API每次调用得遍历解析一遍计算长度，时间(N)。java的String.length()是返回char[].length,时间O(1)
按字符访问
关于按字符访问，for range是按字符访问字符串，但他是顺序访问，不支持随机访问
想随机访问？得把字符串转[]rune：
r := []rune(s)
但是你会发现，转成[]rune后，strings包下面的API都用不了了！
这设计，真想骂娘！！！
注1：strings包下的API只处理UTF-8编码的string。
注2：Go语言源文件总是用UTF8编码，并且Go语言的文本字符串也以UTF8编码的方式处理
注3：UTF-8编码中，没有任何字符的编码是其它字符编码的子串，或是其它编码序列的子串，因此搜索一个字符时只要搜索它的字节编码序列即可，不用担心前后的上下文会对搜索结果产生干扰（说人话就是：做字符串匹配的时候，无脑用字节匹配就行，见下图）
4.1.2. 判断
判空
string的零值是""，也没法赋值nil给string变量
https://tour.golang.org/basics/12
所以len(s)==0 或者s==""都可以拿来判空
https://stackoverflow.com/questions/18594330/what-is-the-best-way-to-test-for-an-empty-string-in-go
判断相等
就用==就行。不区分大小写用EqualFold
https://blog.csdn.net/oqqYuan1234567890/article/details/59110219
4.1.3. 类型转换
[]rune []byte和string互相转换
https://blog.csdn.net/dengming0922/article/details/80883574
https://stackoverflow.com/questions/29255746/how-encode-rune-into-byte-using-utf8
string和数字转换
一种方法是用fmt.Sprintf返回一个格式化的字符串；
另一个方法是用strconv包的 strconv.Itoa. lintcode不让用这个，leetcode 可以。
http://shouce.jb51.net/gopl-zh/ch3/ch3-05.html
x := 123
y := fmt.Sprintf("%d", x)
fmt.Println(y, strconv.Itoa(x)) // "123 123"
字符和数字互相转换？
如果是 0-9 这样的“单字符数字”(我自己起的名字），可以这样转:
b := 1 + '0' // int32
fmt.Printf("Size: %d\nType: %s\nCharacter: %c\n", unsafe.Sizeof(b), reflect.TypeOf(b), b)
rawNum := b - '0' // int32
fmt.Println(rawNum)
如果是“多字符数字”，就得当做字符串和数字做转换
Convert interface/any data structure to string
https://yourbasic.org/golang/interface-to-string/
Use fmt.Sprintf
var x interface{} = "abc"
str := fmt.Sprintf("%v", x)
另见《fmt.Sprintf vs string(data) vs String()》
4.1.4. 改
字符串的值是不可变的：一个字符串包含的字节序列永远不会被改变，当然我们也可以给一个字符串变量分配一个新字符串值。可以像下面这样将一个字符串追加到另一个字符串：
s := "left foot"
t := s
s += ", right foot"
这并不会导致原始的字符串值被改变，但是变量s将因为+=语句持有一个新的字符串值，但是t依然是包含原先的字符串值。
fmt.Println(s) // "left foot, right foot"
fmt.Println(t) // "left foot"
因为字符串是不可修改的，因此尝试修改字符串内部数据的操作也是被禁止的：
s[0] = 'L' // compile error: cannot assign to s[0]
拼接
java有StringBuilder这样的字符串专用stack，相应的go里可以用的动态数组有：
- []byte,通过append拼接
- bytes.Buffer,通过buffer.WriteString()往里面写字符串
其实bytes.Buffer内部就是[]byte - strings.Builder
Examples &选型benchmark:
https://mojotv.cn/go/golang-most-efficient-string-join
https://geektutu.com/post/hpg-string-concat.html#1-2-benchmark-%E6%80%A7%E8%83%BD%E6%AF%94%E6%8B%BC
从benchmark看来，有preallocate的性能好，没有的话这三个差别不大
ref:
https://stackoverflow.com/questions/1760757/how-to-efficiently-concatenate-strings-in-go/47798475#47798475
https://www.jianshu.com/p/df92c0ee6cc8
随机访问、修改
只改其中一两个字符
https://stackoverflow.com/questions/37688457/how-to-replace-nth-char-from-a-string-in-go
方案1. reslice
chars = chars[:3] + "z" + chars[4:]
方案2. 从一开始就用[]byte,而不是string
func main() {
var chars = []byte{'a', 'b', 'c', 'd', 'e', 'f'}
fmt.Println(string(chars[3]))
fmt.Printf("%T\n", chars)
chars[3] = 'z'
fmt.Println(string(chars))
}
方案3. 拷贝成别的数据结构，然后修改
func replaceAt(s string, i int, c rune) string {
r := []rune(s)
r[i] = c
return string(r)
}
替换
strings包下面的替换不支持正则
https://github.com/unknwon/the-way-to-go_ZH_CN/blob/master/eBook/04.7.md#474-%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%9B%BF%E6%8D%A2
想用正则替换得用regexp包
https://www.geeksforgeeks.org/golang-replacing-all-string-which-matches-with-regular-expression/
写正则表达式的时候用...比较方便(字符串面值)，使用反引号代替双引号。在原生的字符串面值中，没有转义操作
其他操作
就用strings 和 strconv 包
https://github.com/unknwon/the-way-to-go_ZH_CN/blob/master/eBook/04.7.md
4.1.5.字符
java用char通吃，但go设计的比较烂，需要理解byte,uint8,int32以及rune.
https://golangbyexample.com/character-in-go/
http://c.biancheng.net/view/18.html
Go语言的字符有以下两种：
- 一种是 uint8 类型，byte 类型是 uint8 的别名，代表了 ASCII 码的一个字符。
- 另一种是 rune 类型，代表一个 UTF-8 字符，当需要处理中文、日文或者其他复合字符时，则需要用到 rune 类型。rune 类型是int32的别名。
声明字符变量
To declare either a byte or a rune we use single quotes. While declaring byte we have to specify the type, If we don’t specify the type, then the default type is meant as a rune.
To declare a string, we use double quotes or backquotes. Double quotes string honors escape character while back quotes string is a raw literal string and doesn’t honor any kind of escaping.
这些字符都是啥类型？
s := "hello, world"
c:=s[0] // c is uint8
cnum := c - '0' //uint8
bytes := []byte(s)
x:=bytes[0] //x is uint8test:='0' //int32.'0'是untyped constant
cnum32:=test-'0' //int32.'0'是untyped constant
直接访问的话，得到的字符是uint8.byte是uint8的别名
r, size := utf8.DecodeRuneInString(s[1:]) // r is int32
for i, w := range "Hello, 世界" {
fmt.Printf("%d\t%q\t%d\n", i, w, w)
}
// w is int32
utf8解码后是int32.for range自动解码。
As mentioned above, integers come in a couple of forms and each form has its own default type: int for simple constants like 123 or 0xFF or -14 and rune for quoted characters like 'a', '世' or '\r'.
https://blog.golang.org/constants#TOC_10.
国际化字符rune
rune是int32的别名，但是使用起来注意有区别，比如for range 字符串时，每个中文字符算3个长度，而for range []rune(字符串) 每个中文字符算一个长度:
for i, r := range "Hello, 世界" {
fmt.Printf("%d\t%q\t%d\n", i, r, r)
}
//...
//7 '世' 19990
//10 '界' 30028
for i, r := range []rune("Hello, 世界" ){
fmt.Printf("%d\t%q\t%d\n", i, r, r)
}
//...
//7 '世' 19990
//8 '界' 30028
4.2. Suffix Array
第一次看到有语言把后缀数组放进了标准库，关键放就放了，这个API设计的就像个玩具项目:
构造方法居然只支持New([]byte) 不支持string不支持 []rune等；
后缀数组理论上能做的事情很多，但是API只提供了个Lookup，同样只支持[]byte
玩具项目都没这么懒……
https://www.kancloud.cn/yetship/golang_standard_library_samples/527457
五、树相关，图相关
啥都没有
其他数据结构？用三方库吧！
其他的基本都没有，我写了一些放到自己的Copy-Paste Data Structures 项目里了
https://github.com/seeflood/Copy-Paste-Data-Structures
比较有名的三方数据结构库：
https://github.com/Workiva/go-datastructures
Q:比较有名的concurrent data structure库？
A:没有。
orcaman/concurrent-map这个连release都没有，pr也很久没合并过了，看着比较练手。
