PHP: 分布均匀的hash函数

php中文网

发布时间：2016-06-06 20:08:52

1987人浏览过

来源于php中文网

原创

前几天google了一些php的hash函数, 想找到一种分布较为均匀的hash算法, 这样对于比如数据库分表或者其他一些需要hash的场景比较有帮助. 然后就发现了这个another happy memcached user. 很多hash函数采用times 33, 下边是php的实现: function hash_func1($ke

前几天google了一些php的hash函数, 想找到一种分布较为均匀的hash算法, 这样对于比如数据库分表或者其他一些需要hash的场景比较有帮助. 然后就发现了这个another happy memcached user.

很多hash函数采用times 33, 下边是php的实现:

function hash_func1($key, $n)
{
    $hash = 0;
    for ($i = 0; $i < strlen($key); $i++) {
        $hash = $hash * 33 + ord($key[$i]);
    }

    return $hash % $n;
}

而上边链接的邮件中提到了一种分布更均匀的算法, 如下:

宽维企业网站管理系统4.0

宽维企业网站管理系统功能说明宽维系列网站管理系统全面免费，个人和商业应用均免费。宽维企业网站管理系统是基于Php＋MySql技术开发的企业电子商务平台，全后台操作，无需学习网页制作等知识。前台智能生成页面，可以方便地在线管理、维护、更新您的企业网站。宽维企业网站管理系统安装简单快捷，5分钟就可以安装完成。1 栏目管理方便灵活：可以发布和管理您需要的任何内容的个性栏目。内置数十个功能发布模型，并可以

下载

function hash_func(&$keyword, $n)
{
    $hash = crc32($keyword) >> 16 & 0x7fff;
    return $hash % $n;
}

为了自己验证下, 我整理了一套cet-4词汇表来做测试. 测试结果如下, 使用time 33

bash$ time php h.php
bucket(0): 11.33%
bucket(1): 9.61%
bucket(2): 10.23%
bucket(3): 9.77%
bucket(4): 9.85%
bucket(5): 9.81%
bucket(6): 10.21%
bucket(7): 9.50%
bucket(8): 9.70%
bucket(9): 9.99%

real    0m0.026s
user    0m0.006s
sys 0m0.003s

使用crc32移位的这个,

bash$ time php h.php
bucket(0): 10.16%
bucket(1): 10.52%
bucket(2): 9.72%
bucket(3): 9.79%
bucket(4): 9.54%
bucket(5): 10.34%
bucket(6): 9.21%
bucket(7): 10.45%
bucket(8): 10.12%
bucket(9): 10.14%

real    0m0.015s
user    0m0.003s
sys 0m0.002s

从测试结果来看, 使用crc32移位的hash方法要比times 33分布更为均匀一些, 并且效率也要高一些. 测试的php代码和cet4词汇表: 点击这里下载. 感兴趣的可以自己测试一下.

原文地址：PHP: 分布均匀的hash函数, 感谢原作者分享。