it-swarm-eu.dev

Quel algorithme de hachage est le meilleur pour l'unicité et la vitesse?

Quel algorithme de hachage est le meilleur pour l'unicité et la vitesse? Les exemples (bons) usages incluent les dictionnaires de hachage.

Je sais qu'il y a des choses comme SHA-256 et autres, mais ces algorithmes sont conçus pour être sécurisé , ce qui signifie généralement qu'ils sont plus lents que les algorithmes qui sont moins unique. Je veux un algorithme de hachage conçu pour être rapide, tout en restant assez unique pour éviter les collisions.

1444
Earlz

J'ai testé différents algorithmes, mesurant la vitesse et le nombre de collisions.

J'ai utilisé trois jeux de clés différents:

Pour chaque corpus, le nombre de collisions et le temps moyen de hachage ont été enregistrés.

J'ai testé:

Résultats

Chaque résultat contient le temps de hachage moyen et le nombre de collisions

Hash           Lowercase      Random UUID  Numbers
=============  =============  ===========  ==============
Murmur            145 ns      259 ns          92 ns
                    6 collis    5 collis       0 collis
FNV-1a            152 ns      504 ns          86 ns
                    4 collis    4 collis       0 collis
FNV-1             184 ns      730 ns          92 ns
                    1 collis    5 collis       0 collis▪
DBJ2a             158 ns      443 ns          91 ns
                    5 collis    6 collis       0 collis▪▪▪
DJB2              156 ns      437 ns          93 ns
                    7 collis    6 collis       0 collis▪▪▪
SDBM              148 ns      484 ns          90 ns
                    4 collis    6 collis       0 collis**
SuperFastHash     164 ns      344 ns         118 ns
                   85 collis    4 collis   18742 collis
CRC32             250 ns      946 ns         130 ns
                    2 collis    0 collis       0 collis
LoseLose          338 ns        -             -
               215178 collis

Remarques :

Les collisions se produisent-elles réellement?

Oui. J'ai commencé à écrire mon programme de test pour voir si des collisions de hachage en fait se produisent - et ne sont pas seulement une construction théorique. Ils se produisent en effet:

Collisions FNV-1

  • creamwove entre en collision avec quists

Collisions FNV-1a

  • costarring entre en collision avec liquid
  • declinate entre en collision avec macallums
  • altarage entre en collision avec zinke
  • altarages entre en collision avec zinkes

Collisions Murmur2

  • cataract entre en collision avec periti
  • roquette entre en collision avec skivie
  • shawl entre en collision avec stormbound
  • dowlases entre en collision avec tramontane
  • cricketings entre en collision avec twanger
  • longans entre en collision avec whigs

Collisions DJB2

  • hetairas entre en collision avec mentioner
  • heliotropes entre en collision avec neurospora
  • depravement entre en collision avec serafins
  • stylist entre en collision avec subgenera
  • joyful entre en collision avec synaphea
  • redescribed entre en collision avec urites
  • dram entre en collision avec vivency

Collisions DJB2a

  • haggadot entre en collision avec loathsomenesses
  • adorablenesses entre en collision avec rentability
  • playwright entre en collision avec snush
  • playwrighting entre en collision avec snushing
  • treponematoses entre en collision avec waterbeds

Collisions CRC32

  • codding entre en collision avec gnu
  • exhibiters entre en collision avec schlager

Collisions SuperFastHash

  • dahabiah entre en collision avec drapability
  • encharm entre en collision avec enclave
  • grahams entre en collision avec gramary
  • ... snip 79 collisions ...
  • night entre en collision avec vigil
  • nights entre en collision avec vigils
  • finks entre en collision avec vinic

Randomnessification

L'autre mesure subjective est la distribution aléatoire des hachages. Le mappage des tables de hachage résultantes montre la répartition uniforme des données. Toutes les fonctions de hachage présentent une bonne distribution lors du mappage linéaire de la table:

Enter image description here

Ou comme Hilbert Map ( XKCD est toujours pertinent ):

Enter image description here

Sauf lors du hachage de chaînes de nombres ("1", "2", ..., "216553") (par exemple, Codes postaux ), où des modèles commencent à émerger dans la plupart des algorithmes de hachage:

