嗨，我是小魔童哪吒，我们来回顾一下上一次分享的内容

  • 分享了切片是什么
  • 切片和数组的区别
  • 切片的数据结构
  • 切片的扩容原理
  • 空切片 和 nil 切片的区别

要是对 GO 的slice 原理还有点兴趣的话，欢迎查看文章 GO 中 slice 的实现原理

map 是什么？ 

hash 表hash 表
C/C++key - value
C/C++
C/C++
C/C++unordered_maphash 表

map 的数据结构是啥样的？

前面说到的 GO 中 string 实现原理，GO 中 slice 实现原理， 都会对应有他们的底层数据结构

哈，没有例外，今天说的 map 必然也有自己的数据结构， 相对来说会比前者会多一些成员，我们这就来看看吧

src/runtime/map.go
hmap
extramapextra
bmap

这个结构是，GO map 里面桶的实现结构，

源码的意思是这样的：

tophashminTopHash

这里源码中有一个注意点：

实际上分配内存的时候，内存的前8个字节是 bmap ，后面跟着 8 个 key 、 8 个 value 和 1 个溢出指针

我们来看看图吧

GO 中 map 底层数据结构成员相对比 string 和 slice 多一些，不过也不是很复杂，咱们画图来瞅瞅

hmaphmap.buckets
B = 3
key / value

如果超出了 8 个的话， 那么就会溢出，此时就会链接到额外的溢出桶

理解起来是这个样子的

严格来说，每一个桶里面只会有8 个键值对，若多余 8 的话，就会溢出，溢出的指针就会指向另外一个桶对应的 8个键值对

bmap
  • tophash 是个长度为8的数组

哈希值低位相同的键存入当前bucket时，会将哈希值的高位存储在该数组中，便于后续匹配

key-value

存放顺序是8个key依次排开，8个value依次排开，这是为啥呢？

因为GO 里面为了字节对齐，节省空间

  • overflow 指针，指向的是另外一个 桶

这里是解决了 2 个问题，第一是解决了溢出的问题，第二是解决了冲突问题

啥是哈希冲突？ 

hash 冲突hash 冲突

关键字值不同的元素可能会映射到哈希表的同一地址上就会发生哈希冲突

简单对应到我们的上述数据结构里面来，我们可以这样理解

当有两个或以上的键(key)被哈希到了同一个bucket时，这些键j就发生了冲突

hash 冲突
  • 开放定址法

当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。 沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。 查找时探查到开放的 地址则表明表中无待查的关键字，即查找失败。

  • 再哈希法

同时构造多个不同的哈希函数。

  • 链地址法

将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i 个单元中 因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

  • 建立公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

细心的小伙伴看到这里，有没有看出来 GO 中的map 是如何解决 hash 冲突的？

没错，GO 中的map 解决hash 冲突 就是使用的是 链地址法来解决键冲突

再来一个图，咱们看看他是咋链 的，其实咱们上述说的溢出指针就已经揭晓答案了

bucketbucketbucket
map
map
mapmap

GO 中 map 可以扩容吗？

当然可以扩容，扩容分为如下两种情况：

  • 增量扩容
  • 等量扩容
map
map
bucket2^15

这里说一下啥是负载因子呢？

有这么一个公式，来计算负载因子：

负载因子 = 键的数量 / bucket 数量

举个例子：

bucket
rehash

例如

  • 哈希因子太小的话，这就表明空间利用率低
  • 哈希因子太大的话，这就表明哈希冲突严重，存取效率比较低
6.5

啥是增量扩容

就是当负载因子过大，也就是哈希冲突严重的时候，会做如下 2 个步骤

double

可是我们想一想，如果有上千万，上亿级别键值对，那么迁移起来岂不是很耗时

map

咱们画个图来瞅瞅

bucket0key-value

实际上是不会触发扩容的，因为GO 的默认负载因子是 6.5

但是我们为了演示方便，模拟一下扩容的效果

bucketbucket1

最后，再做一个迁移，将旧的bucket，迁移到新的bucket上面来，删掉旧的bucket

根据上述的数据搬迁图，我们可以知道

bucketbucket
bucket

啥是等量扩容

等量扩容，等量这个名字感觉像是，扩充的容量和原来的容量是一一对齐的，也就是说成倍增长

buckets
bucket
buckets
buckets

总结

  • 分享 map 是什么
  • map 的底层数据结构是啥样的
  • 什么是哈希冲突，并且如何解决
  • GO 的map 扩容方式，以及画图进行理解

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里，下一次 GO 中 Chan 的实现原理分享

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是小魔童哪吒，欢迎点赞关注收藏，下次见~