1. Golang 字典 map

1. Golang 字典 map

mapmapmap

1.1. 基本用法

字典属于引用类型, 初始化方式主要有 2 种, 分别为:

m1 := make(map[string]int)
m2 := map[string]int{
	"lvmenglou": 32, 
    "litinajie": 28,
}

字典是被设计成 “not addressable”, 所以不能直接修改 value 成员, 如果需要修改 value 成员, 需要对元素整体替换:

type user struct {
	name string
	age  byte
}

m := map[int]user{1: {"lvmenglou": 32}}
m[1].age += 1 // 错误：cannot assign to m[1].age

nil

var m map[string]intm["a"] = 1 // panic: assignment to entry in nil map

nil

var m1 map[string]int  // nil 字典 
m2 := map[string]int{} // 空字典, 不等于 nil

mapmapsync.Map

1.2. 内存模型

先看一下 map 的数据结构:

type hmap struct {
	count      int
	B          uint8          // bucket 的数量是 2^B, 最多可以放 loadFactor * 2^B 个元素, 再多就要 hashGrow 了
	hash0      uint32         // hash seed
	buckets    unsafe.Pointer //2^B 大小的数组, 如果 count == 0 的话, 可能是 nil
	oldbuckets unsafe.Pointer // 扩容的时候, buckets 长度会是 oldbuckets 的两倍, 只有在 growing 时候为空。
	// 其它省略。..
}

type bmap struct {
	topbits  [8]uint8
	keys     [8]keytype
	values   [8]valuetype
	pad      uintptr
	overflow uintptr
}

mapbmapbmapbmap

bmapbmap

1.3. 查找数据

key 经过哈希计算后得到哈希值, 哈希值是 64 个 bit 位(针对 64 位机), 假如一个 key 经过哈希函数计算后, 得到的哈希结果是:

10010111 | 000011110110110010001111001010100010010110010101010 │ 01010

0101010010111bmap

1.4. 扩容缩容

map8*2^BB=5B=6[]bmap

bmap

假设 overflow 太多, 触发了等量扩容, 需要将数据变得更紧凑。

B=2B=3

1.5. 迭代遍历

mapmap*oldbuckets*buckets*oldbuckets*buckets

1.6. 总结

mapmapmapNMrehash

1.7. Deep copy

deepcopy.go

// Package deepcopy provides a function for deep copying map[string]interface{}
// values. Inspired by the StackOverflow answer at:
// http://stackoverflow.com/a/28579297/1366283
//
// Uses the golang.org/pkg/encoding/gob package to do this and therefore has the
// same caveats.
// See: https://blog.golang.org/gobs-of-data
// See: https://golang.org/pkg/encoding/gob/
package deepcopy

import (
	"bytes"
	"encoding/gob"
)

func init() {
	gob.Register(map[string]interface{}{})
}

// Map performs a deep copy of the given map m.
func Map(m map[string]interface{}) (map[string]interface{}, error) {
	var buf bytes.Buffer
	enc := gob.NewEncoder(&buf)
	dec := gob.NewDecoder(&buf)
	err := enc.Encode(m)
	if err != nil {
		return nil, err
	}
	var copy map[string]interface{}
	err = dec.Decode(&copy)
	if err != nil {
		return nil, err
	}
	return copy, nil
}

deepcopy_test.go

package deepcopy

import (
	"testing"

	"github.com/stretchr/testify/assert"
)

func TestMap(t *testing.T) {
	testCases := []struct {
		// original and expectedOriginal are the same value in each test case. We do
		// this to avoid unintentionally asserting against a mutated
		// expectedOriginal and having the test pass erroneously. We also do not
		// want to rely on the deep copy function we are testing to ensure this does
		// not happen.
		original         map[string]interface{}
		transformer      func(m map[string]interface{}) map[string]interface{}
		expectedCopy     map[string]interface{}
		expectedOriginal map[string]interface{}
	}{
		// reassignment of entire map, should be okay even without deepcopy.
		{
			original: nil,
			transformer: func(m map[string]interface{}) map[string]interface{} {
				return map[string]interface{}{}
			},
			expectedCopy:     map[string]interface{}{},
			expectedOriginal: nil,
		},
		{
			original: map[string]interface{}{},
			transformer: func(m map[string]interface{}) map[string]interface{} {
				return nil
			},
			expectedCopy:     nil,
			expectedOriginal: map[string]interface{}{},
		},
		// mutation of map
		{
			original: map[string]interface{}{},
			transformer: func(m map[string]interface{}) map[string]interface{} {
				m["foo"] = "bar"
				return m
			},
			expectedCopy: map[string]interface{}{
				"foo": "bar",
			},
			expectedOriginal: map[string]interface{}{},
		},
		{
			original: map[string]interface{}{
				"foo": "bar",
			},
			transformer: func(m map[string]interface{}) map[string]interface{} {
				m["foo"] = "car"
				return m
			},
			expectedCopy: map[string]interface{}{
				"foo": "car",
			},
			expectedOriginal: map[string]interface{}{
				"foo": "bar",
			},
		},
		// mutation of nested maps
		{
			original: map[string]interface{}{},
			transformer: func(m map[string]interface{}) map[string]interface{} {
				m["foo"] = map[string]interface{}{
					"biz": "baz",
				}
				return m
			},
			expectedCopy: map[string]interface{}{
				"foo": map[string]interface{}{
					"biz": "baz",
				},
			},
			expectedOriginal: map[string]interface{}{},
		},
		{
			original: map[string]interface{}{
				"foo": map[string]interface{}{
					"biz": "booz",
					"gaz": "gooz",
				},
			},
			transformer: func(m map[string]interface{}) map[string]interface{} {
				m["foo"] = map[string]interface{}{
					"biz": "baz",
				}
				return m
			},
			expectedCopy: map[string]interface{}{
				"foo": map[string]interface{}{
					"biz": "baz",
				},
			},
			expectedOriginal: map[string]interface{}{
				"foo": map[string]interface{}{
					"biz": "booz",
					"gaz": "gooz",
				},
			},
		},
		// mutation of slice values
		{
			original: map[string]interface{}{
				"foo": []string{"biz", "baz"},
			},
			transformer: func(m map[string]interface{}) map[string]interface{} {
				m["foo"].([]string)[0] = "hiz"
				return m
			},
			expectedCopy: map[string]interface{}{
				"foo": []string{"hiz", "baz"},
			},
			expectedOriginal: map[string]interface{}{
				"foo": []string{"biz", "baz"},
			},
		},
	}
	for i, tc := range testCases {
		copy, err := Map(tc.original)
		assert.NoError(t, err)
		assert.Exactly(t, tc.expectedCopy, tc.transformer(copy), "copy was not mutated. test case: %d", i)
		assert.Exactly(t, tc.expectedOriginal, tc.original, "original was mutated. test case: %d", i)
	}
}