Go - map implement

[Petelin]

Go - map implement

https://tiancaiamao.gitbooks.io/go-internals/content/zh/02.3.html
https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/
https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics

这篇源于头条面试官问我map是怎么实现的，当时并没有看过。

面试官说go的实现很有特点，我在想这东西还能有什么特别的呢？

现在可以罗列一下比较special的点

• 渐进式扩容，保证延迟平稳
• 没有像Java一样用interface wrap， 也没有像C渣渣一样为每一个map的定义都rewrite出一个结构体。而是采用hmap + maptype 讲变化的部分抽象出来，就只需要对一个key,value对编译出来一个就行。 可以看出对性能，编译速度的考量。
• bucket的设计，一个key被hash之后，地位和桶掩码与之后当索引，高位用来在每一个bucket里充当索引快速判定key存不存在，index是什么。
• bmap的实现是keys，和values分别放在一起还有padding, 就是考虑了字节对齐，cache补齐伪共享
• 没有重用设freelist重用删除的结点。作者把这个加了一个TODO的注释，不过想了一下觉得这个做的意义不大。因为一方面，bucket大小并不一致，重用比较麻烦。另一方面，下层存储已经做过内存池的实现了，所以这里不做重用也会在内存分配那一层被重用的
• bucket直接key/value和间接key/value优化。这个优化做得蛮好的。注意看代码会发现，如果key或value小于128字节，则它们的值是直接使用的bucket作为存储的。否则bucket中存储的是指向实际key/value数据的指针
• 针对插入做了优化， 插入的时候不需要先找之前存的key的位置，只要有空位，就可以放进去，通过隐式的顺序覆盖掉老的key value。要注意删除的时候需要遍历一遍，删掉所有的key。 这种做法是对插入做了优化的，日常场景就是写读多，删除少的。