3

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

因此，在这种情况下，您有一个潜在 N的或 256 个数字。您将为遇到的每条新数据记录“生成”一个新 ID。所以它开始并随机给你af, then 1d, then8a等。

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

所以我的问题是创建这样的唯一键字符串的最快方法是什么，而不是预先生成所有这些字符串，也不需要按顺序递增 1 或诸如此类。也就是说，密钥应该是看似随机的。

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

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

也许有一种方法可以一次随机遍历（并生成）一个 trie，并以这种方式生成 ID，因为您最终位于 trie 中一个唯一的随机位置。我不知道，也许是类似的东西。

另外，我对散列并不复杂，所以我不知道是否有任何好的方法。

4

5 回答 5

2

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

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

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

于 2019-02-06T17:05:18.980 回答
1

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

于 2019-02-06T08:58:15.550 回答
0

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

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

你会得到类似的东西：

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

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

于 2019-02-06T08:48:34.240 回答
0

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

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

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

于 2019-02-06T08:57:42.773 回答
0

我正在考虑这样的事情：

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

也许有更好的方法。

于 2019-02-06T09:26:31.150 回答