用于散列8-16字节字符串的非常快速的散列函数

Question

我需要一个非常快速的字符串散列函数,它非常适合用PHP编写的Web应用程序.

我想要克服的问题是为访问控制系统中的权限分配ID.我正在考虑使用散列字符串来表示权限ID.这样我就可以像这样检查权限:

if ($Auth->isAllowed($user, "blog.comment")) {
    // Do some operation
}
...

if ($Auth->isAllowed($user, "profile.avatar.change")) {
    // Do some other operation
}

DB表将权限哈希映射到用户的角色.要检查是否允许用户执行"profile.avatar.change",将对数据库表进行哈希处理并检查相应的字符串.

这非常方便,无需担心在不同模块之间维护唯一的权限ID.但散列函数应该非常有效.

Answer 1

第一个虽然是他为什么不使用简单的md5功能？.

试着自己写哈希

其中的最常被提及的功能是一个简单的哈希伯恩斯坦的功能也下文称作为Times 33 with Addition.它php由zend 用于为关联数组的键生成哈希值.在php它可以实现如下:

function djb2($s){
    $word = str_split($s);
    $length = count($word);

    $hashAddress = 5381;
    for ($counter = 0; $counter < $length; $counter++){
        $hashAddress = (($hashAddress << 5) + $hashAddress) + $word[$counter];
    }
    return $hashAddress;
}
echo djb2("stackoverflow");

问题是当它以这种方式实现时,它相当慢.测试表明它比它慢约3倍md5.所以我们必须找到功能最快的内部实现hash.

找到最好的内部哈希

只需占用所有算法并测量时间就可以散列数百万个字符串.

function testing($algo, $str) {
    $start = microtime(true);
    for($ax = 0; $ax < 1000000; $ax++){
        hash($algo, $str);
    }

    $end = microtime(true);
    return ($end - $start);
}


$algos = hash_algos();
$times = [];

foreach($algos as $algo){
    $times[$algo] = testing($algo, "stackoverflow");
}

// sort by time ASC
asort($times);

foreach($times as $algo => $time){
    echo "$algo -> " . round($time, 2)."sec\n";
}

我的结果是:

fnv1a32 -> 0.29sec
fnv132 -> 0.3sec
crc32b -> 0.3sec
adler32 -> 0.3sec
crc32 -> 0.31sec
joaat -> 0.31sec
fnv1a64 -> 0.31sec
fnv164 -> 0.31sec
md4 -> 0.46sec
md5 -> 0.54sec
...
md2 -> 6.32sec

结果从执行到执行稍有变化 - 前8个算法由于它们的速度接近以及它对服务器负载的依赖而进行了混乱.

应该选择什么？

你可以采取以上任何前8个功能:$hash = hash('crc32', $string);.实际上,广泛使用的md5功能只比领导者慢1.7倍.

奖金

还有其他一些功能,比如SuperFastHash,它们没有在php代码中实现,但它们比它快4倍crc32.