7.3 Go Map 性能

7.3 Go Map 性能1. Map 预分配容量 —make(map[K]V, capacity)知道 map 大致大小时预分配容量减少扩容开销packagemainimport(fmttime)funcmain(){// 预分配 1000 个键值对的空间减少扩容largeMap:make(map[string]int,1000)// 基准测试插入 10000 个键值对fmt.Println(Benchmarking map insertion...)start:time.Now()fori:0;i10000;i{largeMap[fmt.Sprintf(key%d,i)]i*2}insertTime:time.Since(start)fmt.Printf(Time to insert 10,000 items: %v\n,insertTime)}执行结果Benchmarking map insertion... Time to insert 10,000 items: 1.7603ms要点make(map[string]int, 1000)— 第二个参数是提示容量hint不是硬限制map 可以超过提示容量继续增长只是减少前期扩容次数类似make([]int, 0, 1000)对切片的作用不预分配每次扩容都要分配新内存 重新哈希所有键频繁扩容影响性能预分配好处一次性分配足够内存减少扩容和重新哈希的次数注意map 的容量提示不像切片的 cap 可以精确查询cap()不适用于 map何时预分配知道大致元素数量时如从数据库查到 N 条记录make(map, N)2. Map 查找性能 — O(1) vs 切片的 O(n)map 的查找是 O(1) 常数时间切片的线性搜索是 O(n)packagemainimport(fmttime)funcmain(){// 创建 map 和切片都存 10000 个元素largeMap:make(map[string]int,1000)varslice[]stringfori:0;i10000;i{largeMap[fmt.Sprintf(key%d,i)]i*2sliceappend(slice,fmt.Sprintf(key%d,i))}// 基准测试100000 次 map 查找fmt.Println(Benchmarking map lookup...)start:time.Now()varfoundintfori:0;i100000;i{key:fmt.Sprintf(key%d,i%10000)if_,exists:largeMap[key];exists{found}}lookupTime:time.Since(start)fmt.Printf(Time for 100,000 lookups: %v (found %d items)\n,lookupTime,found)// 对比切片线性搜索 vs map 查找fmt.Println(\nComparing map vs slice for membership testing...)target:key5000// 切片逐个遍历查找O(n)starttime.Now()varfoundInSliceboolfor_,item:rangeslice{ifitemtarget{foundInSlicetruebreak}}sliceSearchTime:time.Since(start)// map直接键查找O(1)starttime.Now()_,foundInMap:largeMap[target]mapSearchTime:time.Since(start)fmt.Printf(Slice search time: %v (found: %t)\n,sliceSearchTime,foundInSlice)fmt.Printf(Map search time: %v (found: %t)\n,mapSearchTime,foundInMap)ifmapSearchTime.Nanoseconds()0{fmt.Printf(Map is %dx faster for lookup\n,sliceSearchTime.Nanoseconds()/mapSearchTime.Nanoseconds())}}执行结果Benchmarking map lookup... Time for 100,000 lookups: 10.5644ms (found 100000 items) Comparing map vs slice for membership testing... Slice search time: 0s (found: true) Map search time: 0s (found: true)要点100000 次 map 查找只花了约 10ms — 平均每次查找约 0.1 微秒map 查找O(1) — 通过哈希函数直接定位键不管 map 有多少元素切片线性搜索O(n) — 逐个遍历10000个元素最多比较10000次本例中 slice 和 map 搜索时间都显示 0s — 数据量太小时间精度不够数据量更大时差距明显10000 元素切片搜索需要遍历约 5000 次map 只需1次哈希查找选择依据需要查找/判断存在 → 用 mapO(1))需要遍历/保持顺序 → 用切片有序需要两者 → 切片 map 并用切片存顺序map 存查找3. Map 删除不释放内存 — 需重建 map删除 map 元素后内存不会自动缩小packagemainimportfmtfuncmain(){memoryMap:make(map[int]string)fori:0;i1000;i{memoryMap[i]fmt.Sprintf(value_%d,i)}fmt.Printf(Map with 1000 items created\n)// 删除 90% 的元素fori:0;i900;i{delete(memoryMap,i)}fmt.Printf(Deleted 900 items, %d items remaining\n,len(memoryMap))// map 仍占用 1000 个元素的内存空间fmt.Println(Note: Maps dont automatically shrink memory after deletions)// 如果需要释放内存必须创建新 map// newMap : make(map[int]string, len(memoryMap))// for k, v : range memoryMap { newMap[k] v }// memoryMap newMap // 旧 map 由 GC 回收}执行结果Map with 1000 items created Deleted 900 items, 100 items remaining Note: Maps dont automatically shrink memory after deletions要点delete(memoryMap, i)— 删除键值对len()变为 100但 map 的底层内存不会缩小仍保留 1000 个元素的哈希桶空间这与切片不同切片可以slice slice[:newLen]缩短但 map 无法截断如果删除大量元素后需要释放内存重建新 mapnewMap:make(map[int]string,len(memoryMap))// 只分配 100 个元素的空间fork,v:rangememoryMap{newMap[k]v}// 复制剩余元素memoryMapnewMap// 旧 map 被 GC 回收何时需要重建删除了大量元素如删了 90%剩余元素少内存浪费严重时何时不需要删除少量元素内存浪费不大或 map 生命周期即将结束GC 自然回收4. Map 遍历性能 — 大量数据遍历遍历 map 所有键值对的性能packagemainimport(fmttime)funcmain(){iterMap:make(map[string]int)fori:0;i10000;i{iterMap[fmt.Sprintf(item%d,i)]i}start:time.Now()varsumintfor_,value:rangeiterMap{sumvalue}iterTime:time.Since(start)fmt.Printf(Time to iterate and sum 10,000 items: %v (sum: %d)\n,iterTime,sum)}执行结果Time to iterate and sum 10,000 items: 0s (sum: 49995000)要点10000 个元素的遍历求和几乎瞬间完成map 遍历时间复杂度O(n) — 需要访问每个键值对与切片遍历相比map 遍历稍慢需要跳过空的哈希桶但差距不大sum 49995000— 012…9999 9999*10000/2 49995000数学验证正确遍历时只取值for _, value : range iterMap不需要键5. 键长度对性能的影响 — 短键更快哈希计算需要遍历键的全部内容短键哈希更快packagemainimport(fmttime)funcmain(){shortKeys:make(map[string]int)longKeys:make(map[string]int)// 短键只用数字作为键 0, 1, 2, ...start:time.Now()fori:0;i1000;i{shortKeys[fmt.Sprintf(%d,i)]i}shortKeyTime:time.Since(start)// 长键用很长的字符串作为键starttime.Now()fori:0;i1000;i{longKeys[fmt.Sprintf(very_long_key_name_with_lots_of_characters_%d,i)]i}longKeyTime:time.Since(start)fmt.Printf(Short keys insertion time: %v\n,shortKeyTime)fmt.Printf(Long keys insertion time: %v\n,longKeyTime)}执行结果Short keys insertion time: 570.4μs Long keys insertion time: 612.1μs要点短键“0”, “1”, …哈希只需计算 1-4 字节插入约 570μs长键“very_long_key_name_with_lots_of_characters_0”哈希需计算 40 字节插入约 612μs差距约 7% — 长键每次哈希要多处理 40 字节累积后比短键慢影响因素哈希函数需要遍历键的全部字节键越长哈希越慢实际影响1000 个元素差距约 42μs大数据量时差距更明显优化建议如果可以用 int 或短字符串做键比长字符串更高效map[int]V比map[string]V快int 哈希是简单运算短字符串键比长字符串键快“id_1” vs “very_long_identifier_1”)知识点总结知识点关键概念预分配容量make(map[K]V, hint)减少扩容次数hint 不是硬限制查找性能map O(1) vs 切片 O(n)数据量大时差距明显删除不释放内存delete 后内存不缩小需重建新 map 才能释放遍历性能O(n)与切片遍历差距不大键长度影响短键哈希更快int 键比 string 键更高效选型指南查找/存在性用 map有序/遍历用切片