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

Je sais qu'il existe des éléments tels que 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 des algorithmes moins uniques . Je veux un algorithme de hachage conçu pour être rapide, tout en restant assez unique pour éviter les collisions.

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

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

• Une liste de 216 553 mots anglais (en minuscules)
• Les nombres "1"à "216553"(pensez aux codes postaux et à la manière dont un hachage pauvre a été pris par msn.com )
• 216 553 GUID "aléatoires" (c'est-à-dire de type 4 uuid )

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

J'ai testé:

• DJB2
• DJB2a (variante utilisant xorplutôt que +)
• FNV-1 (32 bits)
• FNV-1a (32 bits)
• SDBM
• CRC32
• Murmur2 (32 bits)
• SuperFastHash

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

Notes :

• L' algorithme LoseLose (où hash = hash + character) est vraiment affreux . Tout se heurte dans les mêmes 1 375 seaux
• SuperFastHash est rapide, les choses semblent assez dispersées; par ma bonté le nombre de collisions. J'espère que le gars qui l'a porté a quelque chose de mal; c'est assez mauvais
• CRC32 est très bon . Plus lent, et une table de recherche 1k

Les collisions se produisent-elles réellement?

Oui. J'ai commencé à écrire mon programme de test pour voir si les collisions de hachage se produisaient réellement - et ne constituaient pas simplement un concept théorique. Ils se produisent effectivement:

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
• ... coupez 79 collisions ...
• night entre en collision avec vigil
• nights entre en collision avec vigils
• finks entre en collision avec vinic

Aléatoire

L’autre mesure subjective est la distribution aléatoire des hachages. Le mappage des tables de hachage obtenues montre comment les données sont distribuées. Toutes les fonctions de hachage montrent une bonne distribution lors du mappage linéaire de la table:

Ou comme une carte de Hilbert ( XKCD est toujours pertinent ):

Sauf lorsque les chaînes numériques (hashing "1", "2", ..., "216553") (par exemple, des codes postaux ), où commencent à émerger des modèles dans la plupart des algorithmes de hachage:

SDBM :

DJB2a :

FNV-1 :

Tous sauf FNV-1a , qui me semble toujours assez aléatoire:

En fait, Murmur2 semble avoir encore mieux son caractère aléatoire avec Numbersque FNV-1a:

Quand je regarde la FNV-1acarte "nombre", je pense voir des motifs verticaux subtils. Avec Murmur, je ne vois aucune tendance. Qu'est-ce que tu penses?

Le supplément *dans le tableau indique à quel point le caractère aléatoire est mauvais. Avec FNV-1aêtre le meilleur, et DJB2xétant le pire:

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

Au départ, j’avais écrit ce programme pour décider si je devais même me soucier des collisions: c’est le cas.

Et ensuite, il s’est assuré que les fonctions de hachage étaient suffisamment aléatoires.

Algorithme FNV-1a

Le hachage FNV1 est proposé dans des variantes qui renvoient des hachages de 32, 64, 128, 256, 512 et 1024 bits.

L' 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_basiset FNV_primedépendent 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 FNV pour plus de détails.

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

FNV-1 meilleur que FNV-1a?

FNV-1a est tout à fait mieux. Il y avait plus de collisions avec FNV-1a en utilisant le mot anglais corpus:

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

Maintenant, comparez 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 collision:

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

Et puis il y a la façon dont les hachages sont distribués uniformément:

• 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 se comporterait un CRC32 , ajoutait des chiffres à la table.

CRC32 est très bon . Peu de collisions, mais plus lentes, et les frais généraux d’une table de recherche 1k.

Snip tous les trucs erronés sur la distribution du CRC - mon mauvais

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

• plus rapide
• Meilleure randomisation de toutes les classes d'entrées

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

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

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

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

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

for each octet in Key
   AddTheOctetToTheHash

Cela signifie que lorsque les touches s'allongent, Murmur a la chance de briller.

Mise à jour

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

Dans un article opportun de Raymond Chen, on réitère le fait que les GUID "aléatoires" 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 GUID de la version 4 n’est pas toujours imprévisible, car il ne spécifie pas la qualité du générateur de nombres aléatoires. L'article de Wikipedia pour GUID contient des recherches principales qui suggèrent que les GUID futurs et antérieurs 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 puissant.

Le hasard n'est pas la même chose que d'éviter les collisions; 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);
}

Note : 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 le type 4 ou les types 1, 3 et 5. Il est donc plus simple de les appeler des GUID "aléatoires".

Tous les mots anglais miroirs

• https://web.archive.org/web/20070221060514/http://www.sitopreferito.it/html/all_english_words.html
• https://drive.google.com/file/d/0B3BLwu7Vb2U-dEw1VkUxc3U4SG8/view?usp=sharing

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

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

Si vous voulez juste avoir une bonne fonction de hachage, et ne pouvez pas attendre, djb2est l’une des meilleures fonctions de hachage de chaîne que je connaisse. Il offre une excellente distribution et vitesse sur de nombreux jeux de clés et de tailles de table

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

CityHash de 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 code est disponible ici .

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

À propos du support 32 bits:

Toutes les fonctions CityHash sont adaptées aux processeurs 64 bits. Cela dit, ils fonctionneront (à l'exception des nouveaux qui utilisent SSE4.2) en code 32 bits. Ils ne seront pas très rapides cependant. Vous voudrez peut-être utiliser Murmur ou autre chose en code 32 bits.

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

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

• Échelle linéaire
• Échelle logarithmique

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

Conclusions:

• Les fonctions de hachage non cryptographiques telles que Murmur3, Cityhash et Spooky sont assez proches les unes des autres. Il convient de noter que Cityhash est peut-être plus rapide sur les CPU avec l’ CRCinstruction SSE 4.2s , que mon CPU n’a pas. SpookyHash était dans mon cas toujours un 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ûr face aux 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 dans la mesure où ils fonctionnent par blocs. (Je voulais voir si la méthode de lecture faisait 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 voici une bonne comparaison des fonctions de hachage qui manquent dans la réponse de Ian Boyds . Cela indique que CityHash a quelques problèmes dans certains cas.

La source utilisée pour les parcelles:

• https://github.com/sahib/rmlint/tree/gh-pages/plots (désolé pour le code moche)

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 (stocker le 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

Sortie:

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

       user     system      total        real
   1.400000   0.000000   1.400000 (  1.382016)

Je sais qu'il existe des éléments tels que 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 des algorithmes moins uniques .

L'hypothèse selon laquelle les fonctions de hachage cryptographiques sont plus uniques est fausse et, en fait, on peut démontrer qu'elle est souvent rétrograde dans la pratique. En vérité:

1. Les fonctions de hachage cryptographique devraient idéalement ne pas être distinguées de manière aléatoire ;
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 risque d'avoir moins de collisions qu'une fonction cryptographique pour de "bons" ensembles de données - ensembles de données pour lesquels elle a été conçue.

Nous pouvons en faire la démonstration avec les données de la réponse de Ian Boyd et un peu de calcul: le problème de l' anniversaire . La formule pour le nombre attendu de paires en collision si vous choisissez des nentiers au hasard dans l'ensemble [1, d]est la suivante (tirée de Wikipedia):

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

Branchement n= 216553 et d= 2 ^ 32 nous obtenons environ 5,5 collisions attendues . Les tests de Ian montrent principalement des résultats dans ce quartier, à une exception près: la plupart des fonctions n'ont eu aucune collision lors des tests de nombres consécutifs. La probabilité de choisir au hasard 216 553 nombres de 32 bits et d'obtenir zéro collision est d'environ 0,43%. Et ce n'est que pour une fonction - nous avons ici cinq familles de fonctions de hachage distinctes avec zéro collision!

Nous constatons donc ici que les hachages testés par Ian interagissent favorablement avec l'ensemble de données de nombres consécutifs, c'est-à-dire qu'ils dispersent très peu d'entrées différentes plus largement qu'une fonction de hachage cryptographique idéale. (Note latérale: cela signifie que l'évaluation graphique de Ian selon laquelle FNV-1a et MurmurHash2 lui "semblent aléatoires" dans l'ensemble de données numériques peut être réfuté à partir de ses propres données. Zéro collisions sur un ensemble de données de cette taille, pour les deux fonctions de hachage, est remarquablement 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 de Ian mentionne un problème que MSN a déjà rencontré avec les tables de hachage par code postal . Il s'agit d'une utilisation dans laquelle la prévention des collisions sur des entrées probables l' emporte sur un comportement aléatoire.

Une autre comparaison intéressante est le contraste entre les objectifs de conception des fonctions CRC et de hachage cryptographique:

• Le CRC est conçu pour détecter les erreurs résultant de canaux de communication bruyants , qui sont généralement constitués d’un petit nombre de retournements de bits;
• Les hachages cryptographiques sont conçus pour détecter les modifications apportées par des attaquants malveillants , à qui des ressources de calcul limitées sont allouées, mais dont l'intelligence est arbitraire.

Pour le CRC, il est donc bon d’avoir moins de collisions que de hasard dans des entrées très différentes. Avec crypto hashes, c'est un non-non!

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

• Vite. Une mise en œuvre optimisée prend environ 1 cycle par octet.

• Sécurise. SipHash est une PRF forte (fonction pseudo-aléatoire). Cela signifie qu'il est impossible de distinguer une fonction aléatoire (à moins que vous ne connaissiez la clé secrète de 128 bits). Par conséquent:

  • Inutile de vous inquiéter de ce que vos sondes de table de hachage deviennent des heures linéaires en raison de collisions. Avec SipHash, vous savez que vous obtiendrez une performance de cas moyen en moyenne, indépendamment des 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) en tant que MAC (code d’authentification de message). Si vous recevez un message et une balise SipHash, et que cette balise est identique à celle obtenue en exécutant SipHash avec votre clé secrète, vous savez que le créateur du hachage était également en possession de votre clé secrète et que ni le message, ni le le hash a été modifié depuis.

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

Paul Hsieh a déjà fait du hasch rapide . Il énumère le code source et les explications. Mais c'était déjà battu. :)

Java utilise cet algorithme simple multiplier-ajouter:

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

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

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

Il y en a probablement de bien meilleurs, mais ceci est assez répandu et semble constituer un bon compromis entre vitesse et unicité.

Tout d’abord, pourquoi avez-vous besoin de mettre en œuvre 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 soit disponible (à moins que vous ne le fassiez pour votre propre formation).

En ce qui concerne les algorithmes de hachage, 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;
}