非常快的哈希函数，用于哈希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"操作，相应的字符串将被哈希并与DB表进行比较。

这非常方便，在不同模块之间维护唯一的权限ID将不再需要担心。但哈希函数应该非常高效。

- ezpresso

---

哈希是单向的，因此除了其存在之外，您无法在哈希中检查任何内容，例如这种情况。 - Jay Blanchard

最常见的方法是遵循Linux的方式（使用0-7表示权限）。为权限分配ID，并进行2^(id号码)以创建整数，然后以相同的方式展开它以确定您拥有哪些权限...或者只需传递带有一堆变量的对象/令牌并检查$user->can_change_stuff或$user->has_apples。 - Dimi

@JayBlanchard，这正是我想要检查的内容——在数据库表中是否存在某个特定权限。 - ezpresso

将一个8-16字节的字符串哈希为唯一字符串的最快方法是什么都不做，只需将其原样存储即可。它已经很短了。 - apokryfos

@ezpresso请检查答案，否则你的声望积分将会消失一半。 - shukshin.ivan

Answer 1

The first thought was "为什么他不使用一个简单的md5函数呢？"。

尝试自己编写哈希函数

其中一个最常用的函数是一个简单的哈希函数Bernstein's function，也称为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");

问题在于，当以这种方式实现时，速度相对较慢。测试表明，它比md5慢约3倍。因此，我们必须找到最快的内部实现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个算法由于速度接近并且依赖于服务器负载而进行洗牌。

应该选择什么？

您可以选择上面任何一个顶级函数：$hash = hash('crc32', $string);。实际上，广泛使用的md5函数只比领先者慢1.7倍。

奖励 还有其他像SuperFastHash这样的函数, 它们没有在php代码中实现，但比crc32快4倍。

- shukshin.ivan

Answer 2

使用xxHash。它也被PrestoDB所使用。在GitHub上有PHP实现。

- SACn

Answer 3

在大多数情况下，哈希函数的处理时间可以被认为是可以忽略不计的。如果您只需要一个小型哈希（8个字符），则可以简单地使用crc32函数。

<?php
$hash = hash('crc32', 'WhatDoYouWant');
?>

你可以将uniqid与哈希结合使用来创建随机哈希。

<?php
$hash = hash('crc32', uniqid());
?>

- arnolem