京公网安备11010502063487号“map 遍历是随机的”这句话到底随机到什么程度?这篇不凭印象,而是遍历上万次,数首个键的分布、数不同的完整顺序、验证遍历中修改的结果,再指到运行时源码里取随机数的那两行。
同一个进程里第 1 次 for range:a b c d e f g h i j 同一个进程里第 2 次 for range:a b c d e f g h i j 同一个进程里第 3 次 for range:a b c d e f g h i j 同一个进程里第 4 次 for range:i j a b c d e f g h 同一个进程里第 5 次 for range:b c d e f g h i j a
Go 语言规范只说遍历顺序是不确定的;运行时则主动加了随机:每次开始 for range 都取随机偏移。所以不能依赖某次运行里看到的顺序,哪怕在测试里它碰巧稳定。
8 个键:出现过的不同首键 8 个(期望均匀时每个 1250 次),最少 1223 次、最多 1296 次 100 个键:出现过的不同首键 100 个(期望均匀时每个 100 次),最少 59 次、最多 456 次
8 个键时首键基本均匀(1223–1296),但 100 个键时差距很大(59–456)。原因我没有逐项验证,合理的猜测是:随机起点落在“槽”上而不是“键”上,而键之间隔着数量不等的空槽,前面空槽多的键更容易成为第一个。要靠遍历的随机性来做公平选择(比如随机选一个元素)是不可靠的,应该用 math/rand/v2。
5 个键:5000 次遍历出现了 5 种不同的完整顺序;全都是第一次顺序的旋转?true
8 个键:5000 次遍历出现了 8 种不同的完整顺序;全都是第一次顺序的旋转?true
9 个键:5000 次遍历出现了 9 种不同的完整顺序;全都是第一次顺序的旋转?true
20 个键:5000 次遍历出现了 20 种不同的完整顺序;全都是第一次顺序的旋转?true
100 个键:5000 次遍历出现了 100 种不同的完整顺序;全都是第一次顺序的旋转?true
1000 个键:3000 次遍历出现了 1030 种不同的完整顺序;全都是第一次顺序的旋转?false
2000 个键:3000 次遍历出现了 1734 种不同的完整顺序;全都是第一次顺序的旋转?false
20000 个键:3000 次遍历出现了 2878 种不同的完整顺序;全都是第一次顺序的旋转?false在一张表内(这里到 100 个键为止),随机的只有起点,顺序是同一个环的旋转,所以 100 个键只有 100 种顺序。键数上千、map 由多张表组成时,每张表的起点和表之间的起点分别变化,出现的顺序数才超过键数。这与上一篇里“map 由最多 1024 个槽的多张表组成”的设计一致。
遍历时删除另一个还没遍历到的键:被遍历到 0 / 2000 次;遍历时新增键 100:被遍历到 1753 / 2000 次
规范规定遍历中删除了还没遍历到的键,它就不会被遍历到(实测 0 / 2000);遍历中新增的键则“可能”被遍历到(实测 1753 / 2000,与新键落在已遍历位置之前还是之后有关,我没有分别统计)。
fmt.Println(m) → map[apple:1 banana:2 cherry:3 date:4](按键排序)
json.Marshal(m) → {"apple":1,"banana":2,"cherry":3,"date":4}(按键排序)
slices.Sorted(maps.Keys(m)) → [apple banana cherry date]
for range nil map:0 次循环,不会 panicfmt 打印 map 时按键排序(源码 fmt/print.go 打印 map 时调用 internal/fmtsort 的 Sort),encoding/json 的输出也是排好序的(上面的实测);自己遍历时先取出键排序。maps.Keys 返回的是迭代器,配合 slices.Sorted 一行就够。
if m.dirLen <= 0 {
// Use dirIdx == -1 as sentinel for small maps.
dirIdx = -1
groupSmall.data = m.dirPtr
}
it.m = m
it.entryOffset = rand()
it.dirOffset = rand()
it.globalDepth = m.globalDepth
it.dirIdx = dirIdx
it.group = groupSmall
it.clearSeq = m.clearSeq
再启动 3 个新进程,各自第 1 次遍历的顺序:
同一个进程里第 1 次 for range:c e g i j a d f h b
同一个进程里第 1 次 for range:a c d e g h j b f i
同一个进程里第 1 次 for range:h i j b d g a c e f迭代器初始化的代码里取了两个随机数:entryOffset 与 dirOffset。另外每个 map 在创建时有自己的哈希种子,所以环本身的顺序在不同进程、不同 map 之间也不同(上面 3 个新进程各给出不同的顺序)。