go中的数据结构-字典map的使⽤及原理
1. map的使⽤
  golang中的map是⼀种数据类型，将键与值绑定到⼀起，底层是⽤哈希表实现的，可以快速的通过键到对应的值。
  类型表⽰：map[keyType][valueType] key⼀定要是可⽐较的类型（可以理解为⽀持==的操作），value可以是任意类型。
  初始化：map只能使⽤make来初始化，声明的时候默认为⼀个为nil的map，此时进⾏取值，返回的是对应类型的零值（不存在也是返回零值）。添加元素⽆任何意义，还会导致运⾏时错误。向未初始化的map赋值引起 panic: assign to entry in nil map。
1 package main
2
3 import (
4"fmt"
5 )
6
7// bool 的零值是false
8var m map[int]bool
9 a, ok := m[1]
10 fmt.Println(a, ok) // false  false
11
12// int 的零值是0
13var m map[int]int
14 a, ok := m[1]
15 fmt.Println(a, ok) // 0  false
16
17
18 func main() {
19var agemap[string]int
20if age== nil {
21        fmt.Println("map is nil.")
22        age= make(map[string]int)
23    }
24 }
  清空map：对于⼀个有⼀定数据的集合 exp，清空的办法就是再次初始化: exp = make(map[string]int)，如果后期不再使⽤该map，则可以直接：exp= nil 即可，但是如果还需要重复使⽤，则必须进⾏make初始化，否则⽆法为nil的map添加任何内容。
  属性：与切⽚⼀样，map 是引⽤类型。当⼀个 map 赋值给⼀个新的变量，它们都指向同⼀个内部数据结构。因此改变其中⼀个也会反映到另⼀个。作为形参或返回参数的时候，传递的是地址的拷贝，扩容时也不会改变这个地址。
1 func main() {
2    exp := map[string]int{
3"steve": 20,
4"jamie": 80,
5    }
6    fmt.Println("Ori exp", age)
7    newexp:= exp
8    newexp["steve"] = 18
9    fmt.Println("exp changed", exp)
10 }
11
12//Ori age map[steve:20 jamie:80]
13//age changed map[steve:18 jamie:80]
  遍历map：map本⾝是⽆序的，在遍历的时候并不会按照你传⼊的顺序，进⾏传出。
1//正常遍历：
2for k, v := range exp {
3    fmt.Println(k, v)
4 }
5
6//有序遍历
7 import "sort"
8var keys []string
9// 把key单独抽取出来，放在数组中
10for k, _ := range exp {
11    keys = append(keys, k)
12 }
13// 进⾏数组的排序
14 sort.Strings(keys)
15// 遍历数组就是有序的了
16for _, k := range keys {
17    fmt.Println(k, m[k])
18 }
2. map的结构
  Go中的map在可以在 $GOROOT/src/到它的实现。哈希表的数据结构中⼀些关键的域如下所⽰：
1 type hmap struct {
2    count        int//元素个数
3    flags        uint8
4    B            uint8 //扩容常量
5    noverflow    uint1
6 //溢出 bucket 个数
6    hash0        uint32 //hash 种⼦
7    buckets      unsafe.Pointer //bucket 数组指针
8    oldbuckets  unsafe.Pointer //扩容时旧的buckets 数组指针
9    nevacuate    uintptr  //扩容搬迁进度
10    extra        *mapextra //记录溢出相关
11 }
12
13 type bmap struct {
14    tophash        [bucketCnt]uint8
15// Followed by bucketCnt keys
16//and then bucketan Cnt values
17// Followed by overflow pointer.
18 }
  说明：每个map的底层都是hmap结构体，它是由若⼲个描述hmap结构体的元素、数组指针、extra等组成，buckets数组指针指向由若⼲个bucket组成的数组，其每个bucket⾥存放的是key-value数据(通常是8个)和overflow字段（指向下⼀个bmap），每个key插⼊时会根据hash算法归到同⼀个bucket中，当⼀个bucket中的元素超过8个的时候，hmap会使⽤extra中的overflow来扩展存储key。
  图中len 就是当前map的元素个数，也就是len()返回的值。也是结构体中unt的值。bucket array是指数组指针，指向bucket数组。hash seed 哈希种⼦。overflow指向下⼀个bucket。
map的底层主要是由三个结构构成:
1. hmap --- map的最外层的数据结构，包括了map的各种基础信息、如⼤⼩、bucket，⼀个⼤的结构体。
2. mapextra --- 记录map的额外信息，hmap结构体⾥的extra指针指向的结构，例如overflow bucket。
3. bmap --- 代表bucket，每⼀个bucket最多放8个kv，最后由⼀个overflow字段指向下⼀个bmap，注意key、value、overflow字段都不显
⽰定义，⽽是通过maptype计算偏移获取的。
  mapextra的结构如下
1// mapextra holds fields that are not present on all maps.
2 type mapextra struct {
3// If both key and value do not contain pointers and are inline, then we mark bucket
4// type as containing no pointers. This avoids scanning such maps.
5// However, bmap.overflow is a pointer. In order to keep overflow buckets
6// alive, we store pointers to all overflow buckets a.overflow a.oldoverflow.
7// overflow and oldoverflow are only used if key and value do not contain pointers.
8// overflow contains overflow buckets for hmap.buckets.
9// oldoverflow contains overflow buckets for hmap.oldbuckets.
10// The indirection allows to store a pointer to the slice in hiter.
11    overflow    *[]*bmap
12    oldoverflow *[]*bmap
13
14// nextOverflow holds a pointer to a free overflow bucket.
15    nextOverflow *bmap
16 }
  其中Overflow指向的是预分配的overflow bucket，预分配的⽤完了那么值就变成nil。
  bmap的详细结构如下
  在map中出现哈希冲突时，⾸先以bmap为最⼩粒度挂载，⼀个bmap累积8个kv之后，就会申请⼀个新的bmap（overflow bucket）挂在这个bmap的后⾯形成链表，优先⽤预分配的overflow bucket，如果预分配的⽤完了，那么就malloc⼀个挂上去。这样减少对象数量，减轻管理内存的负担，利于gc。注意golang的map不会shrink，内存只会越⽤越多，overflow bucket中的key全删了也不会释放。
  bmap中所有key存在⼀块，所有value存在⼀块，这样做⽅便内存对齐。当key⼤于128字节时，bucket的key字段存储的会是指针，指向key的实际内容；value也是⼀样。
  hash值的⾼8位存储在bucket中的tophash字段。每个桶最多放8个kv对，所以tophash类型是数组[8]uint8。把⾼⼋位存储起来，这样不⽤完整⽐较key就能过滤掉不符合的key，加快查询速度。实际上当
hash值的⾼⼋位⼩于常量minTopHash时，会加上minTopHash，区间[0, minTophash)的值⽤于特殊标记。查key时，计算hash值，⽤hash值的⾼⼋位在tophash中查，有tophash相等的，再去⽐较key值是否相同。
1 type typeAlg struct {
2// function for hashing objects of this type
3// (ptr to object, seed) -> hash
4    hash func(unsafe.Pointer, uintptr) uintptr
5// function for comparing objects of this type
6// (ptr to object A, ptr to object B) -> ==?
7    equal func(unsafe.Pointer, unsafe.Pointer) bool
8
9// tophash calculates the tophash value for hash.
10 func tophash(hash uintptr) uint8 {
11    top := uint8(hash >> (sys.PtrSize*8 - 8))
12if top < minTopHash {
13        top += minTopHash
14    }
15return top
16 }
  golang为每个类型定义了类型描述器_type，并实现了hashable类型的_type.alg.hash和_type.alg.equal，以⽀持map的范型，定义了这类key⽤什么hash函数、bucket的⼤⼩、怎么⽐较之类的，通过这个变量来实现范型。
3. map的基本操作
3.1 map的创建
1 //makemap为make（map [k] v，hint）实现Go map创建。
2//如果编译器已确定映射或第⼀个存储桶，可以在堆栈上创建，hmap或bucket可以为⾮nil。
3//如果h！= nil，则可以直接在h中创建map。
4//如果h.buckets！= nil，则指向的存储桶可以⽤作第⼀个存储桶。
5 func makemap(t *maptype, hint int, h *hmap) *hmap {
6if hint < 0 || hint > int(maxSliceCap(t.bucket.size)) {
7        hint = 0
8    }
9
10// 初始化Hmap
11if h == nil {
12        h = new(hmap)
13    }
14    h.hash0 = fastrand()
15
16// 查将保存请求的元素数的size参数
17    B := uint8(0)
18for overLoadFactor(hint, B) {
19        B++
20    }
21    h.B = B
22
23// 分配初始哈希表
24// if B == 0, 稍后会延迟分配buckets字段（在mapassign中）
25    //如果提⽰很⼤，则将内存清零可能需要⼀段时间。
26if h.B != 0 {
27var nextOverflow *bmap
28        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
29if nextOverflow != nil {
30            h.extra = new(mapextra)
31            Overflow = nextOverflow
32        }
33    }
34
35return h
36 }
go2map地图北京
  hint是⼀个启发值，启发初建map时创建多少个bucket，如果hint是0那么就先不分配bucket，lazy分配。⼤概流程就是初始化hmap结构体、设置⼀下hash seed、bucket数量、实际申请bucket、申请mapextra结构体之类的。
  申请buckets的过程：
1// makeBucketArray初始化地图存储区的后备数组。
2// 1 << b是要分配的最⼩存储桶数。
3// dirtyalloc之前应该为nil或bucket数组
4//由makeBucketArray使⽤相同的t和b参数分配。
5//如果dirtyalloc为零，则将分配⼀个新的⽀持数组，dirtyalloc将被清除并作为后备数组重⽤。
6 func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
7base := bucketShift(b)
8    nbuckets := base
9// 对于⼩b，溢出桶不太可能出现。
10// 避免计算的开销。
11if b >= 4 {
12//加上估计的溢出桶数
13        //插⼊元素的中位数
14        //与此值b⼀起使⽤。
15        nbuckets += bucketShift(b - 4)
16        sz := t.bucket.size * nbuckets
17        up := roundupsize(sz)
18if up != sz {
19            nbuckets = up / t.bucket.size
20        }
21    }
22if dirtyalloc == nil {
23        buckets = newarray(t.bucket, int(nbuckets))
24    } else {
25// dirtyalloc先前是由上⾯的newarray（t.bucket，int（nbuckets）），但不能为空。
26        buckets = dirtyalloc
27        size := t.bucket.size * nbuckets
28if t.bucket.kind&kindNoPointers == 0 {
29            memclrHasPointers(buckets, size)
30        } else {
31            memclrNoHeapPointers(buckets, size)
32        }
33    }
34
35if base != nbuckets {
36//我们预先分配了⼀些溢出桶。
37        //为了将跟踪这些溢出桶的开销降⾄最低，我们使⽤的约定是，如果预分配的溢出存储桶发⽣了溢出指针为零，则通过碰撞指针还有更多可⽤空间。
38        //对于最后⼀个溢出存储区，我们需要⼀个安全的⾮nil指针；只是⽤bucket。
39        nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
40        last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
41        last.setoverflow(t, (*bmap)(buckets))
42    }
43return buckets, nextOverflow
44 }
  默认创建2b个bucket，如果b⼤于等于4，那么就预先额外创建⼀些overflow bucket。除了最后⼀个overflow bucket，其余overflow bucket的overflow指针都是nil，最后⼀个overflow bucket的overflow指针指向bucket数组第⼀个元素，作为哨兵，说明到了到结尾了。
3.2 查询操作
1// mapaccess1返回指向h [key]的指针。从不返回nil，⽽是如果值类型为零，它将返回对零对象的引⽤，该键不在map中。 2//注意：返回的指针可能会使整个map保持活动状态，因此请不要坚持很长时间。
3  func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
4if raceenabled && h != nil {  //raceenabled是否启⽤数据竞争检测。
5        callerpc := getcallerpc()
6        pc := funcPC(mapaccess1)
7        racereadpc(unsafe.Pointer(h), callerpc, pc)
8        raceReadObjectPC(t.key, key, callerpc, pc)
9    }
10if msanenabled && h != nil {
11        msanread(key, t.key.size)
12    }
13if h == nil || h.count == 0 {
14return unsafe.Pointer(&zeroVal[0])
15    }
16// 并发访问检查
17if h.flags&hashWriting != 0 {
18throw("concurrent map read and map write")
19    }
20
21// 计算key的hash值
22    alg := t.key.alg
23    hash := alg.hash(key, uintptr(h.hash0)) // alg.hash
24
25// hash值对m取余数得到对应的bucket
26    m := uintptr(1)<<h.B - 1
27    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
28
29// 如果⽼的bucket还没有迁移，则在⽼的bucket⾥⾯
30if c := h.oldbuckets; c != nil {
31if !h.sameSizeGrow() {
32            m >>= 1
33        }
34        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
35if !evacuated(oldb) {
36            b = oldb
37        }
38    }
39
40// 计算tophash，取⾼8位
41    top := uint8(hash >> (sys.PtrSize*8 - 8))
42

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。