简单用例
func main() {
a := make(map[int]int)
a[2] = 1
fmt.Println(a[2])
}
复制代码golang 使用map是相当的简单，直接使用，无需调包。出于兴趣也是出于疑问，想深入了解map，以及map为啥不是并发安全。上面的用例很简单，使用map一定要make一下，才能使用，否则会因为map为nil而panic。
map的容器
map的容器结构是由bmap结构数组组成，只有理解了bmap的结构，才能理解map如何CURD操作
如何make一个map
对于上面的例子里，要make一个map会调用makemap_small函数，初始化一个hmap的结构
func makemap_small() *hmap {
h := new(hmap) //new 一个hmap
h.hash0 = fastrand() //计算hash种子，用于hash时的参数
return h
}
// A header for a Go map.
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
// Make sure this stays in sync with the compiler's definition.
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}
复制代码- count ： map中key的个数
- buckets：一个指针，指向bmap数组的头指针
- B ：buckets数量的log2
如何map[k]=v
类型的不同，可能会调用不同的函数，不过原理是类似的。对于上面的用例，会调用mapassign_fast64函数
func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {
if h == nil {
panic(plainError("assignment to entry in nil map"))
}
...
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}
hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
// Set hashWriting after calling alg.hash for consistency with mapassign.
h.flags |= hashWriting
if h.buckets == nil {
h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}
again:
bucket := hash & bucketMask(h.B)
...
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
var insertb *bmap
var inserti uintptr
var insertk unsafe.Pointer
for {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] == empty {
if insertb == nil {
insertb = b
inserti = i
}
continue
}
k := *((*uint64)(add(unsafe.Pointer(b), dataOffset+i*8)))
if k != key {
continue
}
insertb = b
inserti = i
goto done
}
...
}
...
insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks
insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8)
// store new key at insert position
*(*uint64)(insertk) = key
h.count++
done:
val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*8+inserti*uintptr(t.valuesize))
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
h.flags &^= hashWriting
return val
}
复制代码从上面的代码可以看到，如果map没被初始化会panic，map会做简单的并发检查，即检查写标志位（h.flags&hashWriting）是否被设置为1，当为1是则panic，但这种检查并不有效，尤其在多核处理器上，所以map不是并发安全。接着计算出key的hash值，并把写标志位置为1。buckets是map的容器，用来装值。如果buckets为空，初始化一个对象。bucketMask计算掩码值（如果h.B=4，则bucketMask(h.B)=1111(2)；15(10)），通过hash和掩码值相与得到是第几个bucket。根据bucket值，计算偏移获取bmap指针值。开始遍历查找是否有空的位置，存放这个key，或者是否有相同的key。如果bmap里面没有相同的key并且也有位置存放这个key，然后将tophash[inserti&(bucketCnt-1)]赋值为hash值的第一个字节，主要用来标志已存放有值。计算存放key的位置指针，赋值为key，将hmap的count加一。最后计算存放val的位置指针，将写标志位置零，将指针返回，编译器会自动添加指令，将用户代码中的value存到这个指针中。如果key已存在，就会直接跳到done区，也就是计算val的位置指针，将写标志位置零，将指针返回。
跳过了map增长之后的代码细节，可以后面继续深入。
如何获取map[k]的value值
弄明白上面如何存放value的原理，取也就是相当的简单了。
func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {
...
if h == nil || h.count == 0 {
return unsafe.Pointer(&zeroVal[0])
}
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
var b *bmap
if h.B == 0 {
// One-bucket table. No need to hash.
b = (*bmap)(h.buckets)
} else {
hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
m := bucketMask(h.B)
b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
...
}
for ; b != nil; b = b.overflow(t) {
for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) {
if *(*uint64)(k) == key && b.tophash[i] != empty {
return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize))
}
}
}
return unsafe.Pointer(&zeroVal[0])
}
复制代码获取value值的过程略写了，过程与存value值类似。首先找到bucket的位置，取得bmap的指针，然后开始遍历查找是否存在这个key，有就返回存放value的指针值，否则返回nil。