你能解释一下MD5和模数这些令人不安的反常现象吗？ [英] Can you explain theese disturbing anomalies of md5 and modulo?
问题描述
好的，这个标题真的很主观。但这就是我的问题所在。
背景是，我希望将静态Web内容的命中内容均匀分布在定义数量的缓存服务器上。此外，由于多个域正在使用中，并且请求不会相互阻塞，因此向客户端的传输速度应该会加快。我也不需要经典的负载均衡器，而是立即在我的html代码中生成正确的链接。我还希望确保相同的URL始终由同一服务器提供。
所以我只定义了一个小函数，它通过散列请求url返回要使用的主机，并根据正在使用的服务器数量计算模数：
function pseudocode_statify($url) { // $url looks like /folder1/folder2/file.jpg
return 'http://' . md5($url) % $num_of_servers .'.mydomain.com' . $url;
}
我首先使用十六进制解码和子字符串来防止就地溢出，但发现上面的方法工作得很好。
然而，我的问题是，如果我运行以下测试脚本：
for($i=0;$i<100000;$i++) {
$md5 = md5(uniqid($i).microtime().rand(1,999999999999));
$result[$md5%2]++;
}
我预计是均匀分布的。表示$Result[0]将接近$Result[1]的值；
情况并非如此。
好的，到目前为止这没什么特别的。我只会接受这样一个事实，即MD5并不像我想象的那样均匀分布，并且可能会使用另一种散列算法，如SHA1或其他什么。
但我试图复制这些发现，发现了一个我无法解释的模式。
比例总是在2/1左右。事实上，比例总是在1/2.16到1/2.17之间
上述脚本的一些运行的示例输出：
output was generated by: echo "ratio: ".$result[0]/$result[1]."
";
ratio: 2.1757121534504
ratio: 2.1729411578062
ratio: 2.1726559360393
ratio: 2.1676895664225
ratio: 2.1667416128848
ratio: 2.1667115284133
ratio: 2.1677791605385
ratio: 2.1658969579688
ratio: 2.1668508131769
ratio: 2.1689292821741
现在奇怪的是，sum%2等于1和sum%2等于0的比率有时会交替！
for($j = 0; $j<100;$j++) {
for($i=0;$i<100000;$i++) {
$md5 = md5(uniqid($i).microtime().rand(1,999999999999));
$result[$md5%2]++;
}
var_dump($result);
}
我从命令行运行了该脚本两次，在运行了三次后中止了它，它产生了两个输出：
joe@joe-laptop:/home/flimmit/httpdocs$ php test.php
PHP Notice: Undefined variable: result in /home/flimmit/httpdocs/test.php on line 6
PHP Notice: Undefined offset: 0 in /home/flimmit/httpdocs/test.php on line 6
PHP Notice: Undefined offset: 1 in /home/flimmit/httpdocs/test.php on line 6
array(2) {
[0]=>
int(68223)
[1]=>
int(31777)
}
array(2) {
[0]=>
int(136384)
[1]=>
int(63616)
}
array(2) {
[0]=>
int(204498)
[1]=>
int(95502)
}
^C
joe@joe-laptop:/home/flimmit/httpdocs$ php test.php
PHP Notice: Undefined variable: result in /home/flimmit/httpdocs/test.php on line 6
PHP Notice: Undefined offset: 1 in /home/flimmit/httpdocs/test.php on line 6
PHP Notice: Undefined offset: 0 in /home/flimmit/httpdocs/test.php on line 6
array(2) {
[1]=>
int(31612)
[0]=>
int(68388)
}
array(2) {
[1]=>
int(63318)
[0]=>
int(136682)
}
array(2) {
[1]=>
int(94954)
[0]=>
int(205046)
}
^C
joe@joe-laptop:/home/flimmit/httpdocs$
正如您在第一个条目中看到的，结果的第一个条目总是更高，在第二个条目中则相反。相同的脚本。
奇怪的是，我只能在多次运行该脚本时重现此行为。
我写了这个小脚本来重现"交换"并生成足够的测量数据：
for($j = 0; $j<100;$j++) {
for($i=0;$i<rand(1000,10000);$i++) {
$md5 = md5(uniqid($i).microtime().rand(1,99999999));
$result[$md5%2]++;
}
#var_dump($result);
echo "ratio: ".$result[0]/$result[1]." ".(($result[0]<$result[1]) ? "A":"B")."
";
sleep(rand(2,5));
}
但在这里它只打印b，而不是A。这让我认为脚本中可能存在语义错误，但我没有找到任何错误。
我真的被卡住了，这让我很困扰。
所以我的问题：
你能推荐一些文献/网页链接吗？如果我能更深入地了解MD5，包括发行版等
你能解释/复制这种行为吗？我是不是说错了？(事实上这很有可能，但我找不到)
您能推荐其他适合我用例的算法吗？它不需要是加密的或强的，但需要快速、确定且均匀分布。
推荐答案
md5()函数返回字符串，而不是整数。
这意味着此字符串将被类型转换为整数以进行模运算；由于此字符串将包含0-9A-F范围内的字符，并转换为整数，因此您具有：
- 16分中有1分得0分
- 在1到9之间的16次机会中有9次
- 在A和F之间的16次机会中有6次--将被设置为0
例如：
$a = md5('plop1');
var_dump($a, (int)$a);
$a = md5('plop2');
var_dump($a, (int)$a);
$a = md5('plop5');
var_dump($a, (int)$a);
将得到以下输出：
string 'ac4bf0e466417336599b72a8b2f595da' (length=32)
int 0
string 'ed91c463402dd797d0718350f5bd0acd' (length=32)
int 0
string '85782b3afb04072c1bf172a6a7e6bb5e' (length=32)
int 85782
我让您猜测这可能会对模运算符的结果产生什么影响；-)
这篇关于你能解释一下MD5和模数这些令人不安的反常现象吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
