Jai testé différents algorithmes, mesurant la vitesse et le nombre de collisions .

Jai utilisé trois jeux de clés différents:

• Une liste de 216 553 mots anglais ^{🕗  archive} (en minuscules)
• Les nombres "1" à "216553" (pensez aux codes postaux, et comment un mauvais hachage a détruit msn.com ^{🕗  archive} )
• 216 553  » random « (ie type 4 uuid ) GUID

Pour chaque corpus, le nombre de collisions et le temps moyen passé à hacher a été enregistré.

Jai testé:

• DJB2
• DJB2a (variante utilisant xor plutô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 

Remarques :

• Le Lalgorithme LoseLose (où hash = hash + character) est vraiment horrible . Tout entre en collision dans les mêmes 1 375 seaux
• SuperFastHash est rapide, les choses semblent assez dispersées; par mon Dieu, le nombre de collisions. Jespère que le type qui la porté a eu un problème; cest plutôt mauvais
• CRC32 est plutôt bon . Table de recherche plus lente et 1k

Des collisions se produisent-elles réellement?

Oui. Jai commencé à écrire mon programme de test pour voir si des collisions de hachage se produisent réellement – et ne sont pas simplement une construction théorique.Elles se produisent effectivement:

Collisions FNV-1

• creamwove entre en collision avec quists

FNV -1a collisions

• 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 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
• entre en collision avec vigils
• finks entre en collision avec vinic

Randomnessification

Lautre mesure subjective est la répartition aléatoire des hachages. Le mappage des HashTables résultants montre la répartition uniforme des données. Toutes les fonctions de hachage montrent une bonne distribution lors du mappage linéaire de la table:

Ou comme Hilbert Map ( XKCD est toujours pertinent ):

Sauf lors du hachage de chaînes numériques ("1", "2", …, "216553") (par exemple, codes postaux ), là où les motifs commencent pour émerger dans la plupart des algorithmes de hachage:

SDBM :

DJB2a :

FNV-1 :

Tous sauf

Si vous souhaitez créer une carte de hachage à partir dun 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 de la table de hachage, vous pouvez garantir, pour un ensemble de données donné, quil ny aura pas de collisions.

Commentaires

• Ici ‘ en savoir plus sur (minimal) Perfect Hashing burtleburtle.net/bob/hash/perfect.html y compris les données de performances, bien quil nutilise ‘ pas le processeur le plus récent, etc.
• Cela ‘ est assez évident, mais il convient de souligner que pour garantir labsence de collisions, les clés devraient avoir la même taille que les valeurs, sauf si Il existe des contraintes sur les valeurs sur lesquelles lalgorithme peut capitaliser.
• @ devios1 Votre déclaration na pas de sens. Premièrement, les valeurs dune table de hachage, parfaites ou non, sont indépendantes des clés. Deuxièmement, une table de hachage parfaite est juste un tableau linéaire de valeurs, indexées par le résultat de la fonction qui a été conçue pour que tous les index soient uniques.
• @MarcusJ Le hachage parfait est généralement utilisé avec moins de 100 clés, mais jetez un oeil à cmph.sourceforge.net … encore loin de votre portée.
• @DavidCary Rien à votre lien prend en charge votre réclamation. Vous avez peut-être confondu O (1) avec  » aucune collision « , mais elles ne sont pas ‘ T du tout la même chose. Bien sûr, un hachage parfait garantit labsence de collision, mais il nécessite que toutes les clés soient connues à lavance et quil y en ait relativement peu. (Mais voir le lien vers cmph ci-dessus.)

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

Si vous voulez juste avoir une bonne fonction de hachage , et je ne peux pas attendre, djb2 est lune des meilleures fonctions de hachage de chaîne que je connaisse. Il a une excellente distribution et vitesse sur de nombreux ensembles 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; } 

Commentaires

