时间戳

首页 > 解决方案 > 如何有效地创建不同 UUID 的大列表？

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

问题描述

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

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

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

谢谢！

标签： node.jslistrandomuniqueuuid

解决方案

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

代码依赖 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 128）映射到自身（它可以对 64 位数字执行此操作，具有不同a的c, 或 32 位数字等等向前）。您甚至可以使用从 0 到 2 128 -1 开始的计数器作为输入，它会在填充整个 [0...2 128）的同一范围内产生不可重复的数字。所以你知道，如果你将它与之前的 uuid 链接起来，或者使用计数器，那么发生冲突的机会是 0。

推荐阅读