How to create a big list of different UUIDs, efficiently?

Question

I want to generate tickets for an event. I need to generate a lot of them and I decided to have the ticket number as UUIDs. The question is how to generate a big list of UUIDs and it to be different.

I know the easy way to just check every new UUID generated in the already existing list, but this is not very performance friendly. :)

I am using NodeJS with UUID v4.

Thank you!

Answer 1

You could use home-grown UUID function, which is guaranteed to be unique pseudo-random integer in the range [0...2¹²⁸). Below is one based on Linear Contguential Generator. Constants are taken from here or here. You only need to keep previous number/UUID at hands to generate next one, no need to check because it will be repeated only after full period of 2¹²⁸.

Code relies on BigInt, tested with node v12

const a = 199967246047888932297834045878657099405n; // should satisfy a % 8n = 5n
const c = 1n;                                       // should be odd
const m = (1n << 128n);
const mask = m - 1n;

function LCG128(state) {
    return (BigInt(state) * a + c) & mask; // same as % m
}

q = 7654321n; // seed

q = LCG128(q);
q.toString(16); // first UUID

q = LCG128(q);
q.toString(16); // second UUID

q = LCG128(q);
q.toString(16); // third UUID

UPDATE

Just to be a more philosophical on the issue at hands:

1. You could consider UUID4 to be black box and trust it - this is what @ChrisWhite proposed
2. You could consider UUID4 to be black box and distrust it - that is whatyou proposed to check in the list or answer by @KevinPastor
3. Make your own transparent box which produces numbers in the proper range and be unique - that is my proposal

Beauty of LCG approach is that, given good multiplier and carry, it uniquely and reversable maps range [0...2¹²⁸) into itself (it could do that for 64bit numbers, with different a, c, or 32bit numbers and so on and so forth). You could even use counter as input starting with 0 up to 2¹²⁸-1 and it will produce non-repeatable numbers in the same range filling whole [0...2¹²⁸). So you know that if you either chain it with previous uuid, or use counter, there is 0 chances of collision.