map总结

key为什么是无序的

map在扩容之后,会发生key的搬迁,原来落在同一个bucket会分散在不同的bucket中,所以顺序有可能不同。

另一个是go设计如此,每次遍历的时候都会随机一个bucket编号来开始遍历,并且是从这个 bucket 的一个随机序号的 cell 开始遍历。

map不是线程安全的

在查找、赋值、遍历、删除的过程中都会检测写标志,一旦发现写标志置位(等于1),则直接 panic。赋值和删除函数在检测完写标志是复位之后,先将写标志位置位,才会进行之后的操作。

map删除过程

删除操作底层函数是mapdelete

针对不同的key,会有不同的操作函数。当删除的时候,会检查flag,如果发现flag是1,直接panic。这表明其他协程正在操作这个map。

首先会根据该key计算hash值,看落到那个bucket,同时检查该map是不是正在扩容,如果是在扩容,直接触发一次桶迁移操作。找到对应的key之后,对key和value进行清零操作。最后,就count数减1,并且将对应的tophash置为empty。

map底层实现原理

map的设计也被称为字典,他的任务就是设计一种数据结构来维护一个集合的数据,并且可以同时对数据进行增删改查操作。最主要的数据结构有两种:哈希查找表、搜索树。

哈希查找表用一个哈希函数将key通过一定的算法分配到不同的桶中(bucket,也就是数组中不同的index),这样,开销主要在哈希函数的计算和数组的查找上。

分配桶的时候有两种算法,一种是取模,将key的hash值与桶bucket取模,模是多少就落在哪个桶中。
另一种是位运算,将hash值与桶个数进行位运算,要保证每个bucket都能有元素,就必须保证桶个数为2的N次方。go的map采用的是位运算。

哈希表一般会碰上哈希值碰撞的问题,就是说不同的key被分配到同一个bukcet中。解决的方式有两种,一种是开放地址法,一种是拉链法。go中的map采用的拉链法。

开放地址法,就是当发生碰撞的时候,会在碰撞bucket的后面一次查找新的空位bucket存储。
拉链法指发生碰撞的时候,都存在该bucket中,然后在这个bucket中维护一个链表存储这些key。

map的源码实现如下:

type hmap struct {
    count int //元素个数,调用len(map)时直接返回该值
    flags uint8
    B uint8 //桶的个数的对数  比如B=4  桶个数为2^4=16个
    noverflow uint16 //溢出桶的个数
    hash0 uint32 //一个hash因子吧应该,计算key的hash值的时候会传入到hash函数中。
    buckets unsafe.Pointer //指向bucket数组的指针 大小为2^B 如果个数为0 就代表为nil
    oldbuckets unsafe.Pointer //旧桶的位置 扩容的时候,buckets 长度会是 oldbuckets 的两倍
    nevacuate uintptr //迁移桶的进度,小于此地址的 buckets 迁移完成
    extra *mapextra
}

buckets是一个指针,指向一个结构体:

type bmap struct {
    tophash [bucketCnt]unit8  //其实就是hash值的高8位
}

上面只是表面的bmap,编译的时候会编译成下面的结构体:

