Quelle est la meilleure fonction de hachage 32 bits pour les chaînes courtes (noms de balises) ?

Question

Quelle est la meilleure fonction de hachage 32 bits pour les chaînes de caractères relativement courtes ?

Les chaînes sont des noms de balises qui se composent de lettres anglaises, de chiffres, d'espaces et de quelques caractères supplémentaires ( # , $ , . , ...). Par exemple : Unit testing , C# 2.0 .

Je recherche le "meilleur", c'est-à-dire le "minimum de collisions". Les performances ne sont pas importantes pour mes objectifs.

Answer 1

Je ne suis pas sûr que ce soit le meilleur choix, mais voici une fonction de hachage pour les chaînes de caractères :

La pratique de la programmation (TABLES HASH, p. 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 != '\0'; p++)
      h = MULTIPLIER * h + *p;
   return h; // or, h % ARRAY_SIZE;
}

Empiriquement les valeurs 31 et 37 se sont avérées être de bons choix pour le multiplicateur dans une fonction de hachage pour les chaînes ASCII.

Answer 2

Si les performances ne sont pas importantes, il suffit de prendre un hachage sécurisé tel que MD5 ou SHA1, et de tronquer sa sortie à 32 bits. Vous obtiendrez ainsi une distribution de codes de hachage qui ne se distingue pas du hasard.

Answer 3

Je suis désolé pour la réponse très tardive à ce sujet. Au début de l'année, j'ai composé une page intitulée Hachage de chaînes courtes qui pourrait être utile dans cette discussion. En résumé, j'ai trouvé que CRC-32 et FNV-1a sont supérieurs pour le hachage de chaînes courtes. Ils sont efficaces et ont produit des hachages largement distribués et sans collision dans mes tests. J'ai été surpris de constater que MD5, SHA-1 et SHA-3 produisaient un petit nombre de collisions lorsque la sortie était plié jusqu'à 32 bits.

Answer 4

Cela dépend de votre matériel. Sur du matériel moderne, c'est-à-dire Intel/AMD avec SSE4.2 ou arm7, vous devriez utiliser la fonction interne _mm_crc32_uxx intrinsèques, car ils sont optimaux pour les chaînes courtes. (Pour les clés longues aussi, mais alors mieux vaut utiliser la version threadée d'Adler, comme dans zlib)

Sur du matériel ancien ou inconnu, il faut soit vérifier l'exécution de la fonction SSE4.2 ou CRC32, soit utiliser une des bonnes fonctions de hachage simples. Par exemple, Murmur2 ou City.

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

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

Si vous connaissez les clés à l'avance, utilisez un hachis parfait et non une fonction de hachage. Par exemple. gperf ou mon phash : https://github.com/rurban/Perfect-Hash#name

De nos jours, la génération de hachages parfaits via un compilateur c est si rapide que vous pouvez même les créer à la volée, et le dynaload.

Answer 5

Utilisez 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,
  0x70,0x88,0x61,0x2c,0x9f,0x0d,0x2b,0x87,0x50,0x82,0x54,0x64,0x26,0x7d,0x03,0x40,
  0x34,0x4b,0x1c,0x73,0xd1,0xc4,0xfd,0x3b,0xcc,0xfb,0x7f,0xab,0xe6,0x3e,0x5b,0xa5,
  0xad,0x04,0x23,0x9c,0x14,0x51,0x22,0xf0,0x29,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, i;

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

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

  return hash;
}

et consultez le site www.amsoftware.narod.ru/algo2.html pour les tests MaFastPrime, MaRushPrime, etc.