How to Shuffle Collections in Java

The java.util.Collections class provides a static shuffle method that randomizes the order of elements in a List. This is the standard way to perform a java collections shuffle without writing your own randomization logic. The method modifies the list in place and works with any List implementation that supports random access, such as ArrayList, or a sequential-access list like LinkedList (though the latter is less efficient).

The Collections.shuffle() Method and Its Contract

The simplest usage is to pass the list you want to shuffle:

List<String> cards = new ArrayList<>(List.of("Ace", "King", "Queen", "Jack"));
Collections.shuffle(cards);
System.out.println(cards);

shuffle uses a default source of randomness and runs in linear time. It requires the list to support set operations, which all standard List implementations do. The method throws an UnsupportedOperationException if the list's set method is not supported, such as with an immutable list created via List.of().

How Shuffle Works Under the Hood

The implementation uses the Fisher-Yates algorithm (also called the Knuth shuffle). It iterates from the last element down to the second, and for each position i it picks a random index between 0 and i inclusive, then swaps the elements at those positions. This guarantees every permutation is equally likely when the random source is unbiased.

// Simplified version of the algorithm
for (int i = list.size() - 1; i > 0; i--) {
    int j = random.nextInt(i + 1);
    Collections.swap(list, i, j);
}

The time complexity is O(n), and the space complexity is O(1) because the shuffle is done in place. This is the most efficient way to randomize a list.

Using a Custom Random Source

Sometimes you need a reproducible shuffle, for example in tests or when you want to control the randomness seed. The overloaded shuffle(List<?> list, Random rnd) method accepts a Random instance. Using a Random with a fixed seed produces the same sequence of shuffles each run, which is useful for deterministic behavior in unit tests.

Random random = new Random(42L);
Collections.shuffle(cards, random);

You can also use a ThreadLocalRandom for better performance in concurrent scenarios, though the default overload already uses a thread-safe random source internally. The Random class is thread-safe, but using a shared instance can cause contention; ThreadLocalRandom avoids that.

Shuffling Arrays and Other Collection Types

The Collections.shuffle method only works on List instances. To shuffle an array, you must first convert it to a List using Arrays.asList() and then shuffle that view. However, the resulting list is backed by the original array, so the shuffle modifies the array directly.

Integer[] numbers = {1, 2, 3, 4, 5};
Collections.shuffle(Arrays.asList(numbers));
// numbers is now shuffled

For other collection types like Set, there is no direct shuffle method because sets do not guarantee order. If you need to randomize a set, convert it to a list first, shuffle, and then optionally rebuild a linked hash set to preserve the new order.

Thread-Safety and Concurrent Modification

The shuffle method is not atomic. If another thread modifies the list while shuffle is running, the behavior is undefined and may throw a ConcurrentModificationException or produce an inconsistent state. To shuffle safely in a multithreaded context, either synchronize externally on the list or use a thread-safe list implementation like CopyOnWriteArrayList, but note that the latter has a high write cost.

If you need a thread-safe shuffle that doesn't block other readers, consider copying the list to a new array, shuffling the copy, and then publishing the result. This avoids holding a lock during the shuffle.

Performance and Memory Considerations

The default shuffle is O(n) in time and O(1) in extra space. For large lists, the dominant cost is the random number generation and the swaps. Using a Random instance with a high-quality algorithm like SecureRandom will be slower but cryptographically strong, which is rarely needed for ordering. For most use cases, ThreadLocalRandom or the default is sufficient.

Memory usage is minimal because the shuffle operates in place. However, if you need to preserve the original order, you must create a copy of the list before shuffling. A shallow copy via new ArrayList<>(original) is enough for immutable elements; for mutable elements, the elements themselves are not copied.

Common Pitfalls and Edge Cases

One common mistake is trying to shuffle an immutable list. For example, List.of() returns an immutable list, and calling Collections.shuffle on it throws UnsupportedOperationException. Always use a mutable ArrayList or LinkedList.

Another edge case is shuffling a list with only one element or zero elements; the method does nothing, which is correct. Also, the shuffle is uniform only if the random source is unbiased. Java's Random uses a linear congruential generator, which is not perfectly uniform but is acceptable for most non-cryptographic purposes.

If you need to shuffle a large list repeatedly, consider reusing a Random instance instead of creating a new one each time, to avoid allocation overhead and to keep the sequence predictable.

Choosing Between shuffle and Other Randomization Techniques

Collections.shuffle is the right tool when you need to reorder all elements randomly. If you only need a few random elements without replacement, a partial Fisher-Yates or a reservoir sampling approach may be more efficient. For example, selecting a random subset of size k from a list of n elements can be done by shuffling only the first k positions, but Collections.shuffle shuffles the entire list. In such cases, a custom implementation that stops after k swaps avoids unnecessary work.

// Partial shuffle for first k elements
for (int i = n - 1; i > n - k - 1; i--) {
    int j = random.nextInt(i + 1);
    Collections.swap(list, i, j);
}

This approach is useful when the list is very large and only a small sample is needed. The tradeoff is that the rest of the list remains in its original order, which may or may not be acceptable depending on the use case.