# Golang Map 实现（三）map 的数据访问

## map 创建示例

``````
val := example1Map[key1]
val, ok := example1Map[key1]``````

## 那访问map 时，底层做了什么，我们一起来探究

``````
// 迭代器中使用
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer){}

// 不返回 bool
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {}
func mapaccess1_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) unsafe.Pointer {}

// 返回 bool
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {}
func mapaccess2_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) (unsafe.Pointer, bool) {}``````

### mapaccess1_fat, mapaccess2_fat

``````//src/cmd/compile/internal/gc/walk.go

if w := t.Elem().Width; w <= 1024 { // 1024 must match runtime/map.go:maxZero
n = mkcall1(mapfn(mapaccess1[fast], t), types.NewPtr(t.Elem()), init, typename(t), map_, key)
} else {
n = mkcall1(mapfn("mapaccess1_fat", t), types.NewPtr(t.Elem()), init, typename(t), map_, key, z)
}``````

``````const maxZero = 1024 // must match value in cmd/compile/internal/gc/walk.go
var zeroVal [maxZero]byte``````

### mapaccess1， mapaccess2

mapaccess1 与 mapaccess2 的差别在于是否返回返回值，mapaccess2 将返回bool 类型作为是否不存在相应key的标识，mapaccess1 不会。所以，这里着重分析mapaccess2. 代码如下：

``````func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
// 竟态分析 && 内存扫描
// ...

if h == nil || h.count == 0 {
// map 为空，或者size 为 0， 直接返回
}
if h.flags&hashWriting != 0 {
// 这里会检查是否在写，如果在写直接panic
throw("concurrent map read and map write")
}

// 拿到对应key 的hash，以及 bucket
alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
// There used to be half as many buckets; mask down one more power of two.
m >>= 1
}
oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) {
b = oldb
}
}

// 获取tophash 值
top := tophash(hash)
bucketloop:
// 遍历解决冲突的链表
for ; b != nil; b = b.overflow(t) {
// 遍历每个bucket 上的kv
for i := uintptr(0); i < bucketCnt; i++ {
// 先匹配 tophash
// ...

// 获取k
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}

// 判断k是否相等,如果相等直接返回，否则继续遍历
if alg.equal(key, k) {
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
if t.indirectvalue() {
v = *((*unsafe.Pointer)(v))
}
return v, true
}
}
}
return unsafe.Pointer(&zeroVal[0]), false
}``````

• 首先，获取key 的hash值，并取到相应的bucket
• 其次，遍历对应的bucket，以及bucket 的链表（冲突链）
• 对于每个bucket 需要先匹配tophash 数组中的值，如果不匹配，则直接过滤。
• 如果hash 匹配成功，还是需要匹配key 是否相等，相等就返回，不等继续遍历。

``````if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}``````

tophash 的值有多种情况, 如果小于minTopHash，则作为标记使用。下面是标识含义:

``````  emptyRest      = 0 // 标记为空，且后面没有数据了 (包括overflow 和 index)
emptyOne       = 1 // 在被删除的时候设置为空
evacuatedX     = 2 // kv 数据被迁移到新hash表的 x 位置
evacuatedY     = 3 // kv 数据被迁移到新hash表的 y 位置
evacuatedEmpty = 4 // bucket 被转移走了，数据是空的
minTopHash     = 5 // 阈值标识``````

enptyRest 是有利于数据遍历的，减少了对数据的访问次数
evacuateX 和 evacuateY 与数据迁移有关，我们在赋值部分学习（赋值才有可能迁移）

## 总结

• map 中，val 如果宽度比较大，0值问题也需要多分配内存。所以，这种情况，使用指针肯定是合理的。（当然，内存拷贝也是一个问题）
• tophash 值的含义参考第一篇 bucket章节

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

## map 创建示例

``````
val := example1Map[key1]
val, ok := example1Map[key1]``````

## 那访问map 时，底层做了什么，我们一起来探究

``````
// 迭代器中使用
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer){}

// 不返回 bool
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {}
func mapaccess1_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) unsafe.Pointer {}

// 返回 bool
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {}
func mapaccess2_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) (unsafe.Pointer, bool) {}``````

### mapaccess1_fat, mapaccess2_fat

``````//src/cmd/compile/internal/gc/walk.go

if w := t.Elem().Width; w <= 1024 { // 1024 must match runtime/map.go:maxZero
n = mkcall1(mapfn(mapaccess1[fast], t), types.NewPtr(t.Elem()), init, typename(t), map_, key)
} else {
n = mkcall1(mapfn("mapaccess1_fat", t), types.NewPtr(t.Elem()), init, typename(t), map_, key, z)
}``````

``````const maxZero = 1024 // must match value in cmd/compile/internal/gc/walk.go
var zeroVal [maxZero]byte``````

### mapaccess1， mapaccess2

mapaccess1 与 mapaccess2 的差别在于是否返回返回值，mapaccess2 将返回bool 类型作为是否不存在相应key的标识，mapaccess1 不会。所以，这里着重分析mapaccess2. 代码如下：

``````func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
// 竟态分析 && 内存扫描
// ...

if h == nil || h.count == 0 {
// map 为空，或者size 为 0， 直接返回
}
if h.flags&hashWriting != 0 {
// 这里会检查是否在写，如果在写直接panic
throw("concurrent map read and map write")
}

// 拿到对应key 的hash，以及 bucket
alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
// There used to be half as many buckets; mask down one more power of two.
m >>= 1
}
oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) {
b = oldb
}
}

// 获取tophash 值
top := tophash(hash)
bucketloop:
// 遍历解决冲突的链表
for ; b != nil; b = b.overflow(t) {
// 遍历每个bucket 上的kv
for i := uintptr(0); i < bucketCnt; i++ {
// 先匹配 tophash
// ...

// 获取k
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}

// 判断k是否相等,如果相等直接返回，否则继续遍历
if alg.equal(key, k) {
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
if t.indirectvalue() {
v = *((*unsafe.Pointer)(v))
}
return v, true
}
}
}
return unsafe.Pointer(&zeroVal[0]), false
}``````

• 首先，获取key 的hash值，并取到相应的bucket
• 其次，遍历对应的bucket，以及bucket 的链表（冲突链）
• 对于每个bucket 需要先匹配tophash 数组中的值，如果不匹配，则直接过滤。
• 如果hash 匹配成功，还是需要匹配key 是否相等，相等就返回，不等继续遍历。

``````if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}``````

tophash 的值有多种情况, 如果小于minTopHash，则作为标记使用。下面是标识含义:

``````  emptyRest      = 0 // 标记为空，且后面没有数据了 (包括overflow 和 index)
emptyOne       = 1 // 在被删除的时候设置为空
evacuatedX     = 2 // kv 数据被迁移到新hash表的 x 位置
evacuatedY     = 3 // kv 数据被迁移到新hash表的 y 位置
evacuatedEmpty = 4 // bucket 被转移走了，数据是空的
minTopHash     = 5 // 阈值标识``````

enptyRest 是有利于数据遍历的，减少了对数据的访问次数
evacuateX 和 evacuateY 与数据迁移有关，我们在赋值部分学习（赋值才有可能迁移）

## 总结

• map 中，val 如果宽度比较大，0值问题也需要多分配内存。所以，这种情况，使用指针肯定是合理的。（当然，内存拷贝也是一个问题）
• tophash 值的含义参考第一篇 bucket章节