[~ # ~] sdbm [~ # ~] :

Enter image description here

DJB2a :

Enter image description here

FNV-1 :

Enter image description here

Tout sauf FNV-1a , qui me semble encore assez aléatoire:

Enter image description here

En fait, Murmur2 semble avoir un caractère aléatoire encore meilleur avec Numbers que FNV-1a:

Enter image description here

Quand je regarde le FNV-1a carte "numérique", je pense que je vois des motifs verticaux subtils. Avec Murmur, je ne vois aucun motif. Que pensez-vous?


Le supplément * dans le tableau indique la gravité du caractère aléatoire. Avec FNV-1a étant le meilleur, et DJB2x étant le pire:

      Murmur2: .
       FNV-1a: .
        FNV-1: ▪
         DJB2: ▪▪
        DJB2a: ▪▪
         SDBM: ▪▪▪
SuperFastHash: .
          CRC: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
     Loselose: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
                                        ▪
                                 ▪▪▪▪▪▪▪▪▪▪▪▪▪
                        ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
          ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪

J'ai écrit à l'origine ce programme pour décider si je devais même s'inquiéter à propos des collisions: oui.

Et puis cela s'est transformé en s'assurant que les fonctions de hachage étaient suffisamment aléatoires.

Algorithme FNV-1a

Le hachage FNV1 est disponible en variantes qui renvoient des hachages 32, 64, 128, 256, 512 et 1024 bits.

algorithme FNV-1a est:

hash = FNV_offset_basis
for each octetOfData to be hashed
    hash = hash xor octetOfData
    hash = hash * FNV_prime
return hash

Où les constantes FNV_offset_basis et FNV_prime dépend de la taille de hachage de retour souhaitée:

Hash Size  
===========
32-bit
    prime: 2^24 + 2^8 + 0x93 = 16777619
    offset: 2166136261
64-bit
    prime: 2^40 + 2^8 + 0xb3 = 1099511628211
    offset: 14695981039346656037
128-bit
    prime: 2^88 + 2^8 + 0x3b = 309485009821345068724781371
    offset: 144066263297769815596495629667062367629
256-bit
    prime: 2^168 + 2^8 + 0x63 = 374144419156711147060143317175368453031918731002211
    offset: 100029257958052580907070968620625704837092796014241193945225284501741471925557
512-bit
    prime: 2^344 + 2^8 + 0x57 = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759
    offset: 9659303129496669498009435400716310466090418745672637896108374329434462657994582932197716438449813051892206539805784495328239340083876191928701583869517785
1024-bit
    prime: 2^680 + 2^8 + 0x8d = 5016456510113118655434598811035278955030765345404790744303017523831112055108147451509157692220295382716162651878526895249385292291816524375083746691371804094271873160484737966720260389217684476157468082573
    offset: 1419779506494762106872207064140321832088062279544193396087847491461758272325229673230371772250864096521202355549365628174669108571814760471015076148029755969804077320157692458563003215304957150157403644460363550505412711285966361610267868082893823963790439336411086884584107735010676915

Voir la page principale de FNV pour plus de détails.

Tous mes résultats sont avec la variante 32 bits.

FNV-1 mieux que FNV-1a?

Non. FNV-1a est mieux partout. Il y a eu plus de collisions avec FNV-1a lors de l'utilisation du corpus Word anglais:

Hash    Word Collisions
======  ===============
FNV-1   1
FNV-1a  4

Comparez maintenant les minuscules et les majuscules:

Hash    lowercase Word Collisions  UPPERCASE Word collisions
======  =========================  =========================
FNV-1   1                          9
FNV-1a  4                          11

Dans ce cas, FNV-1a n'est pas "400%" pire que FN-1, seulement 20% pire.

Je pense que le point le plus important à retenir est qu'il existe deux classes d'algorithmes en matière de collisions:

  • collisions rares : FNV-1, FNV-1a, DJB2, DJB2a, SDBM
  • collisions courantes : SuperFastHash, Loselose

Et puis il y a la répartition uniforme des hachages:

  • distribution exceptionnelle: Murmur2, FNV-1a, SuperFastHas
  • excellente distribution: FNV-1
  • bonne distribution: SDBM, DJB2, DJB2a
  • distribution horrible: Loselose

Mise à jour

Murmure? Bien sûr, pourquoi pas


Mise à jour

@whatshisname s'est demandé comment fonctionnerait un CRC32 , a ajouté des chiffres au tableau.

CRC32 est plutôt bien. Peu de collisions, mais plus lent, et les frais généraux d'une table de recherche 1k.

Coupez toutes les choses erronées sur la distribution CRC - ma mauvaise


Jusqu'à aujourd'hui, j'allais utiliser FNV-1a comme mon de facto algorithme de hachage de table de hachage. Mais maintenant je passe à Murmur2:

  • Plus rapide
  • Mieux randomisation de toutes les classes d'entrée

Et j'ai vraiment, vraiment j'espère qu'il y a quelque chose qui ne va pas avec l'algorithme SuperFastHash que j'ai trouvé ; c'est dommage d'être aussi populaire que ça.

Mise à jour: De la page d'accueil de MurmurHash3 sur Google :

(1) - SuperFastHash a de très faibles propriétés de collision, qui ont été documentées ailleurs.

Donc je suppose que ce n'est pas seulement moi.

Mise à jour: J'ai compris pourquoi Murmur est plus rapide que les autres. MurmurHash2 fonctionne sur quatre octets à la fois. La plupart des algorithmes sont octet par octet:

for each octet in Key
   AddTheOctetToTheHash

Cela signifie qu'à mesure que les clés s'allongent, Murmur a sa chance de briller.


Mise à jour

les GUID sont conçus pour être uniques et non aléatoires

Un article opportun de Raymond Chen réitère le fait que "aléatoire" Les GUID ne sont pas destinés à être utilisés pour leur caractère aléatoire. Ils, ou un sous-ensemble d'entre eux, ne conviennent pas comme clé de hachage:

Même l'algorithme de la version 4 GUID n'est pas garanti d'être imprévisible, car l'algorithme ne spécifie pas la qualité du générateur de nombres aléatoires. L'article Wikipedia pour GUID contient des recherches primaires qui suggèrent que les GUID futurs et précédents peuvent être prédits sur la base de la connaissance de l'état du générateur de nombres aléatoires, car le générateur n'est pas cryptographiquement fort.

L'aléatoire n'est pas la même chose que l'évitement de collision; c'est pourquoi ce serait une erreur d'essayer d'inventer votre propre algorithme de "hachage" en prenant un sous-ensemble d'un guid "aléatoire":

int HashKeyFromGuid(Guid type4uuid)
{
   //A "4" is put somewhere in the GUID.
   //I can't remember exactly where, but it doesn't matter for
   //the illustrative purposes of this pseudocode
   int guidVersion = ((type4uuid.D3 & 0x0f00) >> 8);
   Assert(guidVersion == 4);

   return (int)GetFirstFourBytesOfGuid(type4uuid);
}

Remarque : Encore une fois, je mets "GUID aléatoire" entre guillemets, car c'est la variante "aléatoire" des GUID. Une description plus précise serait Type 4 UUID. Mais personne ne sait ce que sont les types 4 ou 1, 3 et 5. Il est donc plus facile de les appeler des GUID "aléatoires".

Tous les mots anglais miroirs

2530
Ian Boyd

Si vous souhaitez créer une carte de hachage à partir d'un dictionnaire immuable, vous pouvez envisager un hachage parfait https://en.wikipedia.org/wiki/Perfect_hash_function - lors de la construction de la fonction de hachage et table de hachage, vous pouvez garantir, pour un ensemble de données donné, qu'il n'y aura pas de collisions.

61
Damien

Ici est une liste de fonctions de hachage, mais la version courte est:

Si vous voulez juste avoir une bonne fonction de hachage et ne pouvez pas attendre, djb2 est l'une des meilleures fonctions de hachage de chaînes que je connaisse. Il a une excellente distribution et vitesse sur de nombreux jeux de clés et tailles de table différents

unsigned long
hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}
34
Dean Harding

