Threadsafe pseudo-shuffle - each caller gets a random element of the backing array, with the guarantee that each element will be selected at most once. The tradeoff is that as we approach all elements selected, we hit a slowdown as we're forced to scan for the remaining elements. For that reason, this is best suited to situations where we need a…

RandomElementProvider.java

import java.util.Random;
import java.util.concurrent.atomic.AtomicIntegerArray;

public class RandomElementProvider {
  //Flag value - not valid as an element of the backing array.
  public static final int INVALID = Integer.MIN_VALUE;
  //After this many failed random selections, devolve to a scan.
  //Corresponds to being able to handle on average (1 - 1/RETRY_THRESHOLD) of elements
  //being selected already before scanning
  public static final int RETRY_THRESHOLD = 4;
  //Alternately we could store a counter, which would let us avoid fruitless final scans
  volatile boolean depleted = false;
  final AtomicIntegerArray data;
  
  public RandomElementProvider(int[] data) {
    this.data = new AtomicIntegerArray(data);
  }
  public int getInt(){
    return getInt(new Random());
  }
  //Returns either a random, previously unselected element of the backing array, or INVALID
  public int getInt(Random rng){
    if (depleted) return INVALID;
    //Sample
    int tries = 0;
    while(tries < RETRY_THRESHOLD){
      final int idx = rng.nextInt(data.length());
      final int curVal = data.getAndSet(idx, INVALID);
      if (curVal==INVALID) tries++;
      else return curVal;
    }
    //Scan from a random position if we weren't able to find anything by the deadline
    for(int offset = rng.nextInt(data.length()), i=0; i<data.length() && !depleted; i++){
      final int pos = (offset + i) % data.length();
      final int curVal = data.getAndSet(pos, INVALID);
      if (curVal != INVALID) return curVal;
    }
    depleted = true;
    return INVALID;
  }
}