Fonction de hachage très rapide pour hachage de chaînes de 8 à 16 octets

Question

J'ai besoin d'une fonction de hachage de chaînes très rapide, qui s'intègre bien avec l'application web écrite en PHP.

Le problème que j'essaie de surmonter consiste à attribuer des ID aux autorisations dans un système de contrôle d'accès. Je pense à utiliser des chaînes hachées pour représenter les ID des autorisations. De cette façon, je serai en mesure de vérifier les autorisations comme comme ceci:

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

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

Le tableau DB tracera la permission hash aux rôles de l'utilisateur. Pour vérifier que l'utilisateur est autorisé à faire "profile.avatar.change", la chaîne correspondante sera hachée et vérifiée par rapport à la table DB. Ceci est très pratique et il n'y aura pas besoin de s'inquiéter de la maintenance des ID d'autorisations uniques entre différents modules. Mais la fonction de hachage devrait être très efficace.

Answer 1

Le premier était Pourquoi n'utilise-t-il pas une simple fonction md5?.

Essayer d'écrire hash par moi-même

L'un des most frequently referred function est une simple fonction de hachage Bernstein également reffered comme Times 33 with Addition. Il est utilisé dans php par zend to make hashes for keys of associative array. En php il pourrait être mis en œuvre comme suit:

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"); 

Le problème est que quand il est mis en œuvre de cette façon, il est plutôt lent. Les tests montrent qu'il est ~ 3 fois plus lent, que md5. Nous devons donc trouver le plus rapide internal implementation of a hash function.

Trouver le meilleur hachage interne

Il suffit de prendre tous les algos et mesurer le temps de hachage d'un million de chaînes.

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"; 
} 

Mes résultats était:

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 

Le résultat change légèrement de l'exécution à l'exécution - les 8 premiers algos sont SHUFFLING en raison de leurs vitesses proches et sa dépendance à la charge du serveur.

Ce qui devrait être choisi?

Vous pouvez prendre l'une des 8 fonctions ci-dessus: $hash = hash('crc32', $string);. En fait, une fonction largement utilisée md5 est juste 1,7 fois plus lente que les leaders.

Bonus

There are another functions like SuperFastHash, qui ne sont pas mises en œuvre dans le code php, mais ils sont 4 fois plus rapide que crc32.

Answer 2

Le temps de traitement d'une fonction de hachage peut être considéré comme négligeable dans la plupart des cas. Si vous avez besoin d'un peu de hachage (8 caractères), vous pouvez simplement utiliser la fonction crc32.

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

Vous pouvez également combiner un hachage avec uniqid pour créer un hachage aléatoire.

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

Answer 3

Utilisez xxHash. Il est également utilisé par PrestoDB. L'implémentation de PHP sur GitHub