Go数据结构02-Map

2022-11-06  本文已影响0人  王侦

映射是一种数据结构，用于存储一系列无序的键值对。

映射是一个集合，可以使用类似处理数组和切片的方式迭代，但映射是无序的集合，每次迭代映射的时候顺序也可能不一样。

1.使用

func testCreate() {
    colors := make(map[string]string) //创建一个空映射
    colors["Red"] = "#da1337"         //赋值
    fmt.Println(colors)

    //var colors2 map[string]string
    //colors2["Red"] = "#da1337" //error

    value, ok := colors["Blue"] //判断键是否存在
    if ok {
        fmt.Println(value)
    }

    value = colors["Blue"] //判断读取到的值是否空值
    if value != "" {
        fmt.Println(value)
    }
}

func removeColor(colors map[string]string, key string) {
    delete(colors, key)
}

func testRemove() {
    colors := map[string]string{
        "AliceBlue": "#f0f8ff",
        "Coral":     "#ff7F50",
    }

    for key, value := range colors {
        fmt.Printf("Key: %s Value: %s\n", key, value)
    }
    fmt.Println("----------------")

    removeColor(colors, "Coral")

    for key, value := range colors {
        fmt.Printf("Key: %s Value: %s\n", key, value)
    }
}

输出结果：

map[Red:#da1337]
----------------
Key: Coral Value: #ff7F50
Key: AliceBlue Value: #f0f8ff
----------------
Key: AliceBlue Value: #f0f8ff

2.内存数据结构源码

src/runtime/map.go

type hmap struct {
 count     int       //元素个数
 flags     uint8     //标记位
 B         uint8     //buckets的对数 log_2
 noverflow uint16    //overflow的bucket的近似数
 hash0     uint32    //hash种子
 buckets    unsafe.Pointer //指向buckets数组的指针，数组个数为2^B
 oldbuckets unsafe.Pointer //扩容时使用，buckets长度是oldbuckets的两倍
 nevacuate  uintptr  //扩容进度，小于此地址的buckets已经迁移完成
 extra *mapextra     //扩展信息
}

//当map的key和value都不是指针，并且size都小于128字节的情况下，
// 会把 bmap 标记为不含指针，这样可以避免gc时扫描整个hmap。
// 但是，我们看bmap其实有一个overflow的字段，是指针类型的，
// 破坏了bmap不含指针的设想，这时会把overflow移动到extra字段来。
type mapextra struct {
 overflow    *[]*bmap
 oldoverflow *[]*bmap
 nextOverflow *bmap
}

// bucket
type bmap struct {
 tophash [bucketCnt]uint8 //bucketCnt = 8
 // keys     [8]keytype
 // values   [8]valuetype
 // pad      uintptr
 // overflow uintptr
}

bmap就是桶的数据结构，每个桶最多存储8个key-value对，所有的key都是经过hash后有相同的尾部，在桶内，根据hash值的高8位来决定桶中的位置。

注意到key和value是各自在一起的，不是key/value/key/value/...的方式，这样的好处是某些情况下可以省略padding字段，节省内存空间

如map[int64]int8，按照key/value/key/value/... 这样的模式存储，每一个key/value对之后都要额外 padding7个字节；而将所有的key，value 分别绑定到一起，key/key/.../value/value/...，只需在最后添加padding。

每个bucket设计成最多只能放8个key-value对，如果有第9个 key-value落入当前的bucket，那就需要再构建一个bucket，通过overflow指针连接起来。

编译期间会给它加料，动态地创建一个新的结构

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

3.初始化

底层调用makemap函数，计算得到合适的B，map容量最多可容纳6.5*2^B个元素，6.5为装载因子阈值常量。装载因子的计算公式是：装载因子=填入表中的元素个数/散列表的长度，装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

func makemap(t *maptype, hint int, h *hmap) *hmap {
//边界校验
  if hint < 0 || hint > int(maxSliceCap(t.bucket.size)) {
    hint = 0
  }

// initialize Hmap
  if h == nil {
    h = new(hmap)
  }
//生成hash种子
  h.hash0 = fastrand()

  // find size parameter which will hold the requested # of elements
  B := uint8(0)
//计算得到合适的B
  for overLoadFactor(hint, B) {
    B++
  }
  h.B = B

  // allocate initial hash table
  // if B == 0, the buckets field is allocated lazily later (in mapassign)
  // If hint is large zeroing this memory could take a while.
//申请桶空间  
if h.B != 0 {
    var nextOverflow *bmap
    h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
    if nextOverflow != nil {
      h.extra = new(mapextra)
      h.extra.nextOverflow = nextOverflow
    }
  }

  return h
}
//常量loadFactorNum=13 ，loadFactorDen=2
func overLoadFactor(count int, B uint8) bool {
  return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)

makemap函数会通过 fastrand 创建一个随机的哈希种子，然后根据传入的 hint 计算出需要的最小需要的桶的数量，最后再使用 makeBucketArray创建用于保存桶的数组，这个方法其实就是根据传入的 B 计算出的需要创建的桶数量在内存中分配一片连续的空间用于存储数据，在创建桶的过程中还会额外创建一些用于保存溢出数据的桶，数量是 2^(B-4) 个。初始化完成返回hmap指针。

4.查找

Go 语言中读取 map 有两种语法：带 comma 和 不带 comma。当要查询的 key 不在 map 里，带 comma 的用法会返回一个 bool 型变量提示 key 是否在 map 中；而不带 comma 的语句则会返回一个 value 类型的零值。如果 value 是 int 型就会返回 0，如果 value 是 string 类型，就会返回空字符串。

value := m["name"]
fmt.Printf("value:%s", value)

value, ok := m["name"]
  if ok {
    fmt.Printf("value:%s", value)
  }

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)

查找过程：

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  //...
  // 如果 h 什么都没有，返回零值
  if h == nil || h.count == 0 {
    return unsafe.Pointer(&zeroVal[0])
  }
  // 写和读冲突
  if h.flags&hashWriting != 0 {
    throw("concurrent map read and map write")
  }
  // 不同类型 key 使用的 hash 算法在编译期确定
  alg := t.key.alg
  // 计算哈希值，并且加入 hash0 引入随机性
  hash := alg.hash(key, uintptr(h.hash0))
  // 比如 B=5，那 m 就是31，二进制是全 1
  // 求 bucket num 时，将 hash 与 m 相与，
  // 达到 bucket num 由 hash 的低 8 位决定的效果
  m := bucketMask(h.B)
  // b 就是 bucket 的地址
  b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
  // oldbuckets 不为 nil，说明发生了扩容
  if c := h.oldbuckets; c != nil {
    // 如果不是同 size 扩容（看后面扩容的内容）
    // 对应条件 1 的解决方案
    if !h.sameSizeGrow() {
      // 新 bucket 数量是老的 2 倍
      m >>= 1
    }
    // 求出 key 在老的 map 中的 bucket 位置
    oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
    // 如果 oldb 没有搬迁到新的 bucket
    // 那就在老的 bucket 中寻找
    if !evacuated(oldb) {
      b = oldb
    }
  }
  // 计算出高 8 位的 hash
  // 相当于右移 56 位，只取高8位
  top := tophash(hash)
  //开始寻找key
  for ; b != nil; b = b.overflow(t) {
    // 遍历 8 个 bucket
    for i := uintptr(0); i < bucketCnt; i++ {
      // tophash 不匹配，继续
      if b.tophash[i] != top {
        continue
      }
      // tophash 匹配，定位到 key 的位置
      k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
      // key 是指针
      if t.indirectkey {
        // 解引用
        k = *((*unsafe.Pointer)(k))
      }
      // 如果 key 相等
      if alg.equal(key, k) {
        // 定位到 value 的位置
        v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
        // value 解引用
        if t.indirectvalue {
          v = *((*unsafe.Pointer)(v))
        }
        return v
      }
    }
  }
  return unsafe.Pointer(&zeroVal[0])
}

5.赋值操作（插入操作）

m := make(map[int32]int32)
m[0] = 6666666

源码是：

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {

具体流程：

6.扩容

6.1 bucket状态

// 空的 cell，也是初始时 bucket 的状态
empty  = 0

// 空的 cell，表示 cell 已经被迁移到新的 bucket
evacuatedEmpty = 1

// key,value 已经搬迁完毕，但是 key 都在新 bucket 前半部分，
evacuatedX  = 2

// 同上，key 在后半部分
evacuatedY  = 3

// tophash 的最小正常值
minTopHash  = 4

为了避免计算出的topHash与minTopHash 冲突，底层做了相关操作：

func tophash(hash uintptr) uint8 {
  top := uint8(hash >> (sys.PtrSize*8 - 8))
  if top < minTopHash {
    top += minTopHash
  }
  return top
}

当一个 cell 的 tophash 值小于 minTopHash 时，标志这个 cell 的迁移状态。

6.2 触发 map 扩容的时机

装载因子。loadFactor := count/(2^B)

count 就是 map 的元素个数，2^B 表示 bucket 数量。

扩容的时机：

源码在mapassign，对应扩容条件的源码如下

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  ...
  //触发扩容的时机
  if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
    hashGrow(t, h)
    goto again // Growing the table invalidates everything, so try again
  }
  ...
}

// 装载因子超过 6.5
func overLoadFactor(count int, B uint8) bool {
  return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// overflow buckets 太多
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
  if B > 15 {
    B = 15
  }
  return noverflow >= uint16(1)<<(B&15)
}

对应的扩容方法：

优化：渐进式搬迁

调整前：



调整后：扩容完成后，overflow bucket 消失了，key 都集中到了一个 bucket，更为紧凑了，提高了查找的效率。


7.遍历操作

为什么遍历 map 是无序的？

8.删除操作

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {

删除过程：

9.并发操作

map 并不是一个线程安全的数据结构。同时读写一个 map 是不安全的，如果被检测到，会直接 panic。

解决方法1：读写锁 sync.RWMutex。
解决方法2：使用golang提供的 sync.Map

参考文档

上一篇 下一篇

猜你喜欢

热点阅读