一些经典字符串哈希函数算法的 PHP 实现

恩…或许还有朋友不清楚字符串的哈希函数到底有什么用,这个用处呢,就是将字符串转换成数字,同时让所得数字尽量平均的分布在容器中,换句话说就是让字符串得到相同数字这种情况尽可能少的出现。当然咯…容器太小,内容太多那么再好的算法也没法避免出现冲突 = =b

从网上找到的哈希函数基本上都是C算法的…最后只好从C and Java 算法中整理 and 测试了这些 PHP中的实现方法。有几个经典的算法在 PHP 下会有问题,字符串一长就会全部取 0,那些我就没有再列出来了。代码就看下面咯:

function DJBHash($str) // 0.22
{
    $hash = 0;
    $n = strlen($str);
    for ($i = 0; $i < $n; $i++) {
        $hash += ($hash << 5 ) + ord($str[$i]);
    }
    return $hash % 701819;
}

function ELFHash($str) // 0.35
{
    $hash = $x = 0;
    $n = strlen($str);

    for ($i = 0; $i < $n; $i++) {
        $hash = ($hash << 4) + ord($str[$i]);
        if(($x = $hash & 0xf0000000) != 0) {
            $hash ^= ($x >> 24);
            $hash &= ~$x;
        }
    }
    return $hash % 701819;
}

function JSHash($str) // 0.23
{
    $hash = 0;
    $n = strlen($str);

    for ($i = 0; $i < $n; $i++) {
        $hash ^= (($hash << 5) + ord($str[$i]) + ($hash >> 2));
    }
    return $hash % 701819;
}

function SDBMHash($str) // 0.23
{
    $hash = 0 ;
    $n = strlen($str);

    for ($i = 0; $i < $n; $i++) {
        $hash = ord($str[$i]) + ($hash << 6 ) + ($hash << 16 ) - $hash;
    }
    return $hash % 701819;
}

function APHash($str) // 0.30
{
    $hash = 0 ;
    $n = strlen($str);

    for ($i = 0; $i < $n; $i++) {
        if (($i & 1 ) == 0 ) {
            $hash ^= (($hash << 7 ) ^ ord($str[$i]) ^ ($hash >> 3 ));
        } else {
            $hash ^= ( ~ (($hash << 11 ) ^ ord($str[$i]) ^ ($hash >> 5)));
        }
    }
    return $hash % 701819;
}

function DEKHash($str) // 0.23
{
    $n = strlen($str);
    $hash = $n;

    for ($i = 0; $i < $n; $i++) {
        $hash = (($hash << 5) ^ ($hash >> 27)) ^ ord($str[$i]);
    }

    return $hash % 701819;
}

function FNVHash($str) // 0.31
{
    $hash = 0;
    $n = strlen($str);

    for ($i = 0; $i < $n; $i++) {
        $hash *= 0x811C9DC5;
        $hash ^= ord($str[$i]);
    }

    return $hash % 701819;
}

function PJWHash($str) // 0.33
{
    $hash = $test = 0;
    $n = strlen($str);

    for ($i = 0; $i < $n; $i++) {
        $hash = ($hash << 4) + ord($str[$i]);

        if(($test = $hash & -268435456) != 0) {
            $hash = (( $hash ^ ($test >> 24)) & (~-268435456));
        }
    }

    return $hash % 701819;
}

function PHPHash($str) // 0.34
{
    $hash = 0;
    $n = strlen($str);

    for ($i = 0; $i < $n; $i++) {
        $hash = ($hash << 4) + ord($str[$i]);
        if (($g = ($hash & 0xF0000000))) {
            $hash = $hash ^ ($g >> 24);
            $hash = $hash ^ $g;
        }
    }
    return $hash % 701819;
}

function OpenSSLHash($str) // 0.22
{
    $hash = 0;
    $n = strlen($str);

    for ($i = 0; $i < $n; $i++) {
        $hash ^= (ord($str[$i]) << ($i & 0x0f));
    }
    return $hash % 701819;
}

function MD5Hash($str) // 0.050
{
    $hash = md5($str);
    $hash = $hash[0] | ($hash[1] << 8 ) | ($hash[2] << 16) | ($hash[3] << 24) | ($hash[4] << 32) | ($hash[5] << 40) | ($hash[6] << 48) | ($hash[7] << 56);

    return $hash % 701819;
}

 

