Thread safe unique number generator

Question

How to implement java thread-safe generator of unique numbers? This is my version

public class Generator {
    List<Integer> list = new ArrayList<>();

    public Generator() {
        for (int i = 0; i < 1000; i++) {
            list.add(i);
        }
    }

    public Integer generate() {
        Collections.shuffle(list);
        return list.get(0);
    }
}

But theoretically, when shuffling can get a unique number. How to achieve uniqueness? Do I need to sync across my collection when I shuffle, i.e.

synchronized (list) {
    Collections.shuffle(list);
}

Thanks.

Well, it's not unique. `get(0)` might return the same number. — markspace, Mar 24 '19 at 19:21

markspace · Accepted Answer · 2019-03-25T19:02:28.717

There's two issues here, Safe Publication and then the subsequent thread safety of the mutate (shuffle()) followed by a read (get(0)).

I don't think your code address safe publication at all. Use volatile or final for that, and for volatile do the assignment last in the ctor.

public class Generator {
    private final List<Integer> list = new ArrayList<>();

    public Generator() {
        for (int i = 0; i < 1000; i++) {
            list.add(i);
        }
    }

Or

public class Generator {
    private volatile List<Integer> list; 

    public Generator() {
        List<Integer> temp = = new ArrayList<>();
        for (int i = 0; i < 1000; i++) {
            temp.add(i);
        }
        list = temp;
    }

Now I think you can synchronize on list (or any other object) to get thread safety. You have to make sure the get is inside the synchronized block. Note that your code has a bug and doesn't actually produce unique numbers.

public Integer generate() {
  synchronized( list ) {
    Collections.shuffle(list);
    return list.get(0);
  }
}

Or

public synchronized Integer generate() {
    Collections.shuffle(list);
    return list.get(0);
}

See Brian Goetz Java Concurrency in Practice for more, esp. Safe Publication. SO has a short discussion of the Safe Publication pattern too.

Getting unique numbers is just logic, not related to thread safety. First shuffle only once in the ctor, then just increment a counter to return numbers in order. Remember your list only has 1000 numbers so you can return at most 1000 unique numbers.

private int index;
public synchronized Integer generate() {
    if( index >= 1000 ) throw IllegalArgumentError();
    return list.get( index++ );
}

Thanks for your answer. I know, that this generator can return not unique number, how can i achieve uniqueness? — Jaive, Mar 24 '19 at 19:42

score 0 · Answer 2 · answered Mar 24 '19 at 19:24

0

I am guessing here (sorry if off base), that you're looking for a random number between 0 <= x < 1000:

ThreadLocalRandom.current().nextInt(1000);

answered Mar 24 '19 at 19:24

Not a JD

1,864
6
14

Need to create generator without using Random and ThreadLocalRandom. – Jaive Mar 24 '19 at 19:30
...Collections.shuffle() uses random – Not a JD Mar 24 '19 at 19:34
@NotaJD , will it be unique if I spawn different thread at the same second to get the value? – Panadol Chong May 12 '21 at 09:02

Thread safe unique number generator

2 Answers2