Meilleur algorithme de hachage en termes de collisions de hachage et de performances pour les chaînes

Comme Nigel Campbell , a indiqué, il n'y a pas une telle chose comme la "meilleure" fonction de hachage, car il dépend des caractéristiques des données de ce que vous êtes de hachage ainsi que si oui ou non vous avez besoin de chiffrement de la qualité des hachages.

cela dit, voici quelques conseils:

• puisque les éléments que vous utilisez comme entrée dans le hachage ne sont qu'un ensemble de chaînes, vous pouvez simplement combiner les hashcodes pour chacun de ces chaînes individuelles. J'ai vu le pseudo-code suivant suggéré pour le faire, mais je ne sais pas d'analyse particulière de celui-ci:

  int hashCode = 0;
  
  foreach (string s in propertiesToHash) {
      hashCode = 31*hashCode + s.GetHashCode();
  }
  

  selon cet article , système.Web a une méthode interne qui combine les hashcodes en utilisant

  combinedHash = ((combinedHash << 5) + combinedHash) ^ nextObj.GetHashCode();
  

  j'ai aussi vu le code qui simplement xor de la hashcodes ensemble, mais cela semble être une mauvaise idée pour moi (mais j'ai encore aucune analyse pour). Si rien n' autrement, vous finissez avec une collision si les mêmes cordes sont hachées dans un ordre différent.

• j'ai utilisé FNV à bon effet: http://www.isthe.com/chongo/tech/comp/fnv/

• Paul Hsieh a un article décent: http://www.azillionmonkeys.com/qed/hash.html

• un autre bel article de Bob Jenkins qui a été publié pour la première fois en 1997 dans le journal du Docteur Dobb (l'article relié est mis à jour): http://burtleburtle.net/bob/hash/doobs.html

il n'y a pas un seul algorithme de hachage optimal. Si vous avez un domaine d'entrée connu, vous pouvez utiliser un générateur de hachage parfait tel que gperf pour générer un algorithme de hachage qui obtiendra un taux de 100% sur ce jeu d'entrée particulier. Sinon, il n'y a pas de "bonne" réponse à cette question.

je vais être boiteux ici et donner une réponse plus théorique plutôt une épingle-réponse mais s'il vous plaît prendre la valeur en elle.

Premièrement, il y a deux problèmes distincts:

A. Probabilité de Collision B. Performances du hachage (temps, cycles cpu, etc.))

les deux problèmes sont légèrement liés. Ils ne sont pas parfaitement corrélés.

le problème a traite de la différence entre hashee et les espaces de hash résultants. Lorsque vous hachez un fichier de 1KB (1024 octets) et le hachage a 32 octets il y aura:

1,0907481356194159294629842447338 e+2466 (i.e. un nombre avec 2466 zéros) combinaisons possibles de fichiers d'entrée

et l'espace de hachage aura

1,1579208923731619542357098500869 e+77 (c'est à dire un numéro 77 de zéros)

la différence est énorme. il y a 2389 zéros différence entre eux. Il y aura des COLLISIONS (une collision est un cas spécial où deux fichiers d'entrée différents auront exactement le même hachage) puisque nous réduisons 10^2466 cas à 10^77 cas.

la seule façon de minimiser le risque de collison est d'agrandir l'espace de hachage et donc de rendre les hahs plus long. Idéalement, le hachage aura la longueur du fichier, mais c'est un peu débile.

le deuxième problème est la performance. Cette seule traite avec l'algorithme de hachage. Bien sûr, un hachage plus long nécessitera probablement plus de cycles cpu, mais un algorithme plus intelligent pourrait ne pas l'être. J'ai pas vraiment de réponse à cette question. C'est tout simplement trop difficile.

cependant, vous pouvez comparer/mesurer différentes implémentations de hachage et en tirer des pré-conclusions.

Bonne chance ;)

le hashCode simple utilisé par la classe de chaîne de caractères de Java peut montrer un algorithme approprié.

ci-dessous se trouve l'implémentation" GNU Classpath". (Licence: GPL)

  /**
   * Computes the hashcode for this String. This is done with int arithmetic,
   * where ** represents exponentiation, by this formula:<br>
   * <code>s[0]*31**(n-1) + s[1]*31**(n-2) + ... + s[n-1]</code>.
   *
   * @return hashcode value of this String
   */
  public int hashCode()
  {
    if (cachedHashCode != 0)
      return cachedHashCode;

    // Compute the hash code using a local variable to be reentrant.
    int hashCode = 0;
    int limit = count + offset;
    for (int i = offset; i < limit; i++)
      hashCode = hashCode * 31 + value[i];
    return cachedHashCode = hashCode;
  }

vous pouvez obtenir les deux en utilisant la fonction de hachage de Knuth décrit ici .

c'est extrêmement rapide en supposant une table de hachage de puissance-de-2 la taille -- juste une multiplication, un quart, et un bit-et. Plus important encore (pour vous), c'est un excellent moyen de minimiser les collisions (voir cette analyse ).

certains autres bons algorithmes sont décrits ici .

j'adore Stackoverflow! La lecture de cette question m'a fait regarder dans les fonctions de hachage un peu plus et j'ai trouvé le hachage de coucou .

De l'article:

La recherche

exige l'inspection de seulement deux emplacements dans la table de hachage, qui prend du temps constant dans le pire des cas (voir notation Big O). C'est dans contraste avec beaucoup d'autres tables de hachage les algorithmes, qui peuvent ne pas avoir limite constante du pire cas sur le moment pour faire une recherche.

je pense que cela correspond à vos critères de collision et de performance. Il semble que le compromis est que ce type de table de hachage ne peut obtenir que 49% pleine.

Voici une façon simple de le mettre en œuvre vous-même: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html

voici un extrait du billet:

si disons que nous avons un jeu de caractères du capital anglais, les lettres, la longueur du jeu de caractères est de 26 où l'Un peut être représenté par le nombre 0, B par le nombre 1, C par le numéro 2 et ainsi de suite jusqu'à Z par le nombre de 25. Maintenant, chaque fois que nous voulons pour mapper une chaîne de ce jeu de caractères à un nombre unique , nous effectuons la même conversion que nous l'avons fait dans le cas du format binaire

"Murmurhash" est assez bonne sur les performances et les collisions.

mentionnés thread à "softwareengineering.stackexchange" a quelques tests et Murmure gagne.

j'ai écrit mon propre C# port de MurmurHash 2 à .NET et je l'ai testé sur une liste de 466k mots anglais, j'ai eu 22 collisions.

les résultats et la mise en œuvre sont ici: https://github.com/jitbit/MurmurHash.net (clause de non-responsabilité, je suis impliqué avec ce projet open source!)