• En fait, djb2 est sensible à zéro, comme la plupart de ces fonctions de hachage simples, vous pouvez donc facilement casser ces hachages.Il a un mauvais biais, trop de collisions et une mauvaise distribution, il casse sur la plupart des tests de qualité plus subtils: Voir github.com/rurban/smhasher/blob/master/doc/bernstein Sa base de données cdb lutilise, mais je ne ‘ pas lutiliser avec un accès public.
• DJB est assez mauvais du point de vue des performances et de la distribution. Je ne ‘ pas lutiliser aujourdhui.
• @ConradMeyer Je parie ‘, DJB peut être accéléré par un facteur de trois, comme dans cette question à moi , puis ‘ battait probablement la plupart des algorithmes utilisables. Concernant la distribution, je suis daccord. Un hachage produisant des collisions même pour des chaînes de deux lettres peut ‘ être vraiment bon.
• Les gars, jai des doutes. Vous dites que djb2 est mauvais, mais les résultats du test de la réponse acceptée montrent que cest bon.
• Vous pouvez au moins utiliser un prime raisonnable qui produit moins de collisions au lieu de 33. stackoverflow.com/a/2816747/21499

CityHash by Google est lalgorithme que vous recherchez. Ce nest pas bon pour la cryptographie mais cest 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 existe également un port C ordinaire .

À propos de la prise en charge 32 bits:

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

Commentaires

• La prononciation de CityHash est-elle similaire à  » City Sushi?  »
• Vous avez un regardez aussi SipHash, il est destiné à remplacer MurmurHash / CityHash / etc.: 131002.net/siphash
• Voir également FarmHash, a successeur de CitHash. code.google.com/p/farmhash
• xxHash prétend être 5 fois plus rapide que CityHash.
• plain C port le lien est rompu

Jai tracé une courte comparaison de vitesse de différents algorithmes de hachage lors du hachage de fichiers.

Les graphiques individuels ne diffèrent que légèrement dans la méthode de lecture et peuvent être ignorés ici, puisque tous les fichiers ont été stockés dans un tmpfs. Par conséquent, le benchmark nétait pas lié aux E / S si vous vous posez la question.

• Échelle linéaire
• Échelle logarithmique

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 faut noter que Cityhash peut être plus rapide sur les CPU avec linstruction SSE 4.2s CRC, que mon CPU na pas. SpookyHash était dans mon cas toujours un tout petit peu avant CityHash.
• MD5 semble être un bon compromis lors de lutilisation des fonctions de hachage cryptographique, bien que SHA256 puisse être plus sécurisé pour vulnérabilités de collision de MD5 et SHA1.
• La complexité de tous les algorithmes est linéaire – ce qui nest vraiment pas surprenant puisquils fonctionnent par blocs. (Je voulais voir si la méthode de lecture fait une différence, donc vous pouvez simplement comparer les valeurs les plus à droite).
• SHA256 était plus lent que SHA512.
• Je nai pas étudié le caractère aléatoire de les fonctions de hachage. Mais ici est une bonne comparaison des fonctions de hachage qui manquent dans la réponse dIan Boyds . Cela indique que CityHash a quelques problèmes dans les cas dangle.

La source utilisée pour les tracés:

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

Commentaires

• Le graphique à échelle linéaire coupe létiquette de laxe y qui indique la quantité à tracer. Je suppose que ce serait probablement  » temps en secondes « , identique à léchelle logarithmique. Cela vaut la peine dêtre corrigé ‘.

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

Lhypothèse selon laquelle les fonctions de hachage cryptographique sont plus uniques est fausse, et en fait, on peut montrer quelle est souvent à lenvers dans la pratique. En vérité:

1. Les fonctions de hachage cryptographique devraient idéalement être indiscernables du hasard ;
2. Mais avec les fonctions de hachage non cryptographiques, il est souhaitable quelles interagissent favorablement avec les entrées probables .

Ce qui signifie quune fonction de hachage non cryptographique peut bien avoir moins de collisions quun un cryptographique pour un « bon » ensemble de données – des ensembles de données pour lesquels il a été conçu.

