哈希函数（例如SHA1）的随机性

Question

我正在尝试根据用户ID生成均匀的随机数分布。也就是说，我希望为每个用户提供一个随机数，该随机数在用户请求随机数时保持不变（但用户无需存储该数）。对于给定的大量userID，我当前的算法（在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都是唯一的吗？

Answer 1

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