算法的一些说明:

    1. 函数后面注释中是我本地测试的执行1000次的速度(单位:s),可以看出来MD5Hash是最快的,而且要比其他函数快很多很多…但是从这个函数的算法也可以看出来,它仅仅是依赖于md5后字符串的前7个字符,也就是说如果前7个字符相同的话那么获得的hash值是完全一样的,所以实际来说它的分布情况是不太令人信任的….如果按照32个字符来计算的话速度那就远远的慢于其他算法了…
    2. 除了MD5Hash,其他算法都会受到字符串长度的影响,越长越慢,我测试用的是10个字符的英文。
    3. 每个函数最后的 return $hash % 701819; 中 701819 表示是哈希的最大容积,也就是说这些哈希函数最后得到的数字范围是0~701819,这个数字是可以改的,一般认为使用一个大的质数结果的分布会是比较均匀的,在 701819 附近的几个建议的值是:175447, 350899, 1403641, 2807303, 5614657。

或许你又问了,这个到底可以用来做什么呢…
呵呵,我来解释一下我为什么要整理 and 测试这些哈希算法,我在写多用户 Blog,恩…之前的日志里面也有提过,多用户 Blog 一般都有一个功能,那就是使用一个英文和数字组合的用户名来作为 Blog 的地址(二级域名或者目录)。那么就有一个问题了,如何根据用户名来获取用户的 ID,多一次查询吗?有了哈希函数就不用了,使用哈希函数处理用户名,得到一个数字,再对数字做一定的处理(我是按照2位分割成层次的目录,目的是防止一个目录下有太多的文件而影响磁盘检索速度),然后就形成了一个路径,把对应的ID保存在这个路径下的文件内(我个人推荐用户名做文件名),这样就可以根据用户名来直接获得用户的ID,不需要查询,用户名做文件名,所以即使最后结果相同也是在不同的文件中,所以可以不用担心出现碰撞。

当然…如果你的系统完全是根据用户名来操作那当我前面这些都没说 = =b,悄悄的非议一句 SELECT 也是数字比字符串要快一些地。

我选择的是DJB算法,等以后上线后如果测试MD5分布还算可以接受的话再考虑换用。

从这里也可以看出来其实哈希对于分布还是很有用地,呵呵,可以用来作缓存,静态或者其他需要分布存储的东西上面,这都要看你怎么用了。

————— 2018年1月30日 —————–

PHP 7.2.1 执行 10000 次后的秒数:

‘CRC32Hash’ => 0.0013580322265625,
‘MD5Hash’ => 0.007531166076660156,
‘OpenSSLHash’ => 0.00889897346496582,
‘DJBHash’ => 0.01181793212890625,
‘DEKHash’ => 0.012508869171142578,
‘JSHash’ => 0.013315916061401367,
‘PJWHash’ => 0.013475179672241211,
‘ELFHash’ => 0.01398921012878418,
‘PHPHash’ => 0.014571905136108398,
‘SDBMHash’ => 0.014824867248535156,
‘APHash’ => 0.015690088272094727,
‘FNVHash’ => 0.017553091049194336,

MD5Hash 对非数字的字符串使用位运算会报错,做了一下修改直接转换16进制成10进制

function MD5Hash($str) {
    $hash = md5($str);
    $hash = base_convert(substr($hash, 0, 7), 16, 10);
    
    return $hash % 701819;
}

CRC32Hash 就是用了PHP自带的 crc32 来 hash 字符串,再取余

function CRC32Hash($str)
{
    return crc32($str) % 701819;
}

所以 hash 没必要自己写了,用自带的 crc32吧

5 thoughts on “一些经典字符串哈希函数算法的 PHP 实现

  1. BS一下wordpress的编辑器转码功能,明明我把ol的结束标签写在了“或许你又问了,这个到底可以用来做什么呢…”前面,它愣是给移动到了最后,无奈了….还是等着再开发一个新的吧 = =

  2. 我在delphi里已经实现了, 我用的elf和另外个(忘了名了)
    要注意的是701819太大了..我一般用512-1024
    701819..想像这个数组恐怖..
    当然冲突有解决方法的, 所以我用512存30多万一点问题都没 \(^_^)/
    注: 我是用在哈系列表(数组), php里数组可以用字串所以可以偷懒 -.-

  3. 701819 不是为了保存数组,这里就是纯粹为了保存缓存文件的时候防止一个目录下文件太多
    701819 在我的程序中分解成目录最大就是70/18/19,也就是最多3层,每层100个子目录,是比较合适的一个数字

  4. 不一定是多用户Blog,很多地方都可以使用地
    在多用户Blog中应用是考虑到这么一个问题,多用户Blog一般都会提供二级域名(http://flyinghail.blog.com)又或者用户名目录这类功能(http://blog.com/flyinghail),而大部分程序在写的时候是以ID作为唯一标示,所以从用户名到ID需要一个SQL来读取,为了追求效能最大化,使用哈希函数将用户名转换成一个数字,生成一定结构的缓存,在里面放置用户ID,这样就可以给出用户名不需要读取数据库就能获得用户的ID,这样~

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.