algorithm - 生成大量唯一随机数(理论上)

Question

这是一个理论问题；作为一名计算机科学爱好者，我一直在思考这个问题，并且正在尝试理解可能(或正在)用于解决这个问题的逻辑和方法。

问题:假设您有一个数字空间可以在其中漫游以获取某种 ID 值。您需要在此空间内生成随机数。

要求:

• 在此数字空间内，任何数字都不应多次生成，永远生成。当所有数字都用完时，您的“生成”算法失败是可以的。它失败比默默地生成重复项更好，但至少它应该在做欺骗之前用尽所有数字。生成的数字将用作唯一 ID 值。
• 一组本地生成的数字应尽可能随机。例如:
  • 如果一秒钟内生成 100 个数字，然后以每天一个的速度生成另外 100 个数字，则集合的“随机性”应该几乎没有可检测到的差异。
  • 给定一个数字甚至一组数字，“尽可能不可能”对这些数字进行统计分析以确定其生成时间、生成速度等特征。
• 对于这个思想实验，假设 ID 重叠是最坏的情况，不允许发生。 (例如，假设重叠的 ID 可能会导致巨大的安全漏洞，从而导致诉讼，使您的组织在雨天陷入众所周知的纸板箱。)但是，可统计分析的数字字符串也可能证明是有害的 - 例如:如果有人能找出一种模式，他们就可以猜出 ID 并访问其他人的私有(private)数据。

我考虑了四种方法来生成这些巨大的唯一数字集:

• 天真的方法:只使用大数字空间并使用基于密码算法的数字生成器。这个想法是，理论上 key 空间应该很大，以至于给定一个好的算法，两个值可能重叠“不太可能”。如果您可以为您的 ID 使用足够大的数字空间(例如 256 位)，这可能就足够了。但是，如果您必须将 ID 限制为 64 位，那么重叠的可能性就太大了。
• 极其不可扩展的方法:每次生成一个数字时，在已生成的数字列表中搜索它。这适用于小型数据集，但想象一下，如果您生成了 50 万亿个 ID，现在您必须每次都扫描该列表，以确保您刚刚生成的 ID 未被使用。
• “可扩展”方法:与之前的想法相同，但构建一个能够对大量数据集进行快速查询的优化数据库。实际使用的一种简单方法是制作 100 个表 - 所有以数字 00 结尾的数字都在第一个，01 在下一个，依此类推 - 然后你可以缩小范围并优化你的数据库查询迅速地。
• 使用 GUID 算法之类的算法来生成有保证的唯一编号。这是不合适的，因为 GUID 确实有一个“结构”，大多数生成器都会遵循它，因此它的数据不是随机，而是唯一的。

当然，如果不考虑实际用例，我就没有“最佳”选项。我对这类问题带给我的思想和逻辑实验更感兴趣，并且有兴趣听听是否有人使用其他技术或至少想到其他技术来解决这样的问题。您确实会在 YouTube 中看到至少部分类似的内容，其中包含视频 ID。当然，Google 是一家可以在不到一秒钟内为您“搜索互联网”的公司，因此他们的方法可能不适合“其他所有人”。

Answer 1

这是理论上的答案。

由于在此数字空间内，任何数字都不应多次生成，因此该算法有效地生成了数字空间的一些排列。这暗示它应该选择一个特定的排列，并按顺序生成它。

如果空间大小为 N，则有 N! 种可能的排列。给定排列索引，很容易generate it ，一次一个元素。随机选择一个排列，并生成它。

选定的排列有可能是一个身份(生成 0, 1, 2, ... ID 序列)。它看起来不是很随机，但攻击者仍然无法预测它。