Очень быстрая хэш-функция для хэширования 8-16-байтных строк

Мне нужна очень быстрая функция хэширования строк, которая хорошо вписывается в веб-приложение, написанное на PHP.

Проблема, которую я пытаюсь преодолеть, заключается в назначении идентификаторов разрешениям в системе управления доступом. Я думаю об использовании хешированных строк для представления идентификаторов разрешений. Таким образом, я смогу проверить разрешения так:

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

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

Таблица БД будет отображать хэширование прав на роли пользователя. Чтобы проверить, что пользователю разрешено делать "profile.avatar.change", соответствующая строка будет хеширована и проверена на таблице DB.

Это очень удобно, и вам не придется беспокоиться о сохранении уникальных идентификаторов доступа среди разных модулей. Но функция хэширования должна быть очень эффективной.

Ответ 1

Первое, хотя было почему не использовать простую функцию md5?.

Попытка написать хэш самостоятельно

Одна из наиболее часто упоминаемая функция - это простая хэш-функция Bernstein, также обозначаемая как 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.

Поиск лучшего внутреннего хэша

Просто возьмите все algos и измерьте время, чтобы хэшировать миллион строк.

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 раза медленнее лидеров.

Bonus

Существуют и другие функции, такие как SuperFastHash, которые не реализованы в коде php, но они в 4 раза быстрее, чем crc32.

Ответ 2

Используйте xxHash. Он также используется PrestoDB. Реализация PHP на GitHub

Ответ 3

Время обработки функции хэширования в большинстве случаев можно считать пренебрежимо малым. Если вам нужен небольшой хеш (8 символов), вы можете просто использовать функцию crc32.

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

Вы также можете комбинировать хэш с uniqid для создания случайного хэша.

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