Nous pouvons en fait le démontrer avec les données de la réponse de Ian Boyd et un peu de maths: le Problème danniversaire . La formule pour le nombre attendu de paires en collision si vous choisissez des n entiers au hasard dans lensemble [1, d] est la suivante (tirée de Wikipedia):

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

Brancher n = 216,553 et d = 2 ^ 32 nous obtenons environ 5,5 collisions attendues . Les tests dIan montrent principalement des résultats dans ce quartier, mais à une exception près: la plupart des fonctions ont zéro collisions dans le tests de nombres consécutifs. La probabilité de choisir 216 553 nombres de 32 bits au hasard 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 collisions!

Donc, ce que nous voyons ici, cest que les hachages testés par Ian interagissent favorablement avec le jeu de données de nombres consécutifs, cest-à-dire quils « re-dispersent de manière minimalement différente plus largement quune fonction de hachage cryptographique idéale ne le ferait. (Remarque: cela signifie que lévaluation graphique de Ian selon laquelle FNV-1a et MurmurHash2 « lui semblent aléatoires » dans lensemble de données numériques peut être réfutée à partir de ses propres données. Aucune collision sur un ensemble de données de cette taille, pour les deux fonctions de hachage, est étonnamment non aléatoire!)

Ce nest pas une surprise car cest 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 dIan mentionne un problème que MSN a déjà rencontré avec les tables de hachage de code postal . Cest une utilisation où lévitement de collision sur les entrées probables lemporte sur le comportement de type aléatoire.

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

• CRC est conçu pour détecter les erreurs résultant de canaux de communication bruyants , qui sont probablement un petit nombre de retournements de bits;
• Les hachages cryptographiques sont conçus pour capturer les modifications apportées par des attaquants malveillants , à qui sont allouées des ressources de calcul limitées mais arbitrairement beaucoup dintelligence.

Donc, pour CRC, il est encore bon davoir moins de collisions qualéatoires dans des entrées minimalement différentes. Avec les hachages cryptographiques, cest un non-non!

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

En fait, leur vitesse peut parfois être un problème. En particulier, une technique courante pour stocker un jeton dérivé dun mot de passe est dexécuter un algorithme de hachage rapide standard 10000 fois (en stockant 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 

Résultat:

Rehearsal ------------------------------------ 1.480000 0.000000 1.480000 ( 1.391229) --------------------------- total: 1.480000sec user system total real 1.400000 0.000000 1.400000 ( 1.382016) 

Commentaires

• Il est ‘ relativement rapide, bien sûr, pour un algorithme de hachage cryptographique . Mais lOP veut juste stocker des valeurs dans une table de hachage, et je ne pense ‘ quune fonction de hachage cryptographique est vraiment appropriée pour cela.
• La question soulevée (tangentiellement, il apparaît maintenant) le sujet des fonctions de hachage cryptographique. Cest ‘ que je réponds.
• Juste pour dissuader les gens de lidée de  » En particulier , une technique courante pour stocker un jeton dérivé dun mot de passe consiste à exécuter un algorithme de hachage rapide standard 10 000 fois  » – bien que courant, cela ‘ Cest tout simplement stupide. Il existe des algorithmes conçus pour ces scénarios, par exemple bcrypt. Utilisez les bons outils.
• Les hachages cryptographiques sont conçus pour avoir un débit élevé, mais cela signifie souvent quils ont des coûts élevés de configuration, de démontage, de .rodata et / ou détat .Lorsque vous voulez un algorithme pour une table de hachage, vous avez généralement des clés très courtes, et beaucoup dentre elles, mais vous navez pas besoin des garanties supplémentaires dune cryptographie. Jutilise moi-même un Jenkins modifié un à un.
• @ChrisMorgan: plutôt que dutiliser un hachage cryptographiquement sécurisé, HashTable DoS peut être résolu beaucoup plus efficacement en utilisant la randomisation de hachage, de sorte que chaque exécution de les programmes ou même sur chaque table de hachage, donc les données ne sont ‘ pas regroupées dans le même bucket à chaque fois.

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

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

• Sécurisé. SipHash est une forte PRF (fonction pseudo-aléatoire). Cela signifie quil est impossible de le distinguer dune fonction aléatoire (sauf si vous connaissez la clé secrète de 128 bits). Par conséquent:

  • Pas besoin de sinquiéter du fait que vos sondes de table de hachage deviennent linéaires en temps en raison de collisions. Avec SipHash, vous savez que vous obtiendrez des performances moyennes en moyenne, 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 de 128 bits) comme MAC (Code dauthentification de message). Si vous recevez un message et une balise SipHash et que la balise est la même que celle de lexé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 hash ont été modifiés depuis.

