3

我正在尝试使用一种算法来为我的 rails 应用程序中的模型生成唯一的非顺序标记。

例如：

MyModel.create.token #=> '183685'
MyModel.create.token #=> '456873'
MyModel.create.token #=> '813870'

我能想到的唯一方法是创建一个随机的东西，检查冲突，然后重试。对我来说，这似乎是一种很臭的代码，以某种力量的方式。

class MyModel < ActiveRecord::Base
  before_create :set_token

  def set_token
    existing_model_count = nil

    # Loop while we have a token that already belongs to an existing model.
    while existing_model_count.nil? || existing_model_count > 0
      random_token = TokenGenerator.random_token
      existing_model_count = MyModel.where(token: random_token).count
    end

    # Loop exited, meaning we found an unused token.
    self.token = random_token
  end
end

有没有更好的方法来做到这一点，它不涉及while将迭代未知次数的循环？

虽然这里的示例是 ruby​​，但这是一种适用于任何语言的通用算法问题，因此欢迎使用其他语言的解决方案。

4

6 回答 6

6

如果您的“令牌”是某个范围内的整数值，并且您事先知道令牌的数量，那么简单的 Bob Floyd 算法（在 Bentley 的“Programming Peals”或此处描述）会生成一个唯一的随机数而无需重试。它使用额外的存储来“标记”已经使用的数字，但如果随机生成的数字已经被占用（即没有重复的试错迭代），它仍然巧妙地设法立即提出一个未使用的数字。

但是，该算法的一个问题是，即使它生成的数字通常不是有序的，但顺序仍然不是完全随机的。换句话说，即使该算法保证了它从范围中挑选的每个单独数字的均匀分布，它也不能保证结果序列在所有可能的结果序列中的均匀分布。

这对您来说是否重要 - 只有您可以决定。如果您生成的令牌数量与范围的长度相比较小，那么此算法将提供非常令人满意的结果。如果标记的数量接近范围的长度，则该算法将生成“几乎排序”的序列。

于 2013-03-22T21:09:08.487 回答
2

一种方法是混淆数字。我在我的文章Obfuscating Sequential Keys中详细解释了这一点。代码示例是 C#，但应该不难翻译。

于 2013-03-22T21:33:58.867 回答
2

每隔几个小时运行一次 cronjob，使用未使用的标识符重新填充 Redis 集合。让它在后台运行，所以当你需要它时，只需将它从 Redis 集合中弹出即可。

于 2013-03-22T22:22:40.973 回答
2 
cipher = OpenSSL::Cipher::AES.new(128, :CBC).encrypt
cipher.update(MyModel.create.object_id.to_s(36))
于 2013-03-22T22:34:11.423 回答
1

从序列中取出数字。实施 feistel 网络来打乱号码。我在这里找到了一个例子：https ://gist.github.com/Xeoncross/3715367

于 2013-03-22T21:24:36.587 回答
1

您可以使用SecureRandom.uuid. 我认为它保证了唯一的随机 UUID 令牌。

于 2013-03-22T21:57:35.393 回答