php - 你能解释一下这些令人不安的 md5 和模数异常吗？

Question

好吧，标题真的很主观。但这正是我的问题所在。

背景是我想在定义数量的缓存服务器上均匀分布静态 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]."\n";

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

现在奇怪的是，总和 % 2 等于 1 和总和 % 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);
}

我从命令行运行脚本两次，并在运行 3 次后中止它，它产生了这两个输出:

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")."\n";
    sleep(rand(2,5));
}

但这里它只打印 b，从不打印 A。这让我觉得脚本中可能存在语义错误，但我没有发现任何错误。

我真的卡住了，这让我很困扰。

所以我的问题:

• 如果我可以更深入地阅读有关 md5 的任何文献/网络链接，包括发行版等，您能否推荐一下

• 您能解释/重现该行为吗？我这里有错误吗？ (其实很有可能，但我找不到)

• 您能否推荐适合我的用例的任何其他算法？它不需要加密或强大，但需要快速、确定性和均匀分布。

Answer 1

md5()函数返回一个字符串，而不是一个整数。

这意味着该字符串将被类型转换为整数以进行取模；由于此字符串将包含 0-9A-F 范围内的字符，转换为整数，您有:

• 16 分中有 1 分是 0
• 在 1 到 9 之间的 16 次机会中有 9 次
• 16 次中有 6 次出现在 A 和 F 之间——将被转换为 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

我会让你猜猜这对模运算符的结果可能产生的影响;-)