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

Question

Мне нужна очень быстрая функция хэширования строк, которая хорошо вписывается в веб-приложение, написанное на 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.

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

Answer 1

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

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

Один из most frequently referred function простой хэш-функция Бернштейна также обозначаемого как Times 33 with Addition. Он используется в php по zend to make hashes for keys of associative array. В 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. Поэтому нам нужно найти самый быстрый internal implementation of a hash function.

найти лучший внутренний хэш

Просто возьмите все 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 Algos являются перетасовки из-за их близких скоростях и ее зависимости от нагрузки на сервер.

Что следует выбрать?

Вы можете использовать любую из вышеперечисленных функций: $hash = hash('crc32', $string);. Фактически широко используемая функция md5 в 1,7 раза медленнее лидеров.

Bonus

There are another functions like SuperFastHash, которые не реализованы в php коде, но они 4 раза быстрее, чем crc32.

Answer 2

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

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

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

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

Answer 3

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