2

我正在尝试根据用户 ID 生成随机数的均匀分布。也就是说，我希望每个用户的随机数在用户请求随机数时保持不变（但用户不需要存储该数字）。对于给定的大量用户 ID，我当前的算法（在 PHP 中）计算分布$arr是：

$range = 100;
$results = array_fill(0, $range, 0);

foreach ($arr as $userID) {
    $hash = sha1($userID,TRUE);
    $data = unpack('L*', $hash);
    $seed = 0;
    foreach ($data as $integer) {
        $seed ^= $integer;
    }
    srand($seed);
    ++$results[rand(0, $range-1)];
}

人们希望这会产生近似均匀的分布。但事实并非如此！我已经检查以确保其中的每个值$arr都是唯一的，但列表中的一个条目总是比其他所有条目获得更多的活动。有没有更好的方法来生成一个字符串的哈希值，它会给出一个近似均匀的分布？显然 SHA 不能胜任这项工作。我也试过 MD5 和一个简单的 crc32，结果都一样！？

我疯了吗？实际上，我没有验证的唯一解释是每个条目$arr都是唯一的吗？

4

4 回答 4

5

sha1 哈希数分布非常均匀。执行此操作后：

<?php

$n = '';
$salt = 'this is the salt';

for ($i=0; $i<100000; $i++) {
    $n .= implode('', unpack('L*', sha1($i . $salt)));
}   

$count = count_chars($n, 1);
$sum = array_sum($count);

foreach ($count as $k => $v) {
    echo chr($k)." => ".($v/$sum)."\n";
} 

?>

你得到这个结果。每个数字的概率：

0 => 0.083696057956298
1 => 0.12138983759522
2 => 0.094558704004335
3 => 0.07301783188663
4 => 0.092124978934097
5 => 0.088623772577848
6 => 0.11390989553446
7 => 0.092570936094051
8 => 0.12348330833868
9 => 0.11662467707838

您可以使用 sha1 作为基于用户 ID 的简单随机数生成器。

在十六进制中，分布接近完美：

//  $n .= sha1($i . $salt, false);

0 => 0.06245515
1 => 0.06245665
2 => 0.06258855
3 => 0.0624244
4 => 0.06247255
5 => 0.0625422
6 => 0.0625246
7 => 0.0624716
8 => 0.06257355
9 => 0.0625005
a => 0.0625068
b => 0.0625086
c => 0.0624463
d => 0.06250535
e => 0.06250895
f => 0.06251425
于 2012-08-01T23:52:10.433 回答
1

mt_rand()在请求的范围内应该有一个非常均匀的分布。创建用户时，为该用户创建一个随机种子，mt_rand()然后始终为该用户使用mt_srand()该种子。

要获得从 0 到 99 的均匀分布，例如，只需mt_rand(0,$range-1). 使用 sha1、md5 或其他一些散列算法进行技巧不会真正为您提供比直接随机更均匀的分布。

于 2012-08-01T23:39:01.480 回答
0

如果您发布的结果导致您得出结论认为您没有获得适当的分布，那将会很有帮助，但这里可能发生了以下三件事之一：

  1. 您只是在查看太小的样本，和/或您错误地解释了您的数据。正如其他人所评论的那样，均匀分布没有完全均匀的输出是完全合理的。

  2. 如果您使用mt_rand而不是rand.

  3. （我个人认为这是最有可能的）你过度优化你的种子生成，并且丢失数据/鸽子洞/否则会损害你生成随机数的能力。阅读您的代码，我认为您正在执行以下操作：

    1. 生成未知值的统一随机散列
    2. 将散列拆分为长整数并将它们按位异或在一起
    3. 设置rand的种子，并从该种子中生成一个随机数

    但你为什么要做第 2 步？你认为你从中得到了什么好处？尝试走出这一步，只使用从哈希中提取的第一个值作为种子，看看这是否不会给你带来更好的结果。具有随机性的良好经验法则 - 不要试图智取实现算法的人，这是无法做到的 :)

于 2012-08-02T00:38:32.427 回答
0

虽然这里的所有答案都很好，但我会提供对我来说正确的答案，那就是我确实是疯了。显然，该uniq命令实际上并没有像我预期的那样工作（需要首先对数据进行排序）。所以解释确实是其中的值$arr不是唯一的。

于 2012-08-02T14:16:04.687 回答