Fonction additive


C'est une des plus simple, et aussi une des pires. La valeur hashée est tout simplement la somme des bytes individuels. L'implémentation est fort simple:





 inline unsigned HashAdditive(const unsigned char *buffer, 
                              int size)
  {
   unsigned h = 0;

   for (int i=0; i<size; i++)
    h += buffer[i];

   return h;
  }




Cette fonction est très mauvaise parce qu'elle dépend très fortement de la longueur de la clef. En fait, elle ne génère que de grosses valeurs pour les clefs très longues, alors qu'une bonne fonction devrait générer les valeurs sur 0 à 232-1 de façon indépendante de la longueur de la clef. En fait, si on regarde la distribution des valeurs générées, on voit une pointe près de 0, et rien, ou presque à l'autre extrémité du spectre.

En plus, cette fonction possède un élément neutre. Cet élément neutre, c'est celui de l'addition, le zéro. Pourquoi cela est-il important? C'est important car la fonction de hash est incapable de différencier entre des clefs qui contiennent plus ou moins de bytes à zéro, ce qui la rend difficilement utilisable sur des données de type binaire.

Les éléments neutres sont à éviter dans la construction d'une bonne fonction de hash.

Le fait que relativement peu de valeurs distinctes soient générées par la fonction sera un désavantage important: cela va causer des collisions primaires.




( steven.pigeon@videotron.ca )