生成随机函数（而非随机数）

Question

我想创建一个函数，这个函数可以接收一个字符串，并返回一个介于0到1之间的数字。这个函数在接收到相同的字符串时应该总是返回相同的数字，但除此之外，返回的结果不应该有明显的规律。对于任何一大组输入字符串，输出的数字应该是均匀分布的。

此外，我需要生成多个这样的函数，也就是说，当输入字符串是“abc”时，函数A可能总是返回0.593927，而函数B则总是返回0.0162524。我希望这个过程快速（因为是用于数值模拟），并且统计结果要合理。

我使用的是Python，欢迎提供“这里有一个简单的方法可以使用Python库实现”或者“这里有一个你可以实现的算法”的答案。如果在Python中没有快速的方法，我就会考虑换用C语言。

我意识到以下两种方法都可以实现，但每种方法都有缺点，这让我想寻找一个更优雅的解决方案。

存储字典
我可以每次接收到新的字符串时计算一个新的随机数字，并将其存储在字典中，以便如果再次接收到相同的字符串时可以取出。但是，我的应用可能会生成很多只出现一次的字符串，这最终会导致需要在内存中存储一个非常大的字典。而且，这也使得结果的重复性变得更加困难，因为即使我使用相同的种子，如果以不同的顺序接收到相同的字符串，我也会生成不同的函数。因此，最好是能够“实时”计算随机数字。
使用哈希函数
我可以对字符串调用一个哈希函数，然后将结果转换为一个数字。关于生成多个函数的问题，可以通过在每个输入字符串后面添加一个“种子”字符串来解决。但是，这样我就得找到一个速度和统计效果都合适的哈希函数。Python内置的哈希函数速度很快，但它依赖于具体的实现，我不确定它的统计效果如何，因为它并不是为这种目的设计的。另一方面，我可以使用像md5这样的安全哈希算法，它的统计效果很好，但这对于我的应用来说速度太慢。针对数据存储应用的哈希函数通常比像md5这样的加密安全哈希函数要快得多，但它们的设计目的是避免碰撞，而不是产生均匀分布的输出，这两者在所有情况下并不一定相同。

关于哈希函数的进一步说明

为了说明避免碰撞和产生均匀结果是两回事，考虑以下使用Python内置哈希函数的例子：

>>> hash("aaa") % 1000
340
>>> hash("aab") % 1000
343
>>> hash("aac") % 1000
342
>>> hash("aad") % 1000
337
>>> hash("aae") % 1000
336
>>> hash("aaf") % 1000
339
>>> hash("aag") % 1000
338
>>> hash("aah") % 1000
349
>>> hash("aai") % 1000
348
>>> hash("aaj") % 1000
351
>>> hash("aak") % 1000
350

在上面的输出中没有碰撞，但它们显然也不是均匀分布的，因为它们都在336到351之间，并且第三位数字也有明显的规律。我意识到我可能通过做 (hash("aaa")/HASH_MAX)*1000（假设我能搞清楚 HASH_MAX 应该是什么）来获得更好的统计效果，但这应该有助于说明一个好的哈希函数的要求与我所寻找的函数的要求并不相同。

关于这个问题的一些相关信息

我并不知道这个算法需要处理的字符串具体是什么，因为这些字符串将由模拟生成，但以下情况很可能会出现：

它们的字符集非常有限（可能只有4或5种不同的符号）。
会有很多独特或稀有的字符串，以及一些非常常见的字符串，长度各异。
字符串的长度没有上限，但短字符串可能会比长字符串更常见。我不会感到惊讶如果我从未见过超过100个字符的字符串，但我并不确定。许多字符串可能只有一到三个字符，因此算法在处理短字符串时的速度很重要。（不过我想我可以为长度小于某个值的字符串使用查找表。）
通常，这些字符串会有很大的公共子串——往往两个字符串只是在开头或结尾多了一个字符。算法在处理相似字符串时，输出值不应该过于相似，这一点很重要。

字符串处理哈希函数数值模拟均匀分布字典存储随机函数碰撞避免统计效果

生成随机函数（而非随机数）

4 个回答

撰写回答