node.js - 如何有效地创建一个包含不同 UUID 的大列表？

Question

我想为一个事件生成门票。我需要生成很多，因此我决定将票号作为 UUID。问题是如何生成一个大的 UUID 列表并且它是不同的。

我知道检查现有列表中生成的每个新 UUID 的简单方法，但这对性能不是很友好。 :)

我正在使用带有 UUID v4 的 NodeJS。

谢谢!

Answer 1

您可以使用自制的 UUID 函数，它保证是 [0...2¹²⁸) 范围内的唯一伪随机整数。下面是一个基于 Linear Contguential Generator 的.常量取自 here或 here .您只需要保留之前的数字/UUID 即可生成下一个，无需检查，因为它只会在 2¹²⁸ 的完整周期后重复。

代码依赖 BigInt，使用 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

更新

只是为了在手头的问题上更具哲学性:

1. 您可以将 UUID4 视为黑盒并相信它 - 这是@ChrisWhite 提出的建议
2. 您可以将 UUID4 视为黑匣子并且不信任它 - 这是您建议检查列表或由@KevinPastor 回答的内容
3. 制作你自己的透明盒子，它可以产生适当范围内的数字并且是独一无二的 - 这是我的建议

LCG 方法的美妙之处在于，给定良好的乘法器和进位，它唯一且可逆地将范围 [0...2¹²⁸) 映射到自身(它可以对 64 位数字执行此操作，具有不同的a、c 或 32 位数字等等)。您甚至可以使用从 0 开始到 2¹²⁸-1 的计数器作为输入，它会在相同范围内生成不可重复的数字，填充整个 [0...2¹²⁸).所以您知道，如果您将它与之前的 uuid 链接起来，或者使用计数器，则发生冲突的可能性为 0。