HashMap: iterating the key-value pairs in random order

Question

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.

Answer 1

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