你能解释一下扰乱md5和modulo的异常情况吗？

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范围内的字符,已转换为整数,您具有:

• 得到0的16个中有1个机会
• 在16到1之间获得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

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