> # 相关概念 - 哈希表（hash table），又称散列表，它通过建立键`key`与值`value`之间的映射，实现高效的元素查找元素，添加元素，删除元素 O(n)时间 * `hmap`是`map`结构的头部，用于存储`map`的元数据 * `bmap`是实际存储`map`键值对的结构。它表示一个存储桶（bucket）   ```go type hmap struct { count int // 活跃的键值对数量 == map 的大小。必须是第一个字段（由 len() 内置函数使用）。 flags uint8 // 标志位，用于存储与 map 状态相关的标志信息。 B uint8 // 存储桶的数量的对数（log_2），可以容纳最多 loadFactor * 2^B 个元素。 noverflow uint16 // 近似的溢出存储桶的数量；有关详细信息，请参见 incrnoverflow。 hash0 uint32 // 哈希种子，用于哈希函数的初始值。 buckets unsafe.Pointer // 指向存储桶数组的指针，数组大小为 2^B。如果 count == 0，则可能为 nil。 oldbuckets unsafe.Pointer // 指向先前存储桶数组的指针，其大小为当前的一半，仅在增长时为非 nil。 nevacuate uintptr // 迁移进度计数器（小于此值的存储桶已迁移到新的存储桶数组）。 extra *mapextra // 可选字段，包含一些额外的字段。 } type mapextra struct { overflow *[]*bmap /* 溢出桶的指针 */ oldoverflow *[]*bmap nextOverflow *bmap } type bmap struct { // tophash 通常包含此存储桶中每个键的哈希值的最高字节。 // 如果 tophash[0] < minTopHash，则 tophash[0] 是存储桶搬迁状态。 tophash [bucketCnt]uint8 // 接下来是 bucketCnt 个键和 bucketCnt 个元素。 // 注意：将所有键一起打包然后将所有元素一起打包使代码稍微复杂一些， // 比如交替存储 key/elem/key/elem/...，但是这样可以消除填充， // 填充可能需要，例如 map[int64]int8。 // 紧跟在这些之后的是溢出指针。 } /* 当kev/value不为指针时，溢出桶存放到mapextra结构中，overflow存放buckets中的溢出 桶，oldoverflow存放oldbuckets中的溢出桶，nextOverflow预分配溢出桶空间 */ type mapextra struct { overflow *[]*bmap /* 以切片形式存放buckets中的每个溢出桶 */ oldoverflow *[]*bmap /* 以切片形式存放oldbuckets中的每个溢出桶*/ nextOverflow *bmap } /* map标志位 */ iterator 1 /* 迭代器buckets桶的标志位，表示正在使用buckets*/ oldIterator 2 /* 迭代器oldbuckets桶的标志位 ，为示正在使用oldbuckets*/ hashWriting 4 /* 并发写标志位，表示有goroutine正在写map */ sameSizeGrow 8 /* 等量扩容标志，表示申请的桶数量和原来一样 */ ``` > # key的定位 - key 根据当前初始话的hash种子进行哈希计算得到哈希值， hash后几位确定桶的位置， 前几位作为tophash - 当两个不同的 key 落在同一个桶中，也就是发生了哈希冲突。冲突的解决手段是用链表法：在 bucket 中，从前往后找到第一个空位。这样在查找某个 key 时，先找到对应的桶，再去遍历 bucket 中的 key。如果在 bucket 中没找到，并且 overflow 不为空，还要继续去 overflow bucket 中寻找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。 - 链式地址解决哈希冲突： 每个桶存储一个链表包含所有冲突的元素 > # map 的key可以是哪些值 | 操作符 | 变量类型 | | --- | --- | | 等值操作 (==、!=) | 整型、浮点型、字符串、布尔型、复数、指针、管道、接口、结构体、数组 | | 排序操作 ( <、<=、>、 >=) | 整型、浮点型、字符串 | | 不可比较 | map、slice、function | - `map`的键（key）必须是可以用来比较是否相等的类型。这意味着键类型必须是支持`==`和`!=`运算符的类型（ panic: runtime error: hash of unhashable type XXX） - 可以作为key的类型 - **布尔型 (`bool`)**: 可以比较相等，不可以比较大小 - **数字类型**: * 整型 (`int`, `int8`, `int16`, `int32`, `int64`) 可以比较相等，可以比较大小 * 无符号整型 (`uint`, `uint8`, `uint16`, `uint32`, `uint64`) 可以比较相等，可以比较大小 * 浮点型 (`float32`, `float64`) 可以比较相等，可以比较大小 * 复数类型 (`complex64`, `complex128`) `var c1 complex64 = complex(5, 7) // 5 + 7i` 可以比较相等，不可以比较大小 - **字符串类型 (`string`)**：可以比较相等，可以比较大小 - **指针类型**： 比较两个指针是否指向相同的内存地址 ，可以比较相等，不可以比较大小 - **通道类型 (`chan`)**:两个通道值被认为是相等的当且仅当它们指向同一个通道。可以比较相等，不可以比较大小 - **空结构体** ：由于空结构体类型的值是唯一的，只能有一个键值对，可以比较相等，不可以比较大小 - 不可以作为key的类型 - **切片类型 (`slice`)**: 因为切片是动态数据结构，底层数据可以改变，所以不能用作键。 - **映射类型 (`map`)**: `map` 也是一个动态数据结构，不能用作键。 - **函数类型 (`func`)**: 函数是无法进行比较的，因此不能作为键。 - 不包含不可比较类型时，可比较等值 - **接口类型 (`interface{}`)**: 不同类型的比较返回false, 函数类型和切片类型比较返回 false, 两个切片类型比较会报错 - **数组类型 (`array`)**: 虽然数组可以进行比较，但如果它包含不可比较的元素类型，则不能用作键。 - **结构体类型 (`struct`)**: 如果结构体的所有字段都是可比较的类型，那么整个结构体类型也是可比较的，可以用作键；如果包含不可比较的字段，则不能用作键。 > # map为什么是无序的， 如何有序输出 - 每次遍历map时，不是从固定的0号桶开始，而是从一个随机值序号的bucket开始。这种随机性确保了每次遍历的结果都是不同的，从而使得map看起来是无序的。 - 扩容导致key的搬迁:当map进行扩容时，原有的key可能会被搬迁到新的位置，这进一步加剧了map的无序性。 ~~~ package main import ( "fmt" "sort" ) func main() { m := map[int]string{ 3: "c", 1: "a", 2: "b", } fmt.Println("----- Before -----") for k, _ := range m { fmt.Println(k, m[k]) } fmt.Println("----- After -----") s := make([]int, 0, len(m)) for k, _ := range m { s = append(s, k) } sort.Ints(s) for k, _ := range s { v := s[k] fmt.Println(v, m[v]) } } ~~~ > # 对未初始化的 map 进行赋值操作 ~~~ package main import ( "fmt" ) func main() { var m map[string]int m["A"] = 1 //panic: assignment to entry in nil map fmt.Println(m) } ~~~ > # map 是不是线程安全 - map 不是线程安全的， *在查找、赋值、遍历、删除的过程中都会检测写标志，一旦发现写标志置位（等于1），则直接 panic - 当 Go 的 runtime 代码检测到 `map` 的 `hashWriting` 标志位已经被设置（表示当前有 Goroutine 在进行写操作），并且又有另一个 Goroutine 尝试对同一个 `map` 进行写操作时，Go 会抛异常 - 并发写报错：fatal error: concurrent map writes - 并发读和写报错： fatal error: concurrent map read and map write - 并发迭代和写操作报错： concurrent map iteration and map write - 并发读不回抛异常 - 切片不是线程安全的，会出现类似的异常吗？ -- 不会：切片在 Go 中不是线程安全的，并发访问可能会引发数据竞争，虽然不会像 `map` 那样触发 `panic`，但仍然存在数据不一致的风险。与 `map` 相比，切片的底层结构更简单，因此不会进行额外的线程安全检查 > # 并发安全 ~~~ package main import ( "fmt" "sync" ) type CustomMap struct { m map[interface{}]interface{} mu sync.RWMutex } // 初始化 func NewCustomMap() *CustomMap { return &CustomMap{ m: make(map[interface{}]interface{}), } } // 根据键获取值 func (cm *CustomMap) Load(key interface{}) (value interface{}, ok bool) { cm.mu.RLock() value, ok = cm.m[key] cm.mu.RUnlock() return } // 添加键值 func (cm *CustomMap) Store(key, value interface{}) { cm.mu.Lock() cm.m[key] = value cm.mu.Unlock() } // 修改键值 (over=false key不存在修改失败 over=true key不存在则添加) func (cm *CustomMap) LoadOrStore(key, value interface{}, over bool) bool { cm.mu.Lock() defer cm.mu.Unlock() if over { cm.m[key] = value } else { if _, ok := cm.m[key]; !ok { return false } else { cm.m[key] = value } } return true } // 删除键值 func (cm *CustomMap) Delete(key interface{}) { cm.mu.Lock() delete(cm.m, key) cm.mu.Unlock() } // 遍历键值 func (cm *CustomMap) Range(f func(key, value interface{}) bool) { cm.mu.RLock() for k, v := range cm.m { f(k, v) } cm.mu.RUnlock() } func main() { cm := NewCustomMap() var wg sync.WaitGroup wg.Add(5) for i := 0; i < 100000; i++ { cm.Store(i, i) } //添加键值 go func() { for i := 100000; i < 200000; i++ { cm.Store(i, i+1) } wg.Done() }() //删除键值 go func() { for i := 0; i < 100000; i++ { cm.Delete(i) } wg.Done() }() //修改键值 go func() { for i := 0; i < 100000; i++ { cm.LoadOrStore(i, i+1, false) } wg.Done() }() //查询键值 go func() { for i := 0; i < 100000; i++ { cm.Load(i) } wg.Done() }() //遍历键值 go func() { cm.Range(func(k, v interface{}) bool { _, _ = k, v return true }) wg.Done() }() wg.Wait() fmt.Println("正常结束") } ~~~ - *Go言语官方是在Go 1.9中才正式加入了并发安全的字典类型sync.Map ~~~ package main import ( "fmt" "sync" ) func main() { var cm sync.Map var wg sync.WaitGroup wg.Add(5) for i := 0; i < 100000; i++ { cm.Store(i, i) } // 添加键值 go func() { for i := 100000; i < 200000; i++ { cm.Store(i, i+1) } wg.Done() }() // 删除键值 go func() { for i := 0; i < 100000; i++ { cm.Delete(i) } wg.Done() }() // 修改键值 go func() { for i := 0; i < 100000; i++ { _, loaded := cm.LoadOrStore(i, i+1) if loaded { cm.Store(i, i+1) } } wg.Done() }() // 查询键值 go func() { for i := 0; i < 100000; i++ { cm.Load(i) } wg.Done() }() // 遍历键值 go func() { cm.Range(func(k, v interface{}) bool { _, _ = k, v return true }) wg.Done() }() wg.Wait() fmt.Println("正常结束") } ~~~ > # 实现集合 - 成员是唯一的，不能出现重复的数据 - `struct{}` 是一个零大小的类型（zero-sized type）。它不占用任何内存空间 ~~~ package main import "fmt" type Set[T comparable] map[T]struct{} func (s Set[T]) Add(key T) { s[key] = struct{}{} } func (s Set[T]) Delete(key T) { delete(s, key) } func main() { stringSet := make(Set[string]) stringSet.Add("a") stringSet.Add("b") stringSet.Add("c") stringSet.Add("b") stringSet.Add("d") fmt.Println("String Set:", stringSet) } ~~~ > # 对 map 的 key/value 取地址 ~~~ package main import ( "fmt" "unsafe" ) func main() { m := make(map[int]string) m[1] = "A" m[2] = "B" m[3] = "C" //无法对 map 的 key 或 value 进行取址, 因为一旦发生扩容，key 和 value 的位置就会改变，之前保存的地址也就失效了 //fmt.Println(&m[1]) //报错 cannot take address of m[1] (map index expression of type string) fmt.Println("---------------") for k := range m { ptr := unsafe.Pointer(&k) // 获取键的内存地址 fmt.Printf("Key: %d, Address: %p\n", k, ptr) } fmt.Println("---------------") m[4] = "D" m[5] = "E" m[6] = "F" m[7] = "G" m[8] = "H" for k := range m { ptr := unsafe.Pointer(&k) // 获取键的内存地址 fmt.Printf("Key: %d, Address: %p\n", k, ptr) } } ~~~