在Ruby中将唯一种子字符串转换为随机但确定的浮点值

Question

从概念上讲,我在这方面遇到了困难.

基本上,我需要接受一些任意的唯一字符串,并能够将其转换为规范化的浮点值.输出浮点值的作用并不重要,只要相同的字符串输入始终导致相同的标准化浮点输出.

那么这是一个哈希算法吗？我熟悉SHA1或MD5,这看起来类似于密码哈希,其结果与正确的密码相同.但我相信这些方法会输出字符串.而我没有得到的是如何将SHA1或MD5的结果转换为一致的浮点值.

# Goal
def string_to_float(seed_string)
  # ...
end

string_to_float('abc-123') #=> 0.15789
string_to_float('abc-123') #=> 0.15789

string_to_float('def-456') #=> 0.57654
string_to_float('def-456') #=> 0.57654

那么我可以采用什么样的Ruby方法将任意字符串转换为随机但一致的浮点值？

Answer 1

您需要的关键部分是将SHA1或MD5哈希输出转换为确定性和1-1的浮点数的方法.这是一个基于md5的简单解决方案.这也可以用作整数.

require 'digest/md5'

class String
  def float_hash
    (Digest::MD5.hexdigest(self).to_i(16)).to_f
  end
end

puts "example_string".float_hash  # returns 1.3084281619666243e+38

这会生成十六进制哈希,然后将其转换为整数,然后将其转换为浮点数.每一步都是确定性的.

注意:正如@emboss所指出的,这降低了抗冲突性,因为double是8个字节而hash是16个字节.虽然应用程序的声音不应该是一个大问题.

Answer 2

如果安全性没有问题，那么我认为您所描述的不是哈希函数。散列函数是一种单向函数，这意味着计算散列很容易，但还原它是“困难的”，或者理想情况下是不可能的。

你的需求描述了一个内射函数给定域 X 中的任何 x1, x2 ，以下内容成立：

For all x1, x2 element of X, x1 != x2  => f(x1) != f(x2)

f(x) = x 是这样的函数，f(x) = x² 不是。通俗地说：如果输入不同，你希望得到不同的结果，只有输入相同才会得到相同的结果。确实，这对于安全散列也是如此，但它们还提供了单向特性，例如如果仅给定 f(x) 则无法（轻松）找到 x 的属性等。据我了解，您不需要这些安全属性。

简单地说，从现在开始，通过简单地将“字符串字节”解释为“浮点字节”，可以给出从字符串到浮点数的这种单射映射，即您以不同的方式解释字节（想想 C:

unsigned char *bytes = "...";
double d = (double)bytes; 

）。但是，这也有缺点 - 真正的问题是 Float 具有最大精度，因此如果您的字符串太长，您将遇到溢出情况（浮点数在内部表示为double值，在 32 位机器上为 8 个字节）。所以几乎没有足够的空间容纳任何用例。即使首先对字符串进行 MD5 处理也不能解决问题 - MD5 输出已经是 16 字节长。

因此，这可能是一个真正的问题，具体取决于您的确切要求。尽管 MD5（或任何其他散列）将与输入充分混淆以使其尽可能随机，但您仍将可能值的范围从 16 个字节减少到有效的 8 个字节。（注意：在保留随机性方面，将随机 16 字节输出截断为 8 字节通常被认为是“安全的”。椭圆曲线密码学做了类似的事情。但据我所知，没有人能真正证明这一点，但也没有人能证明到目前为止相反）。因此，与您受限的 Float 范围发生碰撞的可能性更大。根据生日悖论，找到碰撞需要 sqrt（有限范围内的值的数量）尝试。对于 MD5，这是 2^64，但对于您的方案，它仅为 2^32。这仍然非常非常不可能产生碰撞。它' 可能是中奖的顺序，同时被闪电击中。如果你能忍受这种最小的可能性，那就去做吧：

def string_to_float(str)
  Digest::MD5.new.digest(str).unpack('D')
end

如果唯一性是绝对优先的，我会建议从浮点数转移到整数。Ruby 内置了对不受long值内部约束限制的大整数的支持（这就是 Fixnum 归结为）。因此，任何任意散列输出都可以表示为一个大整数。