type bmap struct {
    topbits  [8]uint8  //高8
    keys     [8]keytype //
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

bmap就是我们常说的桶,桶里面最多装8个key,这些key之所以会落在同一个桶中,是因为进行hash运算后,hash结果是同一类的。在桶内,又根据计算出来的hash值的高8位来决定key到底落在了桶内的哪个位置。

map总结

key为什么是无序的

map在扩容之后,会发生key的搬迁,原来落在同一个bucket会分散在不同的bucket中,所以顺序有可能不同。

另一个是go设计如此,每次遍历的时候都会随机一个bucket编号来开始遍历,并且是从这个 bucket 的一个随机序号的 cell 开始遍历。

map不是线程安全的

在查找、赋值、遍历、删除的过程中都会检测写标志,一旦发现写标志置位(等于1),则直接 panic。赋值和删除函数在检测完写标志是复位之后,先将写标志位置位,才会进行之后的操作。

map删除过程

删除操作底层函数是mapdelete

针对不同的key,会有不同的操作函数。当删除的时候,会检查flag,如果发现flag是1,直接panic。这表明其他协程正在操作这个map。

首先会根据该key计算hash值,看落到那个bucket,同时检查该map是不是正在扩容,如果是在扩容,直接触发一次桶迁移操作。找到对应的key之后,对key和value进行清零操作。最后,就count数减1,并且将对应的tophash置为empty。

map底层实现原理

map的设计也被称为字典,他的任务就是设计一种数据结构来维护一个集合的数据,并且可以同时对数据进行增删改查操作。最主要的数据结构有两种:哈希查找表、搜索树。

go在程序启动期间,会判断当前cpu是否ase,如果支持,就采用的是ase hash函数。否则使用memhash。

哈希查找表用一个哈希函数将key通过一定的算法分配到不同的桶中(bucket,也就是数组中不同的index),这样,开销主要在哈希函数的计算和数组的查找上。

分配桶的时候有两种算法,一种是取模,将key的hash值与桶bucket取模,模是多少就落在哪个桶中。
另一种是位运算,将hash值与桶个数进行位运算,要保证每个bucket都能有元素,就必须保证桶个数为2的N次方。go的map采用的是位运算。

哈希表一般会碰上哈希值碰撞的问题,就是说不同的key被分配到同一个bukcet中。解决的方式有两种,一种是开放地址法,一种是拉链法。go中的map采用的拉链法。

开放地址法,就是当发生碰撞的时候,会在碰撞bucket的后面一次查找新的空位bucket存储。
拉链法指发生碰撞的时候,都存在该bucket中,然后在这个bucket中维护一个链表存储这些key。

map的源码实现如下:

type hmap struct {
    count int //元素个数,调用len(map)时直接返回该值
    flags uint8 //这个元素是判断当前是否有其他goroutine在操作这个map
    B uint8 //桶的个数的对数  比如B=4  桶个数为2^4=16个
    noverflow uint16 //溢出桶的个数
    hash0 uint32 //一个hash因子吧应该,计算key的hash值的时候会传入到hash函数中。
    buckets unsafe.Pointer //指向bucket数组的指针 大小为2^B 如果个数为0 就代表为nil
    oldbuckets unsafe.Pointer //旧桶的位置 扩容的时候,buckets 长度会是 oldbuckets 的两倍
    nevacuate uintptr //迁移桶的进度,小于此地址的 buckets 迁移完成
    extra *mapextra
}

buckets是一个指针,指向一个结构体:

type bmap struct {
    tophash [bucketCnt]unit8  //其实就是hash值的高8位
}

上面只是表面的bmap,编译的时候会编译成下面的结构体:

type bmap struct {
    topbits  [8]uint8  //高8
    keys     [8]keytype //
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

bmap就是我们常说的桶,桶里面最多装8个key,这些key之所以会落在同一个桶中,是因为进行hash运算后,hash结果是同一类的。在桶内,又根据计算出来的hash值的高8位来决定key到底落在了桶内的哪个位置。

269a7b4dee91ccf106430ee522d6ef6a

bmap是存放key/value的地方,其内部布局为:

其中:hob hash就是存储key经过Hash后的高8位,bmap中,key和value并不是以key/value key/value这些的形式存放,而是以key1,key2… value1,value2…这样的方式存放。

map扩容

使用hash表的目的就是为了快速查找到目标key,但是随着想map中添加key,发生碰撞的概率会越来越大,不同key落在同一个桶中的概率也越来越大。bucket中的8个位置也会逐渐被塞满,查找、删除,更新对应的key效率也会越来越慢。最理想的状况是一个bucket中只装一个key。就能达到O(1)的效率,这就是用空间换时间。go语言中一个bucket装载8个key,这同时又是用时间换空间。

当然,这样做要有个度,不然所有key都落入到一个bucket中,直接退化成一个链表,各种操作又变成了O(n),效率又下降下来了,所以map有一个指标,叫装载因子,其计算公式为:

loadFactor := count/(2^B)
// count就是hmap中的count
//B 就是hmap中的B 2^B就是桶的个数。

在向map中写入新的key的时候,会进行条件检测,当满足以下两个条件的时候,就会触发扩容规则:

  • 装载因子超过阈值,在go中,阈值定义的为6.5
  • overflow的bucket的数量过多:当 B 小于 15,也就是 bucket 总数 2^B 小于 2^15 时,如果 overflow 的 bucket 数量超过 2^B;当 B >= 15,也就是 bucket 总数 2^B 大于等于 2^15,如果 overflow 的 bucket 数量超过 2^15。

解释:

对于第一条,很好理解,每个bucket只会装载8个key,当装载因子大于6.5的时候表示8个坑位都快装满的了,查找,删除都会变得效率很低下。这个时候进行扩容是变得很有必要了。

对于第二条,其实是对第一条的补充,就是说在装载因子比较小的情况下,各个key比较分散,这时候 map 的查找和插入效率也很低,而第 1 点识别不出来这种情况。表面现象就是计算装载因子的分子比较小,即 map 里元素总数少,但是 bucket 数量多(真实分配的 bucket 数量多,包括大量的 overflow bucket)。造成这种情况可能有不停的插入、删除元素。先插入很多元素,导致创建了很多bucket,但是达不到第一种情况,未触发扩容。之后,再删除元素的总数量,再插入很多元素,导致创建很多overflow。

针对这两种不同的情况,有不同的扩容规则:

装载因子过大的扩容规则

针对装载因子过大,解决的办法很简单,就是直接增加bucket的个数,其规则是直接将B+1,也就是将桶的个数翻倍。注意,这个时候元素都在老的bucket中,还没迁移到新的bucket中来。

overflow数量过多

其实元素没那么多,但是 overflow bucket 数特别多,说明很多 bucket 都没装满。解决办法就是开辟一个新 bucket 空间,将老 bucket 中的元素移动到新 bucket,使得同一个 bucket 中的 key 排列地更紧密。这样,原来,在 overflow bucket 中的 key 可以移动到 bucket 中来。结果是节省空间,提高 bucket 利用率,map 的查找和插入效率自然就会提升。

具体做法就是:

由于 map 扩容需要将原有的 key/value 重新搬迁到新的内存地址,如果有大量的 key/value 需要搬迁,会非常影响性能。因此 Go map 的扩容采取了一种称为“渐进式”地方式,原有的 key 并不会一次性搬迁完毕,每次最多只会搬迁 2 个 bucket。

暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