Java des Collections.shuffle est en train de faire quoi?

Question

J'ai récemment trouvé moi-même besoin d'être sûr que ma liste n'était pas dans l'ordre. Hibernate a été assez gentil de nous le retourner dans un ordre parfait. Idiot hibernate, pas à la lecture de mon esprit.

J'ai regardé mon API Java et il me dit sa shuffle méthode fait ceci:

Au hasard permute la liste spécifiée à l'aide d'une source par défaut de l'aléatoire.

Étant la curious george que je suis, je veux savoir exactement ce que cela signifie. Est-il un cours de maths que je peux apprendre? Puis-je voir le code? Java, que faites-vous à ma liste de tableaux?!?!?

Pour être plus précis, qui de concepts mathématiques sont utilisés ici?

Answer 1

Oui, vous pouvez regarder le code; il fait un shuffle de Fisher-Yates. C'est ici (merci OpenJDK, et bravo pour l'open source :-P):

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object arr[] = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

La méthode d'échange:

 private static void swap(Object[] x, int a, int b) {
    Object t = x[a];
    x[a] = x[b];
    x[b] = t;
}

Answer 2

Les Collections JavaDoc donne quelques informations sur le shuffle méthode utilisée.

Cette mise en œuvre parcourt la liste à l'envers, du dernier élément jusqu'à la seconde, à plusieurs reprises permutation au hasard de l'élément sélectionné dans la "position actuelle". Les éléments sont sélectionnés au hasard à partir de la partie de la liste qui s'exécute à partir de l'élément à la position actuelle, inclusivement.

Donc il commence à la fin du parcourt la liste à l'envers. À chaque élément, il s'arrête et fait l'échange de l'élément en cours avec un précédent élément de la liste. Le "défaut de la source de l'aléatoire" dans ce cas est probablement un Hasard objet créé avec une valeur par défaut de la graine.