map类型

wxvirus2022年3月17日

大约 6 分钟

定义

存储一个 KV 模式的数据类型

map[K]V
map[K1]map[K2]V

案例：

m := map[string]string {
		"name": "wujie",
		"course": "golang",
		"site": "wjstar",
		"quality": "notbad",
	}

m2 := make(map[string]int) // empty map

var m3 map[string]int // nil

fmt.Println(m, m2, m3)

map[course:golang name:wujie quality:notbad site:wjstar] map[] map[]

遍历操作

func map1() {
	m := map[string]string {
		"name": "wujie",
		"course": "golang",
		"site": "wjstar",
		"quality": "notbad",
	}

	fmt.Println("Traversing map")

	for k, v := range m {
		fmt.Println(k, v)
	}
}

Traversing map
name wujie
course golang
site wjstar
quality notbad

这里的k也可以使用_进行省略

for _, v := range m {
    fmt.Println(v)
}

几次运行下来，可以发现一个问题：

有时候键”name“是在前面的，有时候键”quality“是在前面的。

这说明了一个这个k 在map里是无序的，而且底层是HashMap

获取 map 的值

func map1() {
	m := map[string]string {
		"name": "wujie",
		"course": "golang",
		"site": "wjstar",
		"quality": "notbad",
	}

	fmt.Println("Getting value")
    // 存在的key
	courseName := m["course"]
	fmt.Println(courseName)
    // 不存在的key
	causeName := m["cause"]
	fmt.Println(causeName)
}

这里我们测试了一个不存在的k去获取值，此时会得到一个空的字符串，虽然在控制台打印看不出啥，但是正符合了go语言定义的一个总归会有一个Zero value提供使用。

但是我们如何进行判断这个k是否存在呢？

fmt.Println("Getting value")
courseName, ok := m["course"]
fmt.Println(courseName, ok)
if causeName, ok := m["cause"]; ok {
    fmt.Println(causeName)
} else {
    fmt.Println("key does not exist")
}

golang true
key does not exist

删除元素

fmt.Println("deleting values")
name, ok := m["name"]
fmt.Println(name, ok)

delete(m, "name")

name, ok = m["name"]
fmt.Println(name, ok)

wujie true
 false

Map 的 Key

map使用了哈希表，必须可以比较相等
除了slice,map,function的内奸类型都可以作为key
Struct类型不包含上述字段，也可以作为key，在编译的时候会进行检查

实例

寻找最长不含有重复字符的子串

从abcabcbb -> abc

从bbbbb -> b

从pwwkew -> wke

思路步骤：

对于每一个字母x

lastOccurred[x]不存在，或者< start 则无需操作
lastOccurred[x] >= start，则更新start的位置
更新lastOccurred[x]，更新maxLength

func lengthOfNnRepeatingSubStr(s string) int {
	lastOccurred := make(map[byte]int)
	start := 0
	maxLength := 0
	for i, ch := range []byte(s) {
        // 避免ch为0的情况
		lastI, ok := lastOccurred[ch]
		if ok && lastI >= start {
			// 更新 start
			start = lastI + 1
		}
		if i-start+1 > maxLength {
			maxLength = i - start + 1
		}
		lastOccurred[ch] = i
	}
	return maxLength
}

func map2() {
	fmt.Println(lengthOfNnRepeatingSubStr("abcabcbb")) // 3
	fmt.Println(lengthOfNnRepeatingSubStr("bbbbbbb")) // 1
	fmt.Println(lengthOfNnRepeatingSubStr("pwwkew")) // 3
	fmt.Println(lengthOfNnRepeatingSubStr("")) // 0
	fmt.Println(lengthOfNnRepeatingSubStr("b")) // 1
	fmt.Println(lengthOfNnRepeatingSubStr("abcdef")) // 6
}

func main() {
	map2()
}

fmt.Println(lengthOfNnRepeatingSubStr("这里是中文"))
fmt.Println(lengthOfNnRepeatingSubStr("一二三二一"))

假如这里使用了中文，这里就不对了，因为这里是使用的byte类型，必须转换为ascii。

操作总结

创建：make(map[string]int)
获取元素：m[k]
key不存在时，获得value类型的初始值
用value, ok := m[key]来判断是否存在key
使用range遍历key或者遍历key value对
遍历不保证顺序，如果需要顺序，需手动对key排序
使用len获得元素个数

HashMap 的基本方案

开放寻址法
拉链法

开放寻址法

大致过程

首先有一个底层数组已经存了一部分的KV值
进来一个新的a:A键值
首先经过Hash，hash的是k，哈希成一个数据，然后对数组的长度取模，可以算出这个键要去数组的几号位
假如要去的目标的地址已经有人占用了，就向后去寻找目标的地址，如果向后的也被占了，就继续往后，遇到空闲的，就进行分配

