HashMap：以随机顺序迭代键值对 [英] HashMap: iterating the key-value pairs in random order

问题描述

我有一个HashMap，我想在每次获得迭代器时以不同的随机顺序迭代它们的键值对。在概念上，我想在调用迭代器之前拖曳地图（或者你想要混洗迭代器）。

我有两个选项我看到： 1）使用LinkedHashMap的方法，并在内部保留一个条目列表，在调用迭代器时将其轻松播放并返回该视图。
$（$）

b $ b 2）采取map.entrySet（），构造一个ArrayList并使用shuffle（）。

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

解决方案

重组一个大集合永远是昂贵的。您将每个条目至少需要一个参考。例如对于100万条记录，您将需要约4 MB。

注意;洗牌操作是 O（N）

我会使用

 映射< K，V> map = 
列表< Map.Entry< K，V>> list = new ArrayList< Map.Entry< K，V>（map.entrySet（））; 
 
 //每次你​​想要一个不同的顺序。 
 Collections.shuffle（list）; 
 for（Map.Entry< K，V> entry：list）{/ * ... * /} 
  

I have a HashMap and I'd like to iterate they key-value pairs in a different random order each time i get the iterator. Conceptually I'd like to "shuffle" the map before calling the iterator (or if you want, "shuffle" the iterator).

I have two options i see:

1) use the approach of LinkedHashMap and keep a list of the entries internally, shuffle it in-place and return that view when the iterator is called.
2) take map.entrySet(), construct an ArrayList and use shuffle() on it.

While the two approaches look vey similar to me, I'm expecting VERY BIG HashMaps, so I'm really concerned on details and internals, as I'm really not in a position to waste memory OR computation.

解决方案

Reshuffling a large collection is always going to be expensive. You are going to need at least one reference per entry. e.g. for 1 million entries you will need approx 4 MB.

Note; the shuffle operation is O(N)

I would use

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

这篇关于HashMap：以随机顺序迭代键值对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！