hashMap一般有两个实现方案：开放寻址法（往后错位）和拉链法（槽内是链表）。

go map 其实是用的拉链法，首先有一个hmap的结构，存放了 2^B 个桶。
map 的数据被置入一个由桶组成的有序数组中，每个桶最多可以存放 8 个 key/value，超了则会链接到额外的溢出桶。
基本数据结构是（桶数组 + 桶内的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值，后 B 位为桶的编号，前8位（tophash）为桶的位置。
通过key的tophash（key的hash高8位）和hash值，找到第一个可插入位置，如果桶满，创建一个溢出桶存储。
关于hash冲突：当两个不同的 key 落在同一个桶中，就是发生了哈希冲突。冲突的解决手段是采用链表法：在桶中，从前往后找到第一个空位进行插入。如果8个kv满了，那么当前桶就会连接到下一个溢出桶（bmap）。

1.2 数据访问

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

2. 扩容

2.1 二倍容量扩容

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

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

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

扩容流程：扩容的时候，新建一个新的桶，渐进式驱逐旧桶数据到新桶，完成后释放老桶。

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

2.2 等量扩容

溢出桶太多，影响了性能效率。这种扩容实际上是一种整理，元素会发生重排，但不会换桶。

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

2.3 扩容条件

1. 装载因子 > 6.5

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

2. 溢出桶的数量过多

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

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

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. 头脑风暴

Go 使用的是拉链法实现了hashmap。
map基本数据结构是桶数组 + 桶key-value数组 + 溢出的桶链表。
计算key的hash值，后 B 位为桶的编号，前8位为桶的位置。超过8个数据，放到溢出桶。
桶里有 8 个键值对，还有 tophash 快速定位置。
二倍扩容桶，扩容桶的时候有可能会迁移桶。相同容量扩容，实际上是一种碎片整理。元素会发生重排，但不会换桶。
扩容的时候，新建一个新的桶，渐进式驱逐旧桶数据到新桶，完成后释放老桶。

Levon's Blog

golang的map实现原理