HashMap: iterating the key-value pairs in random o

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

Actually you do not need to shuffle at all:
Just draw a random index in an array of keys and remove the key by overwritting with the last:

public class RandomMapIterator<K,V> implements Iterator<V> {

private final Map<K,V> map;
private final K[] keys;

private int keysCount;

@SuppressWarnings("unchecked")
public RandomMapIterator(Map<K,V> map) {
    this.map = map;
    this.keys = (K[]) map.keySet().toArray();
    this.keysCount = keys.length;
}

@Override
public boolean hasNext() {
    return keysCount!=0;
}

@Override
public V next() {
    int index = nextIndex();
    K key = keys[index];
    keys[index] = keys[--keysCount];
    return map.get(key);
}

protected int nextIndex() {
    return (int)(Math.random() * keysCount);
}

@Override
public void remove() {
    throw new UnsupportedOperationException();
}

}

Answer 2

Try use concurent hash map and get key by random before iteration cycle

Map<String, String> map = Maps.newConcurrentMap();

        map.put("1", "1");
        map.put("2", "2");
        Iterator<String> iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            map.remove("2");// add random key values
            map.put("2", "2");
            String next = iterator.next();
            System.out.println("next" + next);
        }

Random remove/put values can "shuffle" your map

Answer 3

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