CityHash by Google est l'algorithme que vous recherchez. Ce n'est pas bon pour la cryptographie mais c'est bon pour générer des hachages uniques.

Lisez le blog pour plus de détails et le le code est disponible ici .

CityHash est écrit en C++. Il y a aussi un port C simple .

À propos de la prise en charge 32 bits:

Toutes les fonctions CityHash sont réglées pour les processeurs 64 bits. Cela dit, ils s'exécuteront (à l'exception des nouveaux qui utilisent SSE4.2) en code 32 bits. Ils ne seront cependant pas très rapides. Vous pouvez utiliser Murmur ou autre chose en code 32 bits.

29
Vipin Parakkat

J'ai tracé une courte comparaison de vitesse des différents algorithmes de hachage lors du hachage de fichiers.

Les tracés individuels ne diffèrent que légèrement dans la méthode de lecture et peuvent être ignorés ici, car tous les fichiers ont été stockés dans un tmpfs. Par conséquent, la référence n'était pas liée aux entrées-sorties si vous vous posez la question.

Les algorithmes incluent: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Conclusions:

  • Les fonctions de hachage non cryptographiques comme Murmur3, Cityhash et Spooky sont assez proches les unes des autres. Il convient de noter que Cityhash peut être plus rapide sur les CPU avec l'instruction SSE 4.2s CRC, que mon CPU n'a pas. SpookyHash était dans mon cas toujours un tout petit peu avant CityHash.
  • MD5 semble être un bon compromis lors de l'utilisation de fonctions de hachage cryptographiques, bien que SHA256 puisse être plus sécurisé contre les vulnérabilités de collision de MD5 et SHA1.
  • La complexité de tous les algorithmes est linéaire - ce qui n'est vraiment pas surprenant car ils fonctionnent par blocs. (Je voulais voir si la méthode de lecture fait une différence, vous pouvez donc comparer les valeurs les plus à droite).
  • SHA256 était plus lent que SHA512.
  • Je n'ai pas étudié le caractère aléatoire des fonctions de hachage. Mais ici est une bonne comparaison des fonctions de hachage qui manquent dans réponse Ian Boyds . Cela souligne que CityHash a quelques problèmes dans les cas d'angle.