Commentaires

• Isn ‘ t SipHash exagéré sauf si vous avez besoin de sécurité? Nécessite une clé de 128 bits qui nest quune graine de hachage glorifiée. Sans oublier que MurmurHash3 a une sortie de 128 bits et SipHash na quune sortie de 64 bits. Évidemment, le plus gros condensé a moins de chances de collision.
• @bryc La différence est que SipHash continuera à se comporter correctement, même sur des entrées malveillantes. Une table de hachage basée sur SipHash peut être utilisée pour des données provenant de sources potentiellement hostiles, et peut utiliser un algorithme tel que le sondage linéaire qui est très sensible aux détails de la fonction de hachage.
• Siphash (et prng plus récent associé fonctions de style) est mon choix par défaut pour la sécurité. Pour la performance, xxhash est difficile à battre. Il y a des tonnes de mauvais conseils de hachage sur Internet, même dans les discussions ici. Une bonne performance sur des entrées aléatoires ou semi-aléatoires na pas de sens. Quelle est la pire des performances, avec des entrées du monde réel? Quel est le résultat des entrées malveillantes? Votre table de hachage deviendra éventuellement un vecteur dattaque.

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

Paul Hsieh a déjà effectué un hachage rapide . Il liste le code source et les explications. Mais il était déjà battu. 🙂

Java utilise cette multiplication simple -et-ajouter un algorithme:

Le code de hachage dun objet String est calculé comme

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

en utilisant larithmé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 lexponentiation. (La valeur de hachage de la chaîne vide est zéro.)

Il y en a probablement de bien meilleurs mais cest assez répandu et semble être un bon compromis entre vitesse et caractère unique.

Commentaires

• Je ne ‘ pas utiliser exactement la même chose celui utilisé ici, car il ‘ est encore relativement facile de produire des collisions avec cela. Ce ‘ nest certainement pas terrible, mais il y en a de bien meilleurs. Et sil ny a ‘ aucune raison significative dêtre compatible avec Java, il ne devrait pas être choisi.
• Si vous choisissez toujours ceci façon de hacher pour une raison quelconque, vous pouvez au moins utiliser un meilleur premier comme 92821 comme multiplicateur. Cela réduit beaucoup les collisions. stackoverflow.com/a/2816747/21499
• Vous pourriez aussi bien utiliser FNV1a à la place. Il ‘ est également un simple hachage basé sur la multiplication, mais utilise un multiplicateur plus grand, qui disperse mieux le hachage.
• Vous ne ‘ Je veux faire s[0]*31^3 + s[1]*31^2 + s[2]*31 + s[3]. Évitez lopérateur dalimentation (^) et procédez comme suit: ((s[0]*31 + s[1])*31 + s[2])*31 + s[3].
• @LeopoldoSanczyk Oui, dans le code, cest (et devrait être) fait de manière itérative, cétait juste plus facile à comprendre dans une formule fermée.

Tout dabord, pourquoi avez-vous besoin dimplémenter votre propre hachage? Pour la plupart des tâches, vous devriez obtenir de bons résultats avec des structures de données dune bibliothèque standard, en supposant quune implémentation est disponible (à moins que vous ne le fassiez uniquement pour votre propre formation).

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

Voici un exemple dimplé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; } 

Commentaires

• La variante FNV-1a est légèrement meilleure avec le caractère aléatoire. Permutez lordre de * et ^: h = (h * 16777619) ^ p[i] == > h = (h ^ p[i]) * 16777619