A message-digest algorithm producing 64b
程序员的浪漫
Aug
21
sdbm hash for PHP 
上一篇提到了，使用sdbmhash来生成64bit摘要。这个算法，是需要用在PHP里头的，但是PHP在设计的时候有点囧，用于表示任意变量的 zval 这个struct里头，有一个union是用于存放不同数据类型的，而该union中用于表示整型的变量，就只有一个long。于是很杯具地：
1. 32bit OS下面的php只支持32bit整数
2. 不支持无符号整型
那个抑郁啊，于是只好用php的bcmath这个大整数库来实现上一篇的sdbmhash算法：
大整数库是用字符串来模拟的，没有对位移的直接支持。于是刚开始的时候用 bcmul($hash, 1<<6) 之类来替代C实现中的位移；然后果断发现自己SB了，直接乘65599更合适。
当然了，由于是用字符串来模拟的，可以想象这段代码效率是很低的。但是有多低呢？在我的Ubuntu虚拟机上测试了一下，1w次对18个字符的hash需要大约2.4s，也就是说一次调用大约需要0.2~0.3ms。宿主机是windows（AMD M320, 2.1GHz），php的效率更低，大约花了3~4s。在同样的时间里，纯C实现，可以进行相同的运算10,000,000+次，效率比大约是PHP:C = 1:1000。
由于0.2~0.3ms这个数量级比较大了，于是决定把它写成一个PHP扩展。参照百度文库的这篇教程 http://wenku.baidu.com/view/044da6f8941ea76e58fa04b1.html 比较快就上手了。
最终实现的效率比是大约1:100。看来PHP的扩展开销还是很大啊。
记得前年曾经和@Sandy讨论过ASP、PHP、JSP的效率，他认为ASP和PHP在同一个数量级，和JSP差距很大（而我当初则认为PHP和JSP差距不大）。这个数据很好地证明了这一点。
最后，附上这个PHP扩展。
下载文件 (已下载 1148 次)
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
1. 32bit OS下面的php只支持32bit整数
2. 不支持无符号整型
那个抑郁啊，于是只好用php的bcmath这个大整数库来实现上一篇的sdbmhash算法：
function sdbmhash($str)
{
$mul = "65599"; // (1 << 6) + (1 << 16) - 1
$mod = "18446744073709551616"; // 1 << 64
$hash = "0";
for ($i = 0; $i < strlen($str); ++$i)
{
$hash = bcmod(bcmul($hash, $mul), $mod);
$hash = bcmod(bcadd($hash, ord($str{$i})), $mod);
}
return $hash;
}
{
$mul = "65599"; // (1 << 6) + (1 << 16) - 1
$mod = "18446744073709551616"; // 1 << 64
$hash = "0";
for ($i = 0; $i < strlen($str); ++$i)
{
$hash = bcmod(bcmul($hash, $mul), $mod);
$hash = bcmod(bcadd($hash, ord($str{$i})), $mod);
}
return $hash;
}
大整数库是用字符串来模拟的，没有对位移的直接支持。于是刚开始的时候用 bcmul($hash, 1<<6) 之类来替代C实现中的位移；然后果断发现自己SB了，直接乘65599更合适。
当然了，由于是用字符串来模拟的，可以想象这段代码效率是很低的。但是有多低呢？在我的Ubuntu虚拟机上测试了一下，1w次对18个字符的hash需要大约2.4s，也就是说一次调用大约需要0.2~0.3ms。宿主机是windows（AMD M320, 2.1GHz），php的效率更低，大约花了3~4s。在同样的时间里，纯C实现，可以进行相同的运算10,000,000+次，效率比大约是PHP:C = 1:1000。
由于0.2~0.3ms这个数量级比较大了，于是决定把它写成一个PHP扩展。参照百度文库的这篇教程 http://wenku.baidu.com/view/044da6f8941ea76e58fa04b1.html 比较快就上手了。
最终实现的效率比是大约1:100。看来PHP的扩展开销还是很大啊。
记得前年曾经和@Sandy讨论过ASP、PHP、JSP的效率，他认为ASP和PHP在同一个数量级，和JSP差距很大（而我当初则认为PHP和JSP差距不大）。这个数据很好地证明了这一点。
最后，附上这个PHP扩展。
下载文件 (已下载 1148 次)欢迎扫码关注：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
