//map的结构
//runtime/map.go: 一个map的类型如下: 由多个bmap组成buckets, 数据存在于bmap中

// 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
}



// A bucket for a Go map.
type bmap struct {
	// tophash generally contains the top byte of the hash value
	// for each key in this bucket. If tophash[0] < minTopHash,
	// tophash[0] is a bucket evacuation state instead.
	tophash [bucketCnt]uint8
	// Followed by bucketCnt keys and then bucketCnt elems.
	// NOTE: packing all the keys together and then all the elems together makes the
	// code a bit more complicated than alternating key/elem/key/elem/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
}

//map是引用类型
// 默认为初始化值为nil, 要使用必须先(make)初始化开辟内存
func main() {
	var m map[string]int
	fmt.Println(m == nil)
}

//true

//nil map: 要使用,必须先初始化.
func main() {
	var m map[string]int
	m["m1"] = 1
}
//panic: assignment to entry in nil map

//内容为空的map: 内存已开辟好,可直接使用
func main() {
	m := make(map[string]int)
	m["m1"] = 1
}

//或
func main() {
	m := map[string]int{}
	m["m1"] = 1
}

//定义map: 声明并初始化(crud)
func main() {
	m := map[string]int{
		"m1": 1,
	}

	fmt.Println(m["m1"]) //查询
	m["a"] = 11          //添加/更新

	delete(m, "m1") //删除,key不存在时,不会报错
	delete(m, "m2")

	v, ok := m["m2"] //判断key是否存在
	fmt.Println(v, ok)
}

//1
//0 false

// 切片中存map类型
func main() {
	rand.Seed(time.Now().UnixNano())
	var arr []map[string]int
	arr = make([]map[string]int, 10)

	for i := 0; i < 10; i++ {
		//初始化key
		arr[i] = make(map[string]int)
		arr[i]["m1"] = 10
		arr[i]["m2"] = 20
	}
	fmt.Println(arr)
}

// map中存切片

func main() {
	var m map[string][]int
	//初始化map
	m = make(map[string][]int, 0)
	
	for i := 0; i < 10; i++ {

		key := fmt.Sprintf("user%v", i)
		if _, ok := m[key]; !ok {
			//初始化key
			m[key] = make([]int, 5)
			for j := 0; j < 5; j++ {
				m[key][j] = j * 10
			}
		}
	}
	fmt.Println(m)
}

//map元素的值为匿名结构体: 声明+初始化(可以看到赋值时还是比较麻烦)
func main() {
	m := map[string]struct {
		name string
		age  int
	}{
		"item1": struct {
			name string
			age  int
		}{name: "m1", age: 22},
	}
	fmt.Println(m)
}

//map[item1:{m1 22}]

//map元素的值为匿名结构体: 先声明,后初始化
func main() {
	//声明
	var m map[string]struct {
		name string
		age  int
	}

	//初始化
	m = make(map[string]struct {
		name string
		age  int
	})
	//增加项
	m["item1"] = struct {
		name string
		age  int
	}{name: "m1", age: 22}

	fmt.Println(m)
}

//map[item1:{m1 22}]

// 结构体初始化时: key可以省略
func main() {
	m := map[string]struct {
		name string
		age  int
	}{
		"item1": struct {
			name string
			age  int
		}{"m1",22}, //{name: "m1", age: 22} -> {"m1", 22} key可以省略
	}
	fmt.Println(m)
}

//map元素的值为结构体
func main() {
	type user struct {
		name string
		age  int
	}
	m := map[int]user{
		1: {"tom", 19},
	}
	fmt.Println(m)
}

//map[1:{tom 19}]

//map元素的值为结构体: 修改结构体项的值
func main() {
	type user struct {
		name string
		age  int
	}
	m := map[int]user{
		1: {"tom", 19},
	}
	m[1].age += 1
}

//.\main.go:11:11: cannot assign to struct field m[1].age in map

//map元素的值为结构体: 修改结构体项的值
func main() {
	type user struct {
		name string
		age  int
	}
	m := map[int]user{
		1: {"tom", 19},
	}
	//修改map中k为1的结构体项的值
	// 1.先取出结构体实例
	u := m[1]
	// 2.修改结构体实例的值
	u.age = 1
	// 3.更新map
	m[1] = u
	fmt.Println(u)
}

//{tom 1}

小结: 当map的值为结构或数组时,要修改值,必须先返回对象, 因为struct/slice被设计为not addressable

//遍历map(Iterate over map): 每次运行结果无序的

func main() {
	rand.Seed(time.Now().UnixNano())

	var m map[string]int
	m = make(map[string]int, 0)
	//构建map
	for i := 0; i < 100; i++ {
		key := fmt.Sprintf("user%v", i)
		m[key] = rand.Intn(1024)
	}
	
	//遍历map
	for k, v := range m {
		fmt.Println(k, v)
	}
}

//遍历map: 使key遍历有序
	1.取出key
	2.对key排序
	3.遍历map

func main() {
	rand.Seed(time.Now().UnixNano())

	var m map[string]int
	m = make(map[string]int, 0)
	//构建map
	for i := 0; i < 100; i++ {
		key := fmt.Sprintf("user%v", i)
		m[key] = rand.Intn(1024)
	}

	//排序key
	keys := []string{}
	for k, _ := range m {
		keys = append(keys, k)
	}
	sort.Strings(keys)

	//遍历map-结果有序
	for _, v := range keys {
		fmt.Println(v, m[v])
	}
}

//先计算range m 然后开启for循环
//即必须循环len(m)次
func main() {
	m := make(map[int]int)
	//初始化
	for i := 0; i < 5; i++ {
		m[i] = i + 10
	}
	for k := range m {
		fmt.Println(m, k)
	}
}

// 安全, 在迭代期间,删除或新增key是安全的.
// 1.range m计算迭代次数, 
// 2.开启for循环
// 3.delete(m, k) 将这个key的删除

func main() {
	m := make(map[int]int)
	//初始化
	for i := 0; i < 5; i++ {
		m[i] = i + 10
	}
	//打印初始化的map
	fmt.Println(m)
	//遍历
	for k := range m {
		delete(m, k)
		fmt.Println(m, k) //打印当前map
	}
}

//map[0:10 1:11 2:12 3:13 4:14]
//map[1:11 2:12 3:13 4:14] 0
//map[2:12 3:13 4:14] 1
//map[3:13 4:14] 2
//map[4:14] 3
//map[] 4

// 安全: 运行时对字段并发操作做出检测, 如果某个任务正在对字典进程读写操作,那么其他任务就不能对该字典执行读写.
func main() {
	m := map[string]int{}
	//写操作
	go func() {
		for {
			m["m1"] += 10
			time.Sleep(time.Microsecond)
		}
	}()
	//读操作
	go func() {
		for {
			_ = m["m1"]
			time.Sleep(time.Microsecond)
		}
	}()
	time.Sleep(time.Second)
}

//fatal error: concurrent map read and map write


// 安全: 可用sync.RWMutex实现同步，避免读写操作同时进行
func main() {
	var lock sync.RWMutex
	m := map[string]int{}
	//写操作
	go func() {
		for {
			lock.Lock()
			m["m1"] += 10
			time.Sleep(time.Microsecond)
		}
	}()
	//读操作
	go func() {
		for {
			lock.RLock()
			_ = m["m1"]
			time.Sleep(time.Microsecond)
		}
	}()
	time.Sleep(time.Second)
}

- 性能 开辟足够的空间
func test()map[int]int{ 
   m:=make(map[int]int) 
   for i:=0;i<1000;i++ { 
       m[i] =i
    } 
  
   return m
} 
  
func testCap()map[int]int{ 
   m:=make(map[int]int,1000)       // 预先准备足够的空间 
   for i:=0;i<1000;i++ { 
       m[i] =i
    } 
  
   return m
} 

//性能: 一次开辟足够空间,减少内存扩容和重新hash操作
func test()map[int]int{
   m:=make(map[int]int)
   for i:=0;i<1000;i++ {
       m[i] =i
    }

   return m
}

func testCap()map[int]int{
   m:=make(map[int]int,1000)       // 预先准备足够的空间
   for i:=0;i<1000;i++ {
       m[i] =i
    }

   return m
}

func BenchmarkTest(b*testing.B) {
   for i:=0;i<b.N;i++ {
       test()
    }
}

func BenchmarkTestCap(b*testing.B) {
   for i:=0;i<b.N;i++ {
       testCap()
    }
}
//BenchmarkTest-8            16448             72062 ns/op
//BenchmarkTestCap-8         40266             29741 ns/op

//性能: 对海量小对象,使用值类型,而非指针, 减少gc成本.

[go]map实现通讯录