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

Question

假设您想要一组 1 到 2 位的十六进制数，即 256 个数。只需使用一小部分即可解决问题，但它适用于任何大小的字符串。

因此在这种情况下，您有潜力 N 或 256 个号码。您将为遇到的每条新数据记录 "generate" 一个新 ID。所以它开始并随机给你af，然后是1d，然后是8a，等等

最直接、最天真的方法就是简单地按顺序生成所有数字，然后将它们洗牌，然后从集合中弹出。当您只有 256 个数字时，这很好用。但是，如果您有数百万或数十亿个数字，这是不切实际的，因为您可能有很多腰部生成的 ID 长时间未使用。我想避免这种情况。

所以我的问题是，创建这样一个唯一密钥字符串的最快方法是什么，无需提前生成所有密钥字符串，也无需按顺序递增 1 或诸如此类的东西。也就是说，密钥应该是看似随机的。

我能想到的一种方法是使用 trie 来存储已经 used/generated 的值。然后，当您要获得一个新值时，您会生成一个随机值，然后检查 trie 以查看它是否已被使用。我不知道如何判断这是多么有效，但是一旦你开始运行出 ID 并且下降到集合中的最后几个，它的表现似乎会非常糟糕。你会生成很多已经生成的 ID，并为每个 ID 遍历 trie，所以它会很慢。

我想知道是否有更有效的方法来执行此操作，而无需提前生成它们。此外，数据记录不会用于计算 ID，因为记录可能非常大和复杂。

也许有一种方法可以一次随机遍历（并生成）一个 trie，并以这种方式生成 ID，因为你最终会在 trie 中的一个独特的随机位置。大概是这样吧，我不知道。

此外，我对散列不熟悉，所以我不知道是否有任何好的方法。

Answer 1

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

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

你会得到类似的东西：

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

查看此处获取一些灵感：

Answer 2

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

一个伪随机生成器将为您提供均匀分布的密钥，并且生成速度相当快。但是检查现有的 id 会很慢。您可以使用布隆过滤器（节省内存）或尝试，但正如您在某些时候所说的那样，您应该增加 space.

另一种选择是使用 Gray code 这将生成每个密钥（但不是随机顺序）。您需要跟踪最后发布的代码。

Answer 3

我不确定它的性能如何，但我的想法是使用 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。

Answer 4

我正在考虑这样的事情：

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)
      }
    }
  }
}

也许有更好的方法。

Answer 5

我假设您可以生成顺序 ID；也就是说，您可以通过可靠的方式准确了解迄今为止生成了多少个 ID。然后用任何相当快的加密算法加密这个计数就足够了。

加密将以二进制数的形式进行，大多数算法的加密结果大小相同，也是二进制的。如果需要，您可以对结果进行 base-64 或十六进制编码，使其更易于用作字符串。

由于加密必须是双射（即一对一映射）才能解密，因此每次都保证产生不同的结果，直到总 ID 计数溢出。如果它是一个合理的加密函数，那么结果将是随机的（否则密码将容易受到攻击）。

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

Fast way to create a unique string ID/key from a known set of potential IDs in JavaScript

javascript

algorithm

trie

id-generation

data-structures