java - HashMap: iteración de los pares clave-valor en orden aleatorio

data-structures random

Question

Tengo un HashMap y me gustaría iterar los pares clave-valor en un orden aleatorio diferente cada vez que obtengo el iterador. Conceptualmente me gustaría "mezclar" el mapa antes de llamar al iterador (o si lo desea, "mezclar" el iterador).

Tengo dos opciones que veo:

1) utilice el enfoque de LinkedHashMap y mantenga una lista de las entradas internamente, remezclarla en el lugar y devolver esa vista cuando se llame al iterador.
2) tome map.entrySet (), construya una ArrayList y use shuffle () en ella.

Si bien los dos enfoques parecen muy similares a mí, espero VERY BIG HashMaps, así que estoy realmente preocupado por los detalles y el funcionamiento interno, ya que realmente no estoy en posición de malgastar la memoria O el cálculo.

Answer 1

Intente usar el mapa concurent hash y obtenga la clave al azar antes del ciclo de iteración

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);
        }

Los valores de quitar / poner aleatorios pueden "mezclar" su mapa

Answer 2

La remodelación de una gran colección siempre será costosa. Necesitará al menos una referencia por entrada. por ejemplo, para 1 millón de entradas, necesitarás aproximadamente 4 MB.

Nota; la operación de mezcla es O(N)

yo usaría

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

Answer 3

En realidad, no es necesario mezclar nada:
Simplemente dibuje un índice al azar en una matriz de teclas y elimine la clave sobrescribiendo con la última:

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();
}

}