欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

总结golang之map

程序员文章站 2022-03-15 15:15:07
...

0x01 map基本操作

// 1. 声明
var m map[string]int 

// 2. 初始化,声明之后必须初始化才能使用
// 向未初始化的map赋值引起 panic: assign to entry in nil map.
m = make(map[string]int)
m = map[string]int{}

// 1&2. 声明并初始化
m := make(map[string]int)
m := map[string]int{}

// 3. 增删改查
m["route"] = 66
delete(m, "route") // 如果key不存在什么都不做
i := m["route"] // 三种查询方式,如果key不存在返回value类型的零值
i, ok := m["route"]
_, ok := m["route"]

// 4. 迭代(顺序不确定)
for k, v := range m { 
    use(k, v)
}

// 5. 有序迭代
import "sort"
var keys []string
for k, _ := range m {
    keys = append(keys, k)
}
sort.Strings(keys)
for _, k := range keys {
    use(k, m[k]
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

0x02 map键类型

The key can be any type for which the equality operator is defined.

支持 == 操作符的类型有:

  • boolean,
  • numeric,
  • string,
  • pointer,
  • channel,
  • interface(as long as dynamic type supports equality),
  • 以及只包含上述类型arraystruct

不支持 == 操作符的类型有:

  • slice,
  • map,
  • func,

补充

  1. 不像Java可以为class自定义hashcode方法,以及C++可以重载==操作符,golang map**不支持**==重载或者使用自定义的hash方法。因此,如果想要把struct用作map的key,就必须保证struct不包含slice, map, func
  2. golang为uint32、uint64、string提供了fast access,使用这些类型作为key可以提高map访问速度,详见hashmap_fast.go

0x03 map并发

map不是并发安全的,通常使用sync.RWMutex保护并发map

// 声明&初始化
var counter = struct {
    sync.RWMutex // gard m
    m map[string]int
}{m:make(map[string]int)}
// 读锁
counter.RLock()
counter.m["route"]
counter.RUnlock()
// 写锁
counter.Lock()
counter.m["route"]++
counter.Unlock()
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

0x04 map小技巧

4.1. 利用value类型的零值

visited := map[*Node]bool
if visited[node] { // bool类型0值为false,所以不需要检查ok
    return
}

likes := make(map[string][]*Person)
for _, p range people {
    for _, l range p.Likes {
        // 向一个nil的slice增加值,会自动allocate一个slice
        likes[l] = append(likes[l], p)
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

4.2. map[k1]map[k2]v 对比 map[struct{k1, k2}]v

// map[k1]map[k2]v
hits := make(map[string]map[string]int)
func add(m map[string]map[string]int, path, country string) {
    mm, ok := m[path]
    if !ok {
        mm = make(map[string]int) // 需要检查、创建子map
        m[path] = mm
    }
    mm[country]++
}
add(hits, "/", "cn")
n := hits["/"]["cn"]

// map[struct{k1, k2}]v
type Key struct {
    Path, Country string
}
hits := make(map[Key]int)
hits[Key{"/", "cn"}]++
n := hits[Key{"/", "cn"}]
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

0x05 map实现细节浅析

5.1. 如何计算hash值

golang为每个类型定义了类型描述器_type,并实现了hashable类型的_type.alg.hash_type.alg.equal

type typeAlg struct {
    // function for hashing objects of this type
    // (ptr to object, seed) -> hash
    hash func(unsafe.Pointer, uintptr) uintptr
    // function for comparing objects of this type
    // (ptr to object A, ptr to object B) -> ==?
    equal func(unsafe.Pointer, unsafe.Pointer) bool
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

5.2. map实现结构

map的实现主要有三个struct,

  1. maptype用来保存map的类型信息,包括key、elem(value)的类型描述器,keysize,valuesize,bucketsize等;
  2. hmap - A header for a Go map. hmap保存了map的实例信息,包括count,buckets,oldbuckets等;buckets是bucket的首地址,用hash值的低h.B位hash & (uintptr(1)<<h.B - 1)计算出key所在bucket的index; 
    总结golang之map
  3. bmap - A bucket for a go map. bmap只有一个域tophash [bucketCnt]uint8,它保存了key的hash值的高8位uint8(hash >> (sys.PtrSize*8 - 8))一个bucket包括一个bmap(tophash数组),紧跟的bucketCnt个keys和bucketCnt个values,以及一个overfolw指针。 
    总结golang之map

makemap根据maptype中的信息初始化hmap

func makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap {
    ...
    // initialize Hmap
    if h == nil {
        h = (*hmap)(newobject(t.hmap))
    }
    h.count = 0
    h.B = B
    h.flags = 0
    h.hash0 = fastrand()
    h.buckets = buckets
    h.oldbuckets = nil
    h.nevacuate = 0
    h.noverflow = 0
    return h
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

5.3. 如何访问map

golang的maptype保存了key的类型描述器,以供访问map时调用key.alg.hashkey.alg.equal

type maptype struct {
    key           *_type
    elem          *_type
    ...
}
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    // 并发访问检查
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    // 计算key的hash值
    alg := t.key.alg
    hash := alg.hash(key, uintptr(h.hash0)) // alg.hash

    // 计算key所在的bucket的index
    m := uintptr(1)<<h.B - 1
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))

    // 计算tophash
    top := uint8(hash >> (sys.PtrSize*8 - 8))
    ...
    for {
        for i := uintptr(0); i < bucketCnt; i++ {
            // 检查top值
            if b.tophash[i] != top {
                continue
            }
            // 取key的地址
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if alg.equal(key, k) { // alg.equal
                // 取value得地址
                v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
            }
        }
        ...
        if b == nil {
            // 返回零值
            return unsafe.Pointer(&zeroVal[0])
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

5.4. map扩张

这部分留待以后有机会再续。这里暂时附上Keith Randall的slide作为参考。 
总结golang之map

0x06 map建议

  • 如果知道size,预先分配资源make(map[int]int, 1000)
  • uint32, uint64, string作为键,非常快
  • 清理map:for k:= range m { delete(m, k) }
  • key和value中没有指针可以使GC scanning更快

https://blog.csdn.net/Soooooooo8/article/details/70163475

 

参考 
Go msps in action 
hashmap.go type.go 
GopherCon 2016: Keith Randall - Inside the Map Implementation

相关标签: go