java - HashMap:以随机顺序迭代键值对

Question

我有一个 HashMap，我想在每次获得迭代器时以不同的随机顺序迭代它们的键值对。从概念上讲，我想在调用迭代器之前“打乱” map (或者，如果需要，“打乱”迭代器)。

我有两个选择:

1) 使用 LinkedHashMap 的方法并在内部保留条目列表，将其就地打乱并在调用迭代器时返回该 View 。
2) 采用 map.entrySet()，构造一个 ArrayList 并在其上使用 shuffle()。

虽然这两种方法看起来与我非常相似，但我期待非常大的 HashMap，所以我真的很关心细节和内部结构，因为我真的不能浪费内存或计算。

Answer 1

重新洗牌一个大的集合总是很昂贵的。每个条目至少需要一个引用。例如对于 100 万个条目，您将需要大约 4 MB。

注意；洗牌操作是 O(N)

我会用

Map<K,V> map = 
List<Map.Entry<K,V>> list = new ArrayList<Map.Entry<K,V>>(map.entrySet());

// each time you want a different order.
Collections.shuffle(list);
for(Map.Entry<K, V> entry: list) { /* ... */ }