Context

package main

import (
	"fmt"
)

func main() {
	x := make(map[int]int)
	for i := 0; i < 30; i++ {
		x[i] = i
	}

	for i := 0; i < 10; i++ {
		for k, v := range x {
			fmt.Println(k, v)
			break
		}
	}
}

// output 
18 18
29 29
2 2
2 2
2 2
16 16
28 28
1 1
0 0
4 4

可以看到，我们进行10次遍历 map，每次遍历都只print 出第一对key-value pair，而每次遍历 print 的结果都不同。

Java 中的Hashmap

package com.company;

import java.util.HashMap;
import java.util.Map;

public class Main {

    public static void main(String[] args) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0;i<10;i++){
            map.put(i, i);
        }

        for (int i = 0;i<10;i++){
            for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
                System.out.println(entry.getKey() + ": " + entry.getValue());
                break;
            }
        }
    }
}

在Java中，并没有这个问题。

因为在 Java 中的 Hashmap 会把每个 pair object 在 heap 中的指针存在一个 array 中（根据hash 函数算出一个特定的 pair object 存储在这个 array 中的哪个 index 位置上）。而每次遍历 map 时，都会从这个 array 的头部开始一个一个元素的扫描（如果不为 nill ，说明当前位置存储了 pair 元素），

Staight-forward Idea

如果希望每次遍历 map 时，访问元素的顺序均相同，可以把 key 先提前取出来，存在 slice 里，然后对 key 排序。

import "sort"

var m map[int]string
var keys []int
for k := range m {
    keys = append(keys, k)
}
sort.Ints(keys)
for _, k := range keys {
    fmt.Println("Key:", k, "Value:", m[k])
}

如何实现随机 pick map key

Solution 1

一种方式可以循环map；把key放到slice中：

func randMapKey(m map[string]int) string {
        mapKeys = make([]string, 0, len(m)) // pre-allocate exact size
        for key := range m {
                mapKeys = append(mapKeys, key)
        }
        return mapKeys[rand.Intn(len(mapKeys))]
}

很容易验证这段代码确实会产生随机key。虽然简单但是有代价：O(n) 的时间复杂度和 O(n) 空间复杂度。

Solution 2

Reference

FEATURED TAGS

algorithm algorithmproblem architecturalpattern architecture aws c# cachesystem codis compile concurrentcontrol database dataformat datastructure debug design designpattern distributedsystem django docker domain engineering freebsd git golang grafana hackintosh hadoop hardware hexo http hugo ios iot java javaee javascript kafka kubernetes linux linuxcommand linuxio lock macos markdown microservices mysql nas network networkprogramming nginx node.js npm oop openwrt operatingsystem padavan performance programming prometheus protobuf python redis router security shell software testing spring sql systemdesign truenas ubuntu vmware vpn windows wmware wordpress xml zookeeper

【Golang】Golang 遍历 map 时 key 随机化问题（Interation Order）