【Go语言基础【18】】Map基础

零、概述

Map与其他语言的对比

使用时需注意：

• 初始化后才能使用，避免操作nil map。
• 键必须为可比较类型，值可以是任意类型。
• 非并发安全，并发场景需额外保护。
• 遍历顺序不确定，如需有序遍历可先排序键。

一、Map基础

1、Map的基本概念与特性

1.本质

map是一种引用类型，底层实现为哈希表（hash table）。通过哈希函数将键（key）映射到值（value），实现快速存取。

2.核心特性

• 无序性：元素的存储顺序不确定，遍历时不保证顺序。
• 键唯一性：键不能重复，重复插入会覆盖原有值。
• 键类型限制：键必须是可比较类型（如整数、字符串、指针、结构体等），因为需要通过==判断键是否存在。
• 动态扩容：随着元素增加，会自动扩容以保持性能。

2、Map的声明与初始化

1.声明未初始化的map（nil map）

var m map[string]int // nil map，不可直接使用
// m["key"] = 100  // 错误：nil map不能赋值

2.使用make初始化map

m := make(map[string]int)        // 创建空map
m := make(map[string]int, 10)    // 预分配容量（优化性能）

3.使用字面量初始化

m := map[string]int{
    "apple":  1,
    "banana": 2,
}

3、Map的基本操作

存取元素

m := make(map[string]int)
m["apple"] = 100       // 插入/更新元素
value := m["apple"]    // 获取元素

检查键是否存在

value, exists := m["apple"]
if exists {
    fmt.Println("键存在，值为:", value)
} else {
    fmt.Println("键不存在")
}

删除元素

delete(m, "apple")     // 删除键，无论键是否存在都不会报错

遍历Map

 for key, value := range m {
     fmt.Println(key, value)
 }

 // 只遍历键
 for key := range m {
     fmt.Println(key)
 }

二、Map的底层实现

Go的map底层使用哈希表实现，核心结构是hmap（hash map）：

// A header for a Go map.
type hmap struct {
    // 元素个数，调用 len(map) 时，直接返回此值
    count     int
    flags     uint8
    // buckets 的对数 log_2
    B         uint8
    // overflow 的 bucket 近似数
    noverflow uint16
    // 计算 key 的哈希的时候会传入哈希函数
    hash0     uint32
    // 指向 buckets 数组，大小为 2^B
    // 如果元素个数为0，就为 nil
    buckets    unsafe.Pointer
    // 扩容的时候，buckets 长度会是 oldbuckets 的两倍
    oldbuckets unsafe.Pointer
    // 指示扩容进度，小于此地址的 buckets 迁移完成
    nevacuate  uintptr
    extra *mapextra // optional fields
}

核心组件

1. 桶（bucket） : 每个桶最多存储8个键值对，超出时通过溢出桶（overflow bucket）链接。

2. 哈希函数 : 将键转换为哈希值，低几位用于定位桶，高8位用于快速比较键。

3. 扩容机制 : 当装载因子（元素数/桶数）超过6.5或溢出桶过多时，触发扩容：

   • 翻倍扩容：创建新桶数组，大小为原数组的2倍，渐进式迁移元素。
   • 等量扩容：重新排列桶内元素，使存储更紧凑（解决溢出桶过多问题）。

该结构中用于存储key value的数据结构是 buckets([]bmap), 其中bmap就是我们常说的“桶”，桶里面最多装 8 个元素(key-value)

如果有第 9 个 元素 落入当前的 bucket，那就需要再构建一个 bucket ，通过 overflow 指针连接起来。

Map的性能特点

1. 时间复杂度
   • 插入、查找、删除：平均为O(1)，最坏为O(n)（极端哈希冲突）。
   • 遍历：O(n)。
2. 性能优化
   • 预分配容量：若已知元素数量，使用make(map[T]T, size)减少扩容次数。
   • 避免大结构体作为键：使用指针或基础类型作为键，减少哈希计算开销。

三、Map的注意事项

1.并发安全
map不是并发安全的，多个goroutine同时读写会导致panic。需使用sync.Map或加锁。

import "sync"

var m sync.Map
m.Store("key", "value")
value, ok := m.Load("key")

2.nil map与空map

• nil map：未初始化，不可读写，需用make或字面量初始化。
• 空map：已初始化但无元素，可以读写。

3.键类型限制
键必须是可比较类型（如int、string、struct中字段均为可比较类型），不可使用切片、map、函数等不可比较类型。