锐客网

  1. 首页 > 睿知 > it技术 > >

go语言map函数 go语言中的map( 二 )

IT技术函数


golang中map是一个kv对集合 。底层使用hash table，用链表来解决冲突  ， 出现冲突时，不是每一个key都申请一个结构通过链表串起来，而是以bmap为最小粒度挂载 ， 一个bmap可以放8个kv 。在哈希函数的选择上，会在程序启动时，检测 cpu 是否支持 aes，如果支持，则使用 aes hash，否则使用 memhash 。
map有3钟初始化方式，一般通过make方式创建
map的创建通过生成汇编码可以知道 ， make创建map时调用的底层函数是 runtime.makemap。如果你的map初始容量小于等于8会发现走的是 runtime.fastrand 是因为容量小于8时不需要生成多个桶，一个桶的容量就可以满足
makemap函数会通过fastrand创建一个随机的哈希种子，然后根据传入的hint计算出需要的最小需要的桶的数量，最后再使用makeBucketArray 创建用于保存桶的数组，这个方法其实就是根据传入的B计算出的需要创建的桶数量在内存中分配一片连续的空间用于存储数据 ， 在创建桶的过程中还会额外创建一些用于保存溢出数据的桶 ， 数量是2^(B-4)个 。初始化完成返回hmap指针 。
找到一个 B，使得 map 的装载因子在正常范围内
Go 语言中读取 map 有两种语法：带 comma 和 不带 comma 。当要查询的 key 不在 map 里 ， 带 comma 的用法会返回一个 bool 型变量提示 key 是否在 map 中；而不带 comma 的语句则会返回一个 value 类型的零值 。如果 value 是 int 型就会返回 0，如果 value 是 string 类型 ， 就会返回空字符串 。
map的查找通过生成汇编码可以知道，根据 key 的不同类型 ， 编译器会将查找函数用更具体的函数替换 ， 以优化效率：
函数首先会检查 map 的标志位 flags 。如果 flags 的写标志位此时被置 1 了，说明有其他协程在执行“写”操作，进而导致程序 panic 。这也说明了 map 对协程是不安全的 。
key经过哈希函数计算后，得到的哈希值如下（主流64位机下共 64 个 bit 位）：
m: 桶的个数
从buckets 通过 hashm 得到对应的bucket，如果bucket正在扩容，并且没有扩容完成，则从oldbuckets得到对应的bucket
计算hash所在桶编号：
用上一步哈希值最后的 5 个 bit 位，也就是01010，值为 10，也就是 10 号桶（范围是0~31号桶）
计算hash所在的槽位:
用上一步哈希值哈希值的高8个bit 位，也就是 10010111，转化为十进制，也就是151 ， 在 10 号 bucket 中寻找** tophash 值（HOB hash）为 151* 的 槽位**，即为key所在位置，找到了 2 号槽位，这样整个查找过程就结束了 。
如果在 bucket 中没找到 ， 并且 overflow 不为空，还要继续去 overflow bucket 中寻找，直到找到或是所有的 key 槽位都找遍了 ， 包括所有的 overflow bucket 。
通过上面找到了对应的槽位，这里我们再详细分析下key/value值是如何获取的：
bucket 里 key 的起始地址就是 unsafe.Pointer(b)+dataOffset 。第 i 个 key 的地址就要在此基础上跨过 i 个 key 的大?。欢颐怯种溃?value 的地址是在所有 key 之后，因此第 i 个 value 的地址还需要加上所有 key 的偏移 。
通过汇编语言可以看到，向 map 中插入或者修改 key，最终调用的是mapassign函数 。
实际上插入或修改 key 的语法是一样的 ， 只不过前者操作的 key 在 map 中不存在，而后者操作的 key 存在 map 中 。
mapassign 有一个系列的函数，根据 key 类型的不同 ， 编译器会将其优化为相应的“快速函数” 。
我们只用研究最一般的赋值函数mapassign。
map的赋值会附带着map的扩容和迁移，map的扩容只是将底层数组扩大了一倍，并没有进行数据的转移 ， 数据的转移是在扩容后逐步进行的，在迁移的过程中每进行一次赋值（access或者delete）会至少做一次迁移工作 。

推荐阅读


上一篇：盘锦sap接口开发，sap接口开发与实现

下一篇：儿童仓鼠大冒险游戏下载，小仓鼠闯关大冒险视频