La source utilisée pour les parcelles:

21
Sahib

Les algorithmes SHA (y compris SHA-256) sont conçus pour être rapides.

En fait, leur vitesse peut parfois être un problème. En particulier, une technique courante pour stocker un jeton dérivé d'un mot de passe consiste à exécuter un algorithme de hachage rapide standard 10 000 fois (stockage du hachage du hachage du hachage du hachage du ... mot de passe).

#!/usr/bin/env Ruby
require 'securerandom'
require 'digest'
require 'benchmark'

def run_random_digest(digest, count)
  v = SecureRandom.random_bytes(digest.block_length)
  count.times { v = digest.digest(v) }
  v
end

Benchmark.bmbm do |x|
  x.report { run_random_digest(Digest::SHA256.new, 1_000_000) }
end

Production:

Rehearsal ------------------------------------
   1.480000   0.000000   1.480000 (  1.391229)
--------------------------- total: 1.480000sec

       user     system      total        real
   1.400000   0.000000   1.400000 (  1.382016)
18
yfeldblum

Je sais qu'il y a des choses comme SHA-256 et autres, mais ces algorithmes sont conçus pour être sécurisés , ce qui signifie généralement qu'ils sont plus lents que les algorithmes qui sont moins unique.

L'hypothèse selon laquelle les fonctions de hachage cryptographiques sont plus uniques est erronée et, en fait, il peut être démontré qu'elle est souvent en arrière dans la pratique. En vérité:

  1. Les fonctions de hachage cryptographique devraient idéalement être indiscernables de aléatoires ;
  2. Mais avec les fonctions de hachage non cryptographiques, il est souhaitable qu'elles interagissent favorablement avec les entrées probables .

Ce qui signifie qu'une fonction de hachage non cryptographique peut très bien avoir moins de collisions qu'une fonction cryptographique pour un "bon" ensemble de données - des ensembles de données pour lesquels elle a été conçue .

Nous pouvons en fait le démontrer avec les données de la réponse d'Ian Boyd et un peu de calcul: le problème d'anniversaire . La formule du nombre attendu de paires en collision si vous choisissez n entiers au hasard dans l'ensemble [1, d] est-ce (tiré de Wikipedia):

n - d + d * ((d - 1) / d)^n

En branchant n = 216 553 et d = 2 ^ 32 nous obtenons environ 5,5 collisions attendues . Les tests de Ian montrent principalement des résultats dans ce quartier, mais avec une exception dramatique: la plupart des fonctions ont obtenu zéro collision dans les tests de nombres consécutifs. La probabilité de choisir au hasard 216 553 nombres 32 bits et d'obtenir zéro collision est d'environ 0,43%. Et c'est juste pour une fonction - nous avons ici cinq familles de fonctions de hachage distinctes avec zéro collision!

