map 底层用hash表存储，hash 表中的基本单位是桶，每个桶最多存 8 个键值对，超了则会链接到额外的溢出桶。所以 Go map 基本数据结构是hash数组+桶内的key-value数组+溢出的桶链表。

1. 原理

https://github.com/golang/go/blob/master/src/runtime/map.go#L117C5-L117C5

 type hmap struct {
     count     int    // 元素的个数
     B         uint8  // buckets 数组的长度就是 2^B 个
     overflow uint16 // 溢出桶的数量
     buckets    unsafe.Pointer // 2^B个桶对应的数组指针
     oldbuckets unsafe.Pointer  // 发生扩容时，记录扩容前的buckets数组指针
     extra *mapextra //用于保存溢出桶的地址
 }
 
 type mapextra struct {
     overflow    *[]*bmap
     oldoverflow *[]*bmap
     nextOverflow *bmap
 }

 type bmap struct {
     tophash [bucketCnt]uint8
 }

 //编译期间会给它加料，动态地创建一个新的结构：
type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

1.1 底层结构

在go的map实现中，它的底层结构体是hmap，hmap（hashmap）里维护着若干个bucket数组。
Bucket数组中每个元素都是bmap结构，每个桶中保存了8个kv对，如果8个满了，又来了一个key落在了这个桶里，会使用overflow连接下一个桶(溢出桶)。
hmap这个结构体并不会存储实际的数据，实际存储数据的是bmap结构体。

1.1 数据获取过程

计算key的 hash值，后4位为桶的编号，前8位为桶的位置。
对比完整hash是否匹配，不匹配去溢出的桶寻找。

1.2 数据存放过程

计算key的 hash值，后4位为桶的编号，前8位为桶的位置。
通过key的tophash和hash值，找到第一个可插入位置，如果桶满，创建一个溢出桶存储。

关于hash冲突：当两个不同的 key 落在同一个桶中，就是发生了哈希冲突。冲突的解决手段是采用链表法：在桶中，从前往后找到第一个空位进行插入。如果8个kv满了，那么当前桶就会连接到下一个溢出桶（bmap）。

2. 扩容

2.1 相同容量扩容

由于map中不断的put和delete key，桶中可能会出现很多断断续续的空位，这些空位会导致连接的bmap溢出桶很长。

这种扩容实际上是一种整理,元素会发生重排，但不会换桶。

2.2 二倍容量扩容

这种2倍扩容是由于当前桶数组确实不够用了，发生这种扩容时，元素会重排，可能会发生桶迁移。

如图中所示，扩容前B=2（4个）。扩容后B=3（8个）。

假设一元素key的hash值后三位为101，那么由上文的介绍可知，在扩容前，由hash值的后两位来决定几号桶，即 01 所以元素在1号桶。在扩容发生后，由hash值得后三位来决定几号桶，即101所以元素会迁移到5号桶。

2.3 扩容条件

1. 装载因子 > 6.5

一个桶中最多有8个元素，当平均每个桶中的数据超过了6.5个，那就意味着当前容量要不足了，发生扩容。

2. 溢出桶的数量过多

当 B < 15 时，如果overflow的bucket数量超过 2^B。

当 B >= 15 时，overflow的bucket数量超过 2^15。

2.4 扩容转移

在我们的hmap结构中有一个oldbuckets，扩容刚发生时，会先将老数据存到这个里面。
每次对map进行删改操作时，会触发从oldbucket中迁移到bucket的操作【非一次性，分多次】
在扩容没有完全迁移完成之前，每次get或者put遍历数据时，都会先遍历oldbuckets，然后再遍历buckets。

3. map细节

3.1 map数据不可取址

type Student struct {
	Name string
	Age  int
}

// 编译错误
func f1() {
	m := map[int]Student{
		1: Student{Age: 15, Name: "jack"},
		2: Student{Age: 16, Name: "danny"},
		3: Student{Age: 17, Name: "andy"},
	}
	m[1].Name = "JACK"
}

// 可以修改
func f2() {
	m := map[int]*Student{
		1: &Student{Age: 15, Name: "jack"},
		2: &Student{Age: 16, Name: "danny"},
		3: &Student{Age: 17, Name: "andy"},
	}
	m[1].Name = "JACK"
}

为什么go中要禁止对map的元素进行取址呢？这是因为map 会随着元素数量的增长而重新分配更大的内存空间，会导致之前的地址无效。

3.2 线程不安全

在同一时间点，两个 goroutine 对同一个map进行读写操作是不安全的。举个栗子：

某map桶数量为4，即B=2。此时 goroutine1来插入key1， goroutine2来读取 key2. 可能会发生如下过程：

① goroutine2 计算key2的hash值,B=2，并确定桶号为1。

② goroutine1添加key1，触发扩容条件。

③ B=B+1=3, buckets数据迁移到oldbuckets。

④ goroutine2从桶1中遍历，获取数据失败。

在工作中，当我们涉及到对一个map进行并发读写时，一般采用的做法是采用golang中自带的mutex锁。

3.3 遍历无序

map 在扩容后，会发生 key 的搬迁，原来落在同一个 bucket 中的 key，搬迁后，有些 key 就要远走高飞了（bucket 序号加上了 2^B）。而遍历的过程，就是按顺序遍历 bucket，同时按顺序遍历 bucket 中的 key。搬迁后，key 的位置发生了重大的变化，有些 key 飞上高枝，有些 key 则原地不动。这样，遍历 map 的结果就不可能按原来的顺序了。

golang为了让程序员不依赖这种不可靠的保证，就干脆遍历的时候加入随机数，然后不管什么时候遍历，顺序都是不保证的。

4. 头脑风暴

map基本数据结构是 hashmap + key-value 的 bmap 数组 + 溢出的桶链表。
hmap（hashmap）维护一个桶数组，数组的每个元素是一个bmap。
bmap 有 8个kv 对，多了就用增加一个溢出桶，bmap存着key value，和下一个溢出桶的地址。
碎片整理桶，二倍扩容桶，扩容桶的时候有可能会迁移桶。

Levon's Blog

golang的map实现原理