下图展示一个拥有4个bucket的map：
本例中, hmap.B=2 ， 而hmap.buckets长度是2^B为4.元素经过哈希运算后会落到某个bucket中进行存储查找过程类似bucket 很多时候被翻译为桶，所谓的 哈希桶 实际上就是bucket 数据结构每个bucket可以存储8个键值对
tophash是个长度为8的数组，**哈希值相同的键（准确的说是哈希值低位相同的键）**存入当前bucket时会将哈希值的高位存储在该数组中，以方便后续匹配
data区存放的是key-value数据，存放顺序是key/key/key/…value/value/value，如此存放是为了节省字节对齐带来的空间浪费
overflow 指针指向的是下一个bucket，据此将所有冲突的键连接起来
注意：上述中data和overflow并不是在结构体中显示定义的，而是直接通过指针运算进行访问的
示例下图展示bucket存放8个key-value对：
哈希冲突 当有两个或以上数量的键被哈希到了同一个bucket时，我们称这些键发生了冲突Go使用链地址法来解决键冲突由于每个bucket可以存放8个键值对，所以同一个bucket存放超过8个键值对时就会再创建一个键值对，用类似链表的方式将bucket连接起来 示例下图展示产生冲突后的map：
bucket数据结构指示下一个bucket的指针称为overflow bucket，意为当前bucket盛不下而溢出的部分哈希冲突并不是好事情，它降低了存取效率好的哈希算法可以保证哈希值的随机性但冲突过多也是要控制的 负载因子用于衡量一个哈希表冲突情况，公式为：
// 负载因子 = 键数量/bucket数量
// 例如，对于一个bucket数量为4，包含4个键值对的哈希表来说
// 这个哈希表的负载因子为1
新建一个bucket，长度是原来的2倍，然后旧bucket数据搬迁到新的bucket。一次性搬迁将会造成比较大的延时，Go采用逐步搬迁策略：即每次访问map时都会触发一次搬迁，每次搬迁2个键值对。
示例当前map存储了7个键值对，只有1个bucket。此负载因子为7。再次插入数据时将会触发扩容 *** 作，扩容之后再将 新插入键写入新的bucket
当第8个键值对插入时，将会触发扩容，扩容后示意图如下：
hmap数据结构中oldbuckets成员指原bucketbuckets指向了新申请的bucket新的键值对被插入新的 bucket中后续对map的访问 *** 作会触发迁移，将oldbuckets中的键值对逐步的搬迁过来当oldbuckets中的键 值对全部搬迁完毕后，删除oldbuckets搬迁完成后的示意图如下：
数据搬迁过程中 原bucket中的键值对将存在于新bucket的前面新插入的键值对将存在于新bucket的后面实际搬迁过程中比较复杂
等量扩容 所谓等量扩容，实际上并不是扩大容量buckets数量不变，重新做一遍类似增量扩容的搬迁动作把松散的键值对重新排列一次，以使bucket的使用率更高，进而保证更快的存取在极端场景下 比如不断的增删，而键值对正好集中在一小部分的bucket这样会造成overflow的bucket数量增多，但负载因子又不高从而无法执行增量搬迁的情况如下图所示：
上图可见
overflow的buckt中大部分是空的，访问效率会很差。此时进行一次等量扩容，即buckets数量不变经过重新组织后overflow的bucket数量会减少，即节省了空间又会提高访问效率 查找过程查找过程如下：
跟据key值算出哈希值取哈希值低位与hmpa.B取模确定bucket位置取哈希值高位，在tophash数组中查询如果tophash[i]中存储值也哈希值相等，则去找到该bucket中的key值进行比较当前bucket没有找到，则继续从下个overflow的bucket中查找如果当前处于搬迁过程，则优先从oldbuckets查找注：如果查找不到，也不会返回空值，而是返回相应类型的0值。
插入过程新员素插入过程如下：
跟据key值算出哈希值取哈希值低位与hmap.B取模确定bucket位置查找该key是否已经存在，如果存在则直接更新值如果没找到将key，将key插入 参考 map的整体结构图 Golang中map的底层实现是一个散列表
因此实现map的过程实际上就是实现散表的过程 在这个散列表中
主要出现的结构体有两个
一个叫hmap(a header for a go map)一个叫bucket 这两种结构的样子分别如下所示：
hmap
图中有很多字段但是便于理解map的架构
你只需要关心的只有一个就是标红的字段：buckets数组 Golang的map中用于存储的结构是bucket数组而bucket(即bmap)的结构是怎样的呢？
bucket
相比于hmapbucket的结构显得简单一些
我们使用的map中的key和value就存储在这里（中间）。“高位哈希值”数组记录的是当前bucket中key相关的“索引”
稍后会详细叙述 还有一个字段是一个指向扩容后的bucket的指针
使得bucket会形成一个链表结构例如下图：
由此看出hmap和bucket的关系是这样的：
而bucket又是一个链表所以整体的结构应该是这样的：
哈希表的特点是会有一个哈希函数
对你传来的key进行哈希运算得到唯一的值 一般情况下都是一个数值Golang的map中也有这么一个哈希函数
Golang把求得的值按照用途一分为二：
高位和低位 如图所示 蓝色为高位红色为低位 然后 低位用于寻找当前key属于hmap中的哪个bucket而高位用于寻找bucket中的哪个key 上文中提到：
bucket中有个属性字段是“高位哈希值”数组这里存的就是蓝色的高位值
用来声明当前bucket中有哪些“key”便于搜索查找 需要特别指出的一点是：
我们map中的key/value值都是存到同一个数组中的并不是key0/value0/key1/value1的形式这样做的好处是：
在key和value的长度不同的时候可以消除padding带来的空间浪费。 现在
我们可以得到Go语言map的整个的结构图了：
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）