Donc, ce que nous voyons ici, c'est que les hachages que Ian a testés interagissent favorablement avec l'ensemble de données de nombres consécutifs, c'est-à-dire qu'ils dispersent des entrées minimalement différentes plus largement qu'une fonction de hachage cryptographique idéale. (Note latérale: cela signifie que l'évaluation graphique d'Ian selon laquelle FNV-1a et MurmurHash2 lui "semblent aléatoires" dans l'ensemble de données numériques peut être réfutée à partir de ses propres données. Zéro collision sur un ensemble de données de cette taille, pour les deux les fonctions de hachage, est étonnamment non aléatoire!)

Ce n'est pas une surprise car il s'agit d'un comportement souhaitable pour de nombreuses utilisations des fonctions de hachage. Par exemple, les clés de table de hachage sont souvent très similaires; La réponse d'Ian mentionne n problème que MSN a eu une fois avec les tables de hachage de code postal . Il s'agit d'une utilisation où l'évitement de collision sur les entrées probablement l'emporte sur le comportement aléatoire.

Une autre comparaison instructive ici est le contraste des objectifs de conception entre le CRC et les fonctions de hachage cryptographiques:

  • Le CRC est conçu pour détecter les erreurs résultant de canaux de communication bruyants , qui sont susceptibles d'être un petit nombre de retournements de bits;
  • Les hachages cryptographiques sont conçus pour intercepter les modifications apportées par des attaquants malveillants , qui se voient allouer des ressources de calcul limitées mais arbitrairement beaucoup d'intelligence.

Donc, pour CRC, c'est encore bien d'avoir moins de collisions que aléatoire dans des entrées minimalement différentes. Avec les hachages cryptographiques, c'est un non-non!

15
sacundim

Utilisez SipHash . Il a de nombreuses propriétés souhaitables:

  • Rapide. Une implémentation optimisée prend environ 1 cycle par octet.

  • Sécurisé. SipHash est un PRF fort (fonction pseudo-aléatoire). Cela signifie qu'il est impossible de la distinguer d'une fonction aléatoire (sauf si vous connaissez la clé secrète 128 bits). Par conséquent:

    • Pas besoin de s'inquiéter du fait que vos sondes de table de hachage deviennent linéaires en raison de collisions. Avec SipHash, vous savez que vous obtiendrez en moyenne des performances de cas moyen, quelles que soient les entrées.

    • Immunité aux attaques par déni de service basées sur le hachage.

    • Vous pouvez utiliser SipHash (en particulier la version avec une sortie 128 bits) comme MAC (Message Authentication Code). Si vous recevez un message et une balise SipHash, et que la balise est la même que celle de l'exécution de SipHash avec votre clé secrète, alors vous savez que celui qui a créé le hachage était également en possession de votre clé secrète, et que ni le message ni le le hachage a été modifié depuis.

10
Demi

Cela dépend des données que vous hachez. Certains hachages fonctionnent mieux avec des données spécifiques comme le texte. Certains algorithmes de hachage ont été spécifiquement conçus pour être adaptés à des données spécifiques.

Paul Hsieh une fois fait hachage rapide . Il répertorie le code source et les explications. Mais c'était déjà battu. :)

9
user712092

Java utilise ce algorithme simple de multiplication et d'ajout:

Le code de hachage pour un objet String est calculé comme

 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

en utilisant l'arithmétique int, où s[i] est le i -ème caractère de la chaîne, n est la longueur de la chaîne et ^ indique l'exponentiation. (La valeur de hachage de la chaîne vide est zéro.)

Il y en a probablement beaucoup mieux, mais c'est assez répandu et semble être un bon compromis entre la vitesse et l'unicité.

6
biziclop

Tout d'abord, pourquoi avez-vous besoin d'implémenter votre propre hachage? Pour la plupart des tâches, vous devriez obtenir de bons résultats avec les structures de données d'une bibliothèque standard, en supposant qu'une implémentation est disponible (à moins que vous ne le fassiez que pour votre propre éducation).

En ce qui concerne les algorithmes de hachage réels, mon préféré est FNV. 1

Voici un exemple d'implémentation de la version 32 bits en C:

unsigned long int FNV_hash(void* dataToHash, unsigned long int length)
{
  unsigned char* p = (unsigned char *) dataToHash;
  unsigned long int h = 2166136261UL;
  unsigned long int i;

  for(i = 0; i < length; i++)
    h = (h * 16777619) ^ p[i] ;

  return h;
}
4
user17754