Quel est le meilleur 32bit fonction de hachage pour de courtes chaînes de caractères (noms de balise)?

Quel est le meilleur 32bit fonction de hachage pour relativement courtes chaînes?

Les chaînes de caractères sont des noms de balises qui consistent en anglais des lettres, des chiffres, des espaces et des caractères supplémentaires (#, $, ., ...). Par exemple: Unit testing, C# 2.0.

Je suis à la recherche pour le "meilleur", comme dans "minime collisions', la performance n'est pas important pour mes objectifs.

possible en double stackoverflow.com/questions/251346/...
Pas complètement, parce que ma question est plus précise en termes de hachage de taille et ignore les performances. Aussi, je ne suis pas à la recherche d'une fonction de hachage, je suis à la recherche d'un bon choix -- je sais qu'il y a CRC32 et FNV32, mais ce qui est le mieux pour mon nom de domaine?
Est votre liste de balises fixes à un ensemble de chaînes ou elle va se développer de manière dynamique au fil du temps?
Les balises sont ajoutés par des gens donc je ne peux pas prévoir (mais il y a de la longueur et de la limite de caractères).
Quelles sont les limites?
Longueur Max: 20, jeu de caractères actuel: [A-Za-z\d\.#$@\-\ ] (ce qui peut augmenter légèrement si je constate que certains symbole fort utile, je l'ai raté).
La page suivante a plusieurs implémentations de l'objectif général des fonctions de hachage qui sont efficaces et d'exposition minimale des collisions: partow.net/programming/hashfunctions/index.html

InformationsquelleAutor Andrey Shchekin | 2010-02-28

22

Si la performance n'est pas important, il suffit de prendre un secure hash comme MD5 ou SHA1, et de tronquer sa sortie de 32 bits. Cela vous donnera une distribution de codes de hachage qui est indiscernable de hasard.
- md5 est parfait pour ce scénario
- MD4 (voir tools.ietf.org/html/rfc1320 ) peut-être même mieux, puisqu'il est légèrement plus simple à mettre en œuvre que MD5. Notez que ni MD4, ni MD5 est indiscernable de hasard (les deux ont été "le point de vue cryptographique cassé"), mais ils sont encore assez proche de l'objet à portée de main.
- Pensez-vous qu'il aurait moins de collisions que Nick D de la réponse? Je suis un peu indécis sur ce que d'approuver ou de les utiliser.
- MD5 est cassée dans le sens que vous pouvez créer un hash collision de deux plaintexts qui produisent le même hash. Cela ne veut pas dire que la sortie de MD5 est à distinguer de l'aléatoire - il n'y a pas preimage attaques contre MD5. Ce qui est plus facile à mettre en œuvre est une sorte de hors de propos, trop il va presque certainement avoir une pré-faites MD5 ou SHA1 mise en œuvre dans sa langue de leur choix.
- Sécuriser les hachages tels que SHA1 et MD5 ont le moins de collisions théoriquement possible. Plus rapide hachages comme celui de Nick suggère sont d'excellents où la vitesse est importante, mais ont plus de collisions. La langue de votre choix presque à coup sûr un pré-faites la mise en œuvre de MD5 ou SHA1, trop.
- attaques contre MD5 sont fondées sur une différence de chemin. En appliquant l'entrée de la différence sur un MD5 d'entrée, vous avez un petit mais plus-que-aléatoire probabilité de trouver la différence attendue à la sortie. Cela ne conduit pas à une preimage attaque, mais il fait MD5 se distinguer d'un oracle aléatoire. Dans le cas de MD4, cela a été montré pour être (théoriquement) exploitable quand utilisé dans l'algorithme HMAC (où les collisions en soi, ne sont pas de soucis).
- Ok, merci, je vais l'utiliser.
- Je corrige la position des mains. Je ne savais pas que MD4 a été brisé, même pour les Hmac - résultat intéressant!
- J'ai testé MD5, Sha1 et nomal CRC32, et ils ont presque le même taux de collision, tout au sujet de 0,23%. Donc, MD5 et SHA1, rien de mieux ici. Est-il mieux de hachage que md5 et sha1?
InformationsquelleAutor Nick Johnson
24

Je ne suis pas sûr si c'est le meilleur choix, mais ici, c'est une fonction de hachage pour les chaînes:

la Pratique de La Programmation (TABLES de HACHAGE, pg. 57)
```
/* hash: compute hash value of string */
unsigned int hash(char *str)
{
   unsigned int h;
   unsigned char *p;

   h = 0;
   for (p = (unsigned char*)str; *p != '/* hash: compute hash value of string */
unsigned int hash(char *str)
{
unsigned int h;
unsigned char *p;
h = 0;
for (p = (unsigned char*)str; *p != '\0'; p++)
h = MULTIPLIER * h + *p;
return h; //or, h % ARRAY_SIZE;
}
'; p++)
      h = MULTIPLIER * h + *p;
   return h; //or, h % ARRAY_SIZE;
}
```
Empiriquement, les valeurs de 31 et 37 ont
avéré être un bon choix pour l'

multiplicateur en fonction de hachage pour les chaînes ASCII.
- Yep, nous utilisons cette même fonction de hachage avec MULTIPLICATEUR = 37 pour les chaînes et les chemins. Fonctionne bien pour nous, et je ai pas encore rencontré un problème de collision, même après 2 ans ( bien sûr, il n'y a aucune garantie que nous ne quand même )
- Absolument, cela semble assez simple. Des idées pourquoi FNV a été créé beaucoup plus simple approche fonctionne?
- Shchekin, j'utilise de la FNV hash quand je traite avec des octets (blob). Peut-être, la fonction ci-dessus donne de meilleurs résultats spécifiquement avec des chaînes. Je ne suis pas sûr.
- Nick D - Principale raison pour laquelle nous utilisons l'algorithme ci-dessus est pour la vitesse. Je sais que la performance n'était pas une priorité pour Andrey donc peut-être pas pertinents. J'ai aussi utilisé FNV32 mais plus le hachage des données binaires comme Nick d'mentionné. Peut pas vraiment comparer à périmètre comparable, mais - peut-être la peine d'essayer les deux et voir lequel des deux a le plus faible taux de collision
- Je remarque que Perl algorithme de hachage utilise le MULTIPLICATEUR=33, et fait une étape supplémentaire à la fin: h + = h >> 5) améliorer la distribution de bits de niveau inférieur.
- Cela a été très utile.
- Cet algorithme est l'une des variantes étudiées dans le cst.yorku.ca/~oz/hash.html. Il est malheureusement sujette à base de hachage-attaques par collision (voir [ocert.org/advisories/ocert-2011-003.html]), car il est trivial d'utiliser substring (voir référence papier) collision de calcul; mais il peut bien fonctionner si elle n'est jamais utilisée avec l'extérieur-clés fournies.
InformationsquelleAutor Nick Dandoulakis
14

Je suis désolé pour la réponse tardive sur ce. Plus tôt cette année, j'ai composé une page intitulée Le Hachage Des Chaînes Courtes qui pourrait être utile dans cette discussion. En résumé, j'ai trouvé que la CRC-32 et de la FNV-1a sont de qualité supérieure pour le hachage des chaînes courtes. Ils sont efficaces et produit largement diffusé et libre de collision hachages dans mes tests. J'ai été surpris de constater que MD5, SHA-1 et SHA-3 produit un petit nombre de collisions lorsque la sortie a été plié à 32 bits.
- CRC32 est toujours la meilleure réponse ici
- Je pense aussi que CRC32 devrait être en tête de classement répondre
- En fait, CRC32 de distribution est assez terrible par rapport aux alternatives. Pour la version 32 bits de tables de hachage, même un naïfs algorithme de type de produit/de rotation peut produire une meilleure distribution pour <8byte chaînes, et à éventuellement être beaucoup plus rapide. En parlant de cela, xxHash exactement ce que fait, mais avec beaucoup mieux la distribution, et spécialement optimisé pour les processeurs modernes (très différent de CRC32). Pour le hachage d'un grand nombre de petites chaînes avec une baisse du nombre de collisions (comme lors de lexing), DJB2 est probablement la meilleure option.
InformationsquelleAutor gfkeogh
1

Vous pouvez vérifier murmurhash2. Il est rapide, même pour les petites chaînes, et a un bon mélange de l'étape finale, de sorte qu'il est encore bon mixte pour les très petites chaînes.

InformationsquelleAutor Ritsaert Hornstra
1

Qui dépend de votre matériel.
Sur le matériel moderne, c'est à dire Intel/AMD avec SSE4.2 ou arm7 vous devez utiliser l'interne _mm_crc32_uxx intrinsèques, comme ils le sont optimales pour des chaînes courtes. (Pour les longues touches aussi, mais alors mieux utiliser Adler version filetée, comme dans zlib)

Sur de vieux ou inconnu matériel, soit au moment de l'exécution de la sonde pour le SSE4.2 ou CRC32 de fonctionnalité ou d'utiliser un seul si le simple bon de fonctions de hachage. E. g. Murmur2 ou de la Ville

Un aperçu de la qualité et de la performance est ici:
https://github.com/rurban/smhasher#smhasher

Il y a aussi toutes les implémentations. Favorisée sont https://github.com/rurban/smhasher/blob/master/crc32_hw.c et https://github.com/rurban/smhasher/blob/master/MurmurHash2.cpp

Si vous connaissez les clés à l'avance, utiliser un parfait de hachage, pas une fonction de hachage. E. g. gperf ou mon phash: https://github.com/rurban/Perfect-Hash#name

Aujourd'hui de hachage parfait génération via un compilateur c est si rapide, vous pouvez même créer à la volée, et dynaload il.
- Mise à jour: Murmur2 et la Ville ne peut pas être appelé simple de bonnes fonctions de hachage plus. Le plus rapide serait FNV1 ou CRC32-C, le mieux serait de Métro ou Farmhash.
- SpookyHash64 a toujours le meilleur shoda des avalanches/le plus bas taux de collisions de toutes les fonctions de hachage j'ai trouvé, j'aimerai fortement des conseils de l'utiliser pour robin des bois de hachage les cartes, sauf si vous avez empiriquement constaté que d'autres fonctions de hachage sont mieux/plus vite. Pour les petites entrées, je recommanderais FNV1A ou DJB2. SpookyHash a un assez haut coût de la mise en pointant à ~30 cycles. Métro/Ferme/Murmure/Ville/xxHash/beaucoup d'autres sont grands pour rapide, à des fins générales de hachage, avec moins de temps de préparation, mais une augmentation des taux de collisions. Je ne voudrais pas l'utiliser lorsque le faible taux de collisions sont importantes.
InformationsquelleAutor rurban
0

Si c'est rare que les utilisateurs d'ajouter de nouvelles balises, vous pouvez utiliser un parfait hachage (http://en.wikipedia.org/wiki/Perfect_hash_function) c'est recalculée chaque fois qu'un nouveau tag est ajouté. Bien sûr, sans connaître le problème que vous êtes vraiment essayer de résoudre, c'est la conjecture de comprendre ce que vous pourriez faire.

InformationsquelleAutor

Utilisation MaPrime2c fonction de hachage:

 
static const unsigned char sTable[256] = 
{ 
0xa3,0xd7,0x09,0x83,0xf8,0x48,0xf6,0xf4,0xb3,0x21,0x15,0x78,0x99,0xb1,0xaf,0xf9, 
0xe7,0x2d,0x4d,0x8a,0xce,0x4c,0xca,0x2e,0x52,0x95,0xd9,0x1e,0x4e,0x38,0x44,0x28, 
0x0a,0xdf,0x02,0xa0,0x17,0xf1,0x60,0x68,0x12,0xb7,0x7a,0xc3,0xe9,0xfa,0x3d,0x53, 
0x96,0x84,0x6b,0xba,0xf2,0x63,0x9a,0x19,0x7c,0xae,0xe5,0xf5,0xf7,0x16,0x6a,0xa2, 
0x39,0xb6,0x7b,0x0f,0xc1,0x93,0x81,0x1b,0xee,0xb4,0x1a,0xea,0xd0,0x91,0x2f,0xb8, 
0x55,0xb9,0xda,0x85,0x3f,0x41,0xbf,0xe0,0x5a,0x58,0x80,0x5f,0x66,0x0b,0xd8,0x90, 
0x35,0xd5,0xc0,0xa7,0x33,0x06,0x65,0x69,0x45,0x00,0x94,0x56,0x6d,0x98,0x9b,0x76, 
0x97,0xfc,0xb2,0xc2,0xb0,0xfe,0xdb,0x20,0xe1,0xeb,0xd6,0xe4,0xdd,0x47,0x4a,0x1d, 
0x42,0xed,0x9e,0x6e,0x49,0x3c,0xcd,0x43,0x27,0xd2,0x07,0xd4,0xde,0xc7,0x67,0x18, 
0x89,0xcb,0x30,0x1f,0x8d,0xc6,0x8f,0xaa,0xc8,0x74,0xdc,0xc9,0x5d,0x5c,0x31,0xa4, 
0 x 70,0x88,0x61,0x2c 0x9f,0x0d,0x2b,0x87,0x50,0x82,0x54,0x64,0x26,0x7d,0x03,0x40, 
0x34,0x4b,0x1c,0 x 73,0xd1,0xc4,0xfd,0x3b,0xcc,0xfb,0x7f,0xab,0xe6,0x3e,0x5b,les flux de jetons 0xa5, 
0xad,0x04,0x23,0x9c,0x14,0 x 51,0x22,0xf0,0 x 29,0x79,0x71,0x7e,0xff,0x8c,0x0e,0xe2, 
0x0c,0xef,0xbc,0x72,0x75,0x6f,0x37,0xa1,0xec,0xd3,0x8e,0x62,0x8b,0x86,0x10,0xe8, 
0x08,0x77,0x11,0xbe,0x92,0x4f,0x24,0xc5,0x32,0x36,0x9d,0xcf,0xf3,0xa6,0xbb,0xac, 
0x5e,0x6c,0xa9,0x13,0x57,0x25,0xb5,0xe3,0xbd,0xa8,0x3a,0x01,0x05,0x59,0x2a,0x46 
}; 


#define PRIME_MULT 1717 


unsigned int 
maPrime2cHash (unsigned char *str, unsigned int len) 
{ 
unsigned int hash = len, j'; 


for (i = 0; i != len; i++, str++) 
{ 

hachage ^= sTable[( *str + i) & 255]; 
hash = hash * PRIME_MULT; 
} 

de retour de hachage; 
}

et de regarder http://www.amsoftware.narod.ru/algo2.html pour MaFastPrime, MaRushPrime, etc tests.

InformationsquelleAutor Alexander

0

Si votre programme a besoin de communiquer avec d'autres système, il est préférable d'utiliser un algorithme qui est bien connue. Le quick & sale est à l'aide de premiers caractères de hachage md5. Vous n'avez pas besoin de passer des heures ou des jours pour inventer des roues de votre projet.

L'inconvénient est d'obtenir beaucoup beaucoup plus grande chance de collisions. Toutefois, si votre valeur de hachage est pour un horodatage de la session, ou courte vie circulates la tâche. Il n'y a pas de problème pour l'utiliser.

InformationsquelleAutor Yi Jiang

Vous devez vous connecter pour publier un commentaire.