开放寻址1

xunzhi

读取也是差不多的一个流程，如果哈希再经过取模之后，从 1 号位开始往后找，直到找到为止。

拉链法

主要流程

同样的也会经过 hash 然后取模，找到位置
但是对于的位置并不直接放数据，每一个位置上都是存的指针，会额外放的一个像链表的东西
产生相同的 hash 的时候，就会在下面继续追加一个键值，这个就解决了hash碰撞的位置，纵向的往下拉一个链表

读取：

同样经过 hash 取模之后找到位置
然后找到对应的链表进行遍历即可获取到对应的数据

拉链法

charu

Go 的 map

有一个map.go文件里面有一个结构体：hmap

// A header for a Go map.
type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/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
    // 桶数量的2 的对数
	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 用于计算k的哈希值的

    // 桶 => 拉链法
	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
}

bmap代表了hmap里面的桶的内容

// A bucket for a Go map.
type bmap struct {
	tophash [bucketCnt]uint8 // key 的哈希值 8个哈希值
}

bucketCntBits = 3
bucketCnt     = 1 << bucketCntBits // 8

gomap

map 的初始化

使用 make 初始化

m := make(map[string]int, 10)

 0x001c 00028 (/Users/wujie/GolangProjects/src/rpc-test/demo/demo4.go:6)       PCDATA  $1, ZR
        0x001c 00028 (/Users/wujie/GolangProjects/src/rpc-test/demo/demo4.go:6)       CALL    runtime.makemap_small(SB)
        0x0020 00032 (/Users/wujie/GolangProjects/src/rpc-test/demo/demo4.go:6)       MOVD    8(RSP), R0
        0x0024 00036 (/Users/wujie/GolangProjects/src/rpc-test/demo/demo4.go:7)       STP     (ZR, ZR), ""..autotmp_11-16(SP)
        0x0028 00040 (/Users/wujie/GolangProjects/src/rpc-test/demo/demo4.go:7)       MOVD    $type.map[string]int(SB), R1
        0x0030 00048 (/Users/wujie/GolangProjects/src/rpc-test/demo/demo4.go:7)       MOVD    R1, ""..autotmp_11-16(SP)
        0x0034 00052 (/Users/wujie/GolangProjects/src/rpc-test/demo/demo4.go:7)       MOVD    R0, ""..autotmp_11-8(SP)

这里编译下来它调用了runtime.makemap_small方法，如果是windows可能是makemap方法，我现在是mac m1架构的

func makemap_small() *hmap {
	h := new(hmap)
	h.hash0 = fastrand()
	return h
}

func makemap(t *maptype, hint int, h *hmap) *hmap {
	mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
	if overflow || mem > maxAlloc {
		hint = 0
	}

	// initialize Hmap
	if h == nil {
		h = new(hmap)
	}
	h.hash0 = fastrand()

	// Find the size parameter B which will hold the requested # of elements.
	// For hint < 0 overLoadFactor returns false since hint < bucketCnt.
	B := uint8(0)
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B

	// allocate initial hash table
	// if B == 0, the buckets field is allocated lazily later (in mapassign)
	// If hint is large zeroing this memory could take a while.
	if h.B != 0 {
		var nextOverflow *bmap
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		if nextOverflow != nil {
            // 存储溢出桶
			h.extra = new(mapextra)
            // 下一个可用的溢出桶的位置
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}

mapmake初始化

字面量初始化

元素少于 25 个时，转化为简单赋值

hash := map[string]int{
    "1": 2,
    "3": 4,
    "5": 6,
}

编译的时候直接给你改成下面的：

hash := make(map[string]int, 3)
hash["1"] = 2
hash["3"] = 4
hash["5"] = 6

元素多于 25 个时，转换为循环赋值

hash := map[string]int{
    "1": 2,
    "2": 2,
    "3": 4,
    ...
    "26": 26,
}

转化

hash := make(map[string]int, 26)
// 存放key的数组
vstatk := []string{"1", "2", "3", ..., "26"}
// 存放value的数组
vstatv := []int{1, 2, 3, ..., 26}
for i := 0; i < len(vstatk); i++ {
    hash[vstatk[i]] = vstatv[i]
}

总结

Go 语言使用了拉链法实现了hashmap
每一个桶中存储键哈希的前 8 位
桶超出 8 个数据，就会存储到溢出桶中

map类型

# 定义

# 遍历操作

# 获取 map 的值

# 删除元素

# Map 的 Key

# 实例

# 操作总结

# HashMap 的基本方案

# 开放寻址法

# 拉链法

# Go 的 map

# map 的初始化

# 使用 make 初始化

# 字面量初始化

# 总结

定义