JavaScript中从已知的潜在ID集合快速创建唯一字符串ID/键的方法

Question

假设你想要一组1到2位的十六进制数字，也就是256个数字。只需使用一个小集合来解决问题，但任何大小的字符串都可以使用该方法。因此，在这种情况下，您有一个潜在的N或256个数字。每当出现新数据记录时，您将“生成”一个新的ID。所以它开始并随机给出 af，然后是 1d，然后是 8a等等。直接而幼稚的方法是按顺序生成所有数字，然后打乱它们并从集合中弹出。当您只有256个数字时，这样做很好。但如果您有数百万或数十亿个数字，则不实用，因为您可能会有许多浪费的已生成ID长时间未被使用。我想避免这种情况。因此，我的问题是，有没有一种更快速的方法来创建这样的唯一键字符串，而不需要预先生成所有键，并且不需要按顺序递增1。也就是说，关键字应该看起来是随机的。我能想象的一种方法是使用trie存储已使用/生成的值。然后，当您要获取新值时，生成一个随机值，然后检查trie以查看它是否已经使用过。虽然我不知道如何衡量其效率，但一旦您开始耗尽ID并降到集合中的最后几个ID，它似乎表现非常糟糕。您将生成许多已经生成的ID，并为每个ID遍历字典树，因此速度会很慢。我想知道是否有一种更有效的方法可以在不预先生成所有数字的情况下实现这一点。此外，数据记录不会用于计算ID，因为记录可能非常大且复杂。也许有一种方法可以随机遍历（并生成）字典树，以这种方式生成ID，因为您最终在trie中处于唯一的随机位置。也许是这样，我不知道。另外，我对哈希技术不太精通，因此不知道是否有任何好的方法可用。

- Lance

---

输入数据不会用于生成ID，因为它们可能是非常大和复杂的对象。 - Lance

请删除主观用语，如“最快的方式”。在担心使其更快之前，请先解决您的问题。 - Mulan

我知道如何用已经描述的慢方法解决问题，因此是最快的方法。 - Lance

@user633183嗯，他*确实有一种方法来解决当前的问题，只是当他接近上限时速度会变得非常慢。 - CertainPerformance

如果您真的只使用普通计数器，例如 1、2、3 等，但是将结果哈希为 ID，会怎样呢？这样，ID 将是唯一的，并且仅在需要时生成，但是它们在脚本之外没有任何明显的含义或顺序（我猜哈希可以转换回数字，如果您需要数字而不是字符串）。 - CertainPerformance

Answer 1

我假设您可以生成顺序ID；也就是说，您有一种可靠的方法来准确地知道到目前为止已经生成了多少个ID。然后，只需使用任何合理快速的加密算法对此计数进行加密即可。

加密将在计数作为二进制数字上完成，并且使用大多数算法的加密结果将是相同的大小，也是二进制的。如果需要，您可以使用base-64或hex编码结果，以使其更容易用作字符字符串。

由于加密必须是双射（也就是一对一映射），以便能够进行解密，因此这保证每次都会产生不同的结果，直到总ID计数溢出为止。如果它是一个合理的加密函数，那么结果将看起来是随机的（否则密码将容易受到攻击）。

- rici

---

这正是我在一天前回答中概述的完全相同的过程，但使用 "encryption" 作为混合函数... https://dev59.com/kLHma4cB1Zd3GeqPOqWj#54549632 - bernie

@bernie：我想这是真的；我没有仔细阅读你的答案。这些事情经常发生；我经常会发现我的答案被重复，有时候是几年后。我猜建议使用加密的好处在于大多数程序员都知道如何找到一个库来做到这一点，而“混合函数”听起来像是需要研究和实现的东西。然而，显然两个答案都不是OP所寻找的，所以我想可能存在其他未指明的限制。 - rici

Answer 2

我不确定它的性能如何，但我的想法是使用一个object或Map和Math.random()

let obj = {}

function generateRandomId(){
  let id = Math.abs( 0.5 - Math.random()) * 1000
  if(obj[id]){
   generateRandomId() 
  } else {
    obj[id] = true
  }
  return id
}

console.log(generateRandomId())
console.log(generateRandomId())
console.log(generateRandomId())
console.log(generateRandomId())

但是如果您可以使用模块，我发现这个模块最有用

uuid 这将生成RFC4122 UUIDS。

- Code Maniac

---

99.99% 安全。如果包括 Date.now(); 来避免重复的 ID，则为 100%。 - user3119231

Answer 3

我认为混合函数是你想要的。它会在输入中移动位，以产生相同长度的输出。它是可逆的，因此每个输入对应一个唯一的输出。

由于您希望输入数据不参与id生成，因此您需要一个代理id。您可以为每个记录分配一个递增的id，并使用混合函数来混淆id。

您将得到类似以下内容：

• 记录A => id == 1 => mixed id == 0x7ed55d16
• 记录B => id == 2 => mixed id == 0xc761c23c
• 等等。

请参见此处以获取一些灵感：

• https://crypto.stackexchange.com/questions/12145/need-32-bit-mixing-function-that-has-perfect-avalanche-between-octets
• https://gist.github.com/badboy/6267743

- bernie

---

这个问题是一个动态目标！我稍微修改了答案以满足那个要求。 - bernie

请问您能否推荐一个实现方案？这些方案看起来都很复杂，我不知道如何评估它们的使用情况。 - Lance

在我的例子中，我使用了类似于“8a”这样的2位十六进制值，但是你有非常大的值“0x7ed55d16”。看起来混合函数都产生了非常大的值，所以这是不正确的 :/ 这些值应该与输入的大小相同，因此为256或更小。 - Lance

@LancePollard 嗯，到底是哪一个？你说你想处理“数百万或数十亿的数字”。在我继续处理之前，请澄清一下你的需求。 - bernie

我希望它与样本大小成比例。因此，如果有256个可能的值，在十六进制中它应该最多只有2个字符，但如果有100万个值，那么一个32位整数或十六进制值就可以了。 - Lance

Answer 4

我认为在速度、灵活性和效率之间应该有一些权衡。

一方面，伪随机生成器将给您提供均匀分布的密钥，并且生成速度相对较快。但是检查现有ID将会很慢。您可以使用布隆过滤器（节省内存）或尝试其他方法，但是随着时间的推移，您应该增加空间。

另一个选择是使用格雷码，它将产生每个密钥（但不是随机顺序）。您需要跟踪最后发出的代码。

- Mariy

Answer 5

我在考虑类似这样的东西：

var trie = buildTrie()
var id1 = genId(trie)
var id2 = genId(trie)

console.log(id1,id2)

function buildTrie() {
  var trie = buildNode(0)
  return trie

  function buildNode(level) {
    if (level == 7) { // 8 bits
      var node = {
        available: true,
        leaf: true
      }
      return node
    } else {
      var a = buildNode(level + 1)
      var b = buildNode(level + 1)
      var node = {
        availableLeft: true,
        availableRight: true,
        left: a,
        right: b
      }

      a.parent = node
      b.parent = node

      return node
    }
  }
}

function genId(node) {
  var bytes = []
  step(node, bytes)
  var id = parseInt(bytes.join(''), 2).toString(16)
  return id

  function step(node, bytes) {
    if (node.leaf) {
      node.available = false
      var c = node
      var p = c.parent
      while (p) {
        if (p.left == c) {
          p.availableLeft = false
        } else if (p.right == c) {
          p.availableRight = false
        }

        if (!p.availableLeft && !p.availableRight) {
          c = p
          p = p.parent
        } else {
          p = false
        }
      }
    }

    var randomDirection = Math.random() >= 0.5
    if (randomDirection) {
      if (node.availableLeft) {
        bytes.push(0)
        step(node.left, bytes)
      } else if (node.availableRight) {
        bytes.push(1)
        step(node.right, bytes)
      }
    } else {
      if (node.availableRight) {
        bytes.push(1)
        step(node.right, bytes)
      } else if (node.availableLeft) {
        bytes.push(0)
        step(node.left, bytes)
      }
    }
  }
}

可能有更好的方法。

- Lance

---

这是一棵二叉树，因此您有2^{nbLevels + 1} - 1个包含几个字段的节点。每个节点也在buildTrie()中预先构建。这将快速使用大量内存，适用于“数百万或数十亿个数字”。 - bernie

@bernie，你有没有什么更节省空间的建议？可以参考一下这个链接：(https://dev59.com/gHVC5IYBdhLWcg3wlyMo)。 - Lance

我在你的问题中没有看到任何需要真正随机分配ID的内容。这是一个要求还是你只是想为每个数据记录提供一个不明显的标识符？如果不需要真正的随机性，那么我的答案比较紧凑，每个记录只存储一个数字。否则，使用的随机ID需要存储在某个地方（哈希表、trie、数组等）。 - bernie

谢谢，那样说得通。不，我只是不想要递增的ID。 - Lance