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

Question

我有一个HashMap,每当我得到迭代器时,我想以不同的随机顺序迭代它们的键值对.从概念上讲,我想在调用迭代器之前"洗牌"地图(或者如果你想要,"洗牌"迭代器).

我有两种选择:

1)使用LinkedHashMap的方法并在内部保留一个条目列表,将其随地移动并在调用迭代器时返回该视图.
2)取map.entrySet(),构造一个ArrayList并在其上使用shuffle().

虽然这两种方法看起来很像我,但我期待非常大的HashMaps,所以我真的很关心细节和内部,因为我真的不能浪费内存或计算.

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) { /* ... */ }