你能解释一下MD5和模数这些令人不安的反常现象吗？

Can you explain theese disturbing anomalies of md5 and modulo?(你能解释一下MD5和模数这些令人不安的反常现象吗？)

问题描述

好的，这个标题真的很主观。但这就是我的问题所在。 背景是，我希望将静态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和模数这些令人不安的反常现象吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！