如何生成唯一的、可预测的、可重复的、非连续的字母数字标识符？

Question

我必须生成由四个字母数字字符组成的标识符，例如B41F.

我有以下要求：

每个标识符必须是唯一的（没有用于查找现有标识符的中心位置）
标识符不能明显连续（例如 1A01、1A02）
一定是可以预见的
仅使用标识符索引必须是可重复的（在两个不同的环境中，生成的第 N 个具有索引 N 的标识符必须相同）

该问题对任何语言都是通用的。我的实现将在 dart 中完成。

我认为这可以通过 PRNG 和一些 LUT 来完成，但是如果不重放整个序列，我找不到任何符合要求 4) 的实现或伪代码。此外，一些 PRNG 实现有一个随机组件，不能保证在库更新时可重复。

我怎样才能做到这一点？我正在寻找伪代码、代码或提示。

Answer 1

当标识符必须唯一时，您不应使用 PRNG。 RNG 不保证唯一性。有些人可能需要很长时间才能重复，但这是他们的全部 bit-range，将其减少到较小的数量可能会导致更早的冲突。

您的标识符实际上只是以 36 为基数的数字，因此您需要 shuffle(index).toRadixString(36) 之类的东西来生成它。

棘手的一点是 shuffle 函数，它必须是数字 0..36^4-1 的排列，看起来是随机的 (non-sequential)，但可以计算 (有效？）对于任何输入。

因为 36^4 不是 2 的幂，所以大多数简单的 bit-shuffles 可能都行不通。

如果你只能接受 32^4 个数字 (2^20 ~ 1M) 可能会更容易。然后，您还可以选择从结果中删除 O、I、0 和 1，这可能更易于阅读。

在那种情况下，我会做一些原始的事情（根本不是加密安全的），比如：

// Represent 20-bit numbers
String represent(int index) {
  RangeError.checkValueInInterval(index, 0, 0xFFFFF, "index");
  var digits = "23456789ABCDEFGHJKLMNPQRSTUVWXYZ";
  return "${digits[(index >> 15) & 31]}${digits[(index >> 10) & 31]}"
       "${digits[(index >> 5) & 31]}${digits[index & 31]}";
}

// Completely naive number shuffler for 20-bit numbers.
// All numbers made up on the spot.
int shuffle(int index) {
  RangeError.checkValueInInterval(index, 0, 0xFFFFF, "index");
  index ^= 0x35712;
  index ^= index << 15;
  index ^= index << 4;
  index ^= index << 12;
  index ^= index << 7;
  index ^= index << 17;
  return index & 0xFFFFF; // 20 bit only.
}

如果您真的想要使用完整的 36^4 范围，我可能会做类似洗牌的事情，但是在 base-six 算术中。也许：

String represent(int index) =>   
    RangeError.checkValueInInterval(index, 0, 1679615, "index")
        .toRadixString(36).toUpperCase();

int shuffle(int index) {
  RangeError.checkValueInInterval(index, 0, 1679615, "index");
  const seed = [1, 4, 2, 5, 0, 3, 1, 4]; // seed.
  var digits = List<int>.filled(8, 0);
  for (var i = 0; i < 8; i++) {
    digits[i] = index.remainder(6);
    index = index ~/ 6;
  }

  void shiftAdd(List<int> source, int shift, int times) {
    for (var n = digits.length - 1 - shift; n >= 0; n--) {
      digits[shift + n] = (digits[shift + n] + source[n] * times).remainder(6);
    }
  }

  shiftAdd(seed, 0, 1);
  shiftAdd(digits, 3, 2);
  shiftAdd(digits, 5, 1);
  shiftAdd(digits, 2, 5);
  var result = 0;
  for (var i = digits.length - 1; i >= 0; i--) {
    result = result * 6 + digits[i];
  }
  return result;
}

同样，这是我当场编造的东西，它“洗牌”，但不保证结果的属性，除此之外它们看起来顺序。

如何生成唯一的、可预测的、可重复的、非连续的字母数字标识符？

How can I generate a unique, predictable, repeatable, non sequential alphanumeric identifier?

dart

pseudocode