从大学的课本里面,我们学到:hash 表其实就是将key 通过hash算法映射到数组的某个位置,然后把对应的val存放起来。
如果出现了hash冲突(也就是说,不同的key被映射到了相同的位置上时),就需要解决hash冲突。解决hash冲突的方法还是比较多的,比如说开放定址法,再哈希法,链地址法,公共溢出区等(复习下大学的基本知识)。
其中链地址法比较常见,下面是一个链地址法的常见模式:
position 指通过key 计算出的数组偏移量。例如当 position = 6 的位置已经填满kv后,再次插入一条相同position的数据将通过链表的方式插入到该条位置之后。
在php的array 中是这么实现的,golang中也基本是这么实现。下面我们学习下golang中map的实现。
golang的map中,首先把kv 分在了n个桶中,每个桶中的数据有8条(bucketcnt)。如果一个桶满了(overflow),也会采用链地址法解决hash 的冲突。
下面是定义一个hashmap的结构体:
type hmap struct { // 长度 count int // map 的标识, 下方做了定义 flags uint8 // 实际buckets 的长度为 2 ^ b b uint8 // 从bucket中溢出的数量,(存在extra 里面) noverflow uint16 // hash 种子,做key 哈希的时候会用到 hash0 uint32 // 存储 buckets 的地方 buckets unsafe.pointer // 迁移时oldbuckets中存放部分buckets 的数据 oldbuckets unsafe.pointer // 迁移的数量 nevacuate uintptr // 一些额外的字段,在做溢出处理以及数据增长的时候会用到 extra *mapextra } const ( // 有一个迭代器在使用buckets iterator = 1 // 有一个迭代器在使用oldbuckets olditerator = 2 // 并发写,通过这个标识报panic hashwriting = 4 samesizegrow = 8 ) type mapextra struct { overflow *[]*bmap oldoverflow *[]*bmap nextoverflow *bmap } type bmap struct { tophash [bucketcnt]uint8 }
表中除了对基本的hash数据结构做了定义外,还对数据迁移、扩容等操作做了定义,这里我们可以忽略,等学习到时我们再深入了解。
buckets 字段中是存储桶数据的地方。正常会一次申请至少2^n长度的数组,数组中每个元素就是一个桶。n 就是结构体中的b。这里面要注意以下几点:
// 根据key的类型取相应的hash算法 alg := t.key.alg hash := alg.hash(key, uintptr(h.hash0)) // 根据b拿到一个掩码 m := bucketmask(h.b) // 通过掩码以及hash指,计算偏移得到一个bucket b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
一个桶的示意图如下:
每个桶里面,可以放8个k,8个v,还有一个overflow指针(就是上面的next),用来指向下一个bucket 的地址。在每个bucket的头部,还会放置一个tophash,也就是bmap 结构体。这个数组里面存放的是key的hash值,用来对比我们key生成的hash和存出的hash是否一致(当然除了这个还有其他的用途,后面讲数据访问的时候会讲到)。 tophash中的数据,是从计算的hash值里面截取的。获取bucket 是用的低bit位的hash,tophash 使用的是高bit位的hash值(8位)
golang 实现的map比朴素的hashmap 在很多方面都有优化。
原文连接:https://www.cnblogs.com/-lee/p/12777241.html
如对本文有疑问, 点击进行留言回复!!
VSCode1.4 搭建Golang的开发调试环境(遇到很多问题)
网友评论