Golang map

 

Map是key-value数据结构,又称为字段或者关联数组,类似其他编程语言的集合。
一 map的声明
声明一: var variableName map[keyType] valueType
说明: keyType不可以是slice,map,func
var Jack map[string] string Jack = make(map[string]string])
声明是不会分配内存的,初始化需要make,分配内存后才能赋值和使用。
分配内存要用make
声明二: Lee := make(map[string]string])
声明赋值一体化 Lei := map[string]string{“familyname”:”li”,”name”:”lei”}
func make(Type, size IntegerType) Type
内建函数make分配并初始化一个类型为切片、映射通道的对象,其第一个实参为类型,而非值。make的返回类型与其参数相同,而非指向它的指针。其具体结果取决于具体的类型:
切片:size指定了其长度,该切片的容量等于其长度。切片支持第二个整数实参可用来指定不同的容量;它必须不小于其长度,因此make([]int,0,10) 会分配一个长度为0,容量为10的切片
map:初始分配的创先取决于size,但产生的映射长度为0.size可以省略,这种情况下就会分配一个小的起始大小
channel: 通道的缓存根据指定的缓存容量初始化。若size为零或被省略,该通道即为无缓存的。
二 map的操作
a 增加和更新
map[“key”] = “value” map[“Lei”] = “Lee” Lee:=map[float64]string Jack[2.2] = “Lee” Jack[math.NaN()] = “Jack”
b map删除
delete(map,”key”)
delete 是一个内置函数,如果 key 存在,就删除该 key-value,如果 key 不存在,
不操作,但是也不会报错
删除整个map
b1 遍历删除
b2 map = make(…) make 一个新的,让原来的成为垃圾,被 gc 回收
c map的查找
value:=map[key]
d map的遍历
for key,value:= range m{ fmt.Printf(“key:%v ; value:%v\n”,key,value) }
小节总结:
  1. map 在使用前一定要 make
  2. map 的 key 是不能重复,如果重复了,则以最后这个 key-value 为准
  3. map 的 value 是可以相同的.
  4. map 的 key-value 是无序,所以遍历的时候返回的顺序不同。
  5. map 的容量达到后,再想 map 增加元素,会自动扩容,并不会发生 panic,也就是说 map 能动态的增长 键值对(key-value)
  6. map 的 value 也经常使用 struct 类型,更适合管理复杂的数据(比前面 value 是一个 map 更好),比如 value 为 Student 结构体
Map进阶
map并不是一个线程安全的数据结构。同时(多个协程同时读写)读写一个map是未定义的行为,如果被检测到,会直接panic。因为map为引用类型,所以即使函数传值调用,参数副本依然指向映射m, 所以多个goroutine并发写同一个映射m, 写过多线程程序的同学都知道,对于共享变量,资源,并发读写会产生竞争的, 故共享资源遭到破坏。这点可以通过sync包的锁来解决。
type Hua struct { Data map[string]string Lock sync.Mutex }
func(d Hua) Get (k string) string { d.Lock.Lock() defer d.Lock.Unlock() return d.Data[k] }
func(d Hua) Set(k,v string) { d.Lock.Lock() defer d.Lock.Unlock() d.Data[k] = v }
func main() { var Hua = Hua{Data : make(map[string]string)}
Hua.Set(“jack”,”lili”) fmt.Println(Hua.Get(“jack”)) }
也可以通过更高级的sync.Map来解决
sync.Map 和 map 不同,不是以语言原生形态提供,而是在 sync 包下的特殊结构。
1 无须初始化 直接声明即可 var sence sync.Map
2 sync.Map 不能使用map的方式进行取值和设置等操作,而是使用sync.Map的方法进行调用 Store表示存储,
Load表示获取,Delete表示删除 scene.Store(“green”, 97) scene.Load(“green”) //97 scene.Delete(“green”)
3 遍历用scene.Range(func(k,v interface{}}) bool{})
map的内存模型,在源码中表示map的结构体是hmap
// A header for a Go map. type hmap struct {
// 元素个数,调用 len(map) 时,直接返回此值 count int flags uint8
// buckets 的对数,也就是说buckets的数组长度就是2^B
B uint8
// overflow 的 bucket 近似数
noverflow uint16
// 计算 key 的哈希的时候会传入哈希函数
hash0 uint32
// 指向 buckets 数组,大小为 2^B
// 如果元素个数为0,就为 nil
buckets unsafe.Pointer
// 扩容的时候,buckets 长度会是 oldbuckets 的两倍 oldbuckets
unsafe.Pointer
// 指示扩容进度,小于此地址的 buckets 迁移完成
nevacuate uintptr extra *mapextra
// optional fields
}
说明: B 是 buckets 数组的长度的对数,也就是说 buckets 数组的长度就是 2^B。bucket 里面存储了 key 和 value。
buckets 是一个指针,最终它指向的是一个结构体:
type bmap struct { tophash [bucketCnt]uint8 }
但这只是表面的结构,在编译期间会给它动态创建一个新的结构:
type bmap struct { topbits [8]uint8 keys [8]keytype values [8]valuetype pad uintptr overflow uintptr }
bmap就是常说的桶,bmap 就是我们常说的“桶”,桶里面会最多装 8 个 key,这些 key 之所以会落入同一个桶,是因为它们经过哈希计算后,哈希结果是“一类”的。在桶内,又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置(一个桶内最多有8个位置)。
map的key和value 都不是指针,并且小于128字节的情况下,会把 bmap 标记为不含指针,这样可以避免 gc 时扫描整个 hmap。但是,我们看 bmap 其实有一个 overflow 的字段,是指针类型的,破坏了 bmap 不含指针的设想,这时会把 overflow 移动到 extra 字段来。
map的查找过程
key经过哈希计算后,得到hash值共 64 个 bit 位。
计算它到底要落在哪个桶时,只会用到最后 B 个 bit 位,B是数组长度的对数。
如果B=5,那么桶的个数就是buckets数组的长度是2^5=32。
用最后B个bit为来算出十进制数字,就是桶的号码。例如最后5位是01010 算出来是10号桶。
还没完啊 还没完,这才到桶,接着往下看,坚持一下。
再用哈希值的高8位(10010111),找到key在bucket中的位置。最开始桶内都没有key,如果是新增就放入找到的第一个空位。
buckets 编号就是桶编号,当发生了哈希冲突,解决手段是用链表法:
在 bucket 中,从前往后找到第一个空位。
这样,在查找某个 key 时,先找到对应的桶,再去遍历 bucket 中的 key。
举栗:
假定B=5,bucket的总数就是2^5=32,首先计算出待查找key的哈希,使用低5位00110,找到对应的6号桶。
然后用高8位10010111,对应10进制151,在6号bucket中寻找tophash为151的key,定位到2号槽位。
如果桶中没找到,并且overflow不为空,还要继续去overflow中寻找,直到找到或是所有key的槽位都找遍了,包括所有的 overflow bucket,仍然没找到就返回相应类型的零值,不会返回nil

map的key和value 都不是指针,并且小于128字节的情况下,会把 bmap 标记为不含指针,这样可以避免 gc 时扫描整个 hmap。但是,我们看 bmap 其实有一个 overflow 的字段,是指针类型的,破坏了 bmap 不含指针的设想,这时会把 overflow 移动到 extra 字段来。
map的查找过程
key经过哈希计算后,得到hash值共 64 个 bit 位。
计算它到底要落在哪个桶时,只会用到最后 B 个 bit 位,B是数组长度的对数。
如果B=5,那么桶的个数就是buckets数组的长度是2^5=32。
用最后B个bit为来算出十进制数字,就是桶的号码。例如最后5位是01010 算出来是10号桶。
还没完啊 还没完,这才到桶,接着往下看,坚持一下。
再用哈希值的高8位(10010111),找到key在bucket中的位置。最开始桶内都没有key,如果是新增就放入找到的第一个空位。
buckets 编号就是桶编号,当发生了哈希冲突,解决手段是用链表法:
在 bucket 中,从前往后找到第一个空位。
这样,在查找某个 key 时,先找到对应的桶,再去遍历 bucket 中的 key。
举栗:
假定B=5,bucket的总数就是2^5=32,首先计算出待查找key的哈希,使用低5位00110,找到对应的6号桶。
然后用高8位10010111,对应10进制151,在6号bucket中寻找tophash为151的key,定位到2号槽位。
如果桶中没找到,并且overflow不为空,还要继续去overflow中寻找,直到找到或是所有key的槽位都找遍了,包括所有的 overflow bucket,仍然没找到就返回相应类型的零值,不会返回nil
因此,某个 key 在搬迁前后 bucket 序号可能和原来相等,也可能是相比原来加上 2^B(原来的 B 值),取决于 hash 值 第 6 bit 位是 0 还是 1。
再明确一个问题:如果扩容后,B 增加了 1,意味着 buckets 总数是原来的 2 倍,原来 1 号的桶“裂变”到两个桶。
例如,原始 B = 2,1号 bucket 中有 2 个 key 的哈希值低 3 位分别为:010,110。由于原来 B = 2,所以低 2 位 10决定它们落在 2 号桶,现在 B 变成 3,所以 010110 分别落入 2、6 号桶。

发表评论

电子邮件地址不会被公开。 必填项已用*标注