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

Question

Quel serait le meilleur algorithme de hachage si nous avions les priorités suivantes (dans cet ordre):

1. Collisions de hachage minimales
2. Performance

Il n'est pas nécessaire que ce soit sécurisé. Fondamentalement, j'essaie de créer un index basé sur une combinaison de propriétés de certains objets. Toutes les propriétés sont des chaînes .

Toute référence aux implémentations c # serait appréciée.

Answer 1

Oubliez le terme "meilleur". Peu importe l'algorithme de hachage n'importe qui pourrait venir avec, sauf si vous avez un nombre très limité de données qui doit être haché, chaque algorithme qui fonctionne très bien, en moyenne, peuvent devenir complètement inutile si seulement nourris avec le droit (ou à partir de votre point de vue "mal") de données.

Au lieu de perdre trop de temps à penser à comment obtenir le hash plus sans accident sans l'aide de beaucoup trop de temps PROCESSEUR, je préfère commencer à réfléchir à "Comment faire pour que les collisions posent moins de problèmes". E. g. si chaque compartiment de hachage est en fait une table et toutes les chaînes de ce tableau (qui a eu une collision) sont triés par ordre alphabétique, vous pouvez effectuer une recherche dans un seau de table à l'aide de la recherche binaire (qui est seulement O(log n)) et cela signifie que, même lorsque chaque seconde de hachage seau a 4 collisions, votre code aura toujours des performances décentes (il sera un peu plus lent par rapport à une collision table libre, mais pas tant que ça). Un gros avantage ici est que si votre table est assez grande et votre hash n'est pas trop simple, deux chaînes de caractères résultant de la même valeur de hachage en général un aspect complètement différent (d'où la recherche binaire peut arrêter de comparer des chaînes après peut-être un ou deux personnages en moyenne; faire tous les comparer très rapide).

En fait j'ai eu une situation moi-même avant, où la recherche directement dans un tableau trié à l'aide de binaires de recherche s'est avéré être plus rapide que le hachage! Même si mon algorithme de hachage a été simple, il a fallu un certain temps pour hacher les valeurs. Des tests de Performance ont montré que seulement si je reçois plus de 700 à 800 entrées, le hachage est en effet plus rapide que la recherche binaire. Cependant, comme le tableau pourrait ne jamais se développer de plus de 256 entrées de toute façon et que la moyenne de la table a été en dessous de 10 entrées, l'analyse comparative a clairement montré que, sur chaque système, chaque CPU, le binaire de recherche a été plus rapide. Ici, le fait que généralement déjà comparant le premier octet des données a été suffisant pour conduire à la prochaine brecherche itération (comme les données utilisées pour être très différente de la première un à deux octets déjà) s'est avéré comme un grand avantage.

Donc, pour résumer: je voudrais prendre un décent algorithme de hachage, qui ne cause pas trop de collisions en moyenne, et est assez rapide (j'irais même jusqu'à accepter certaines collisions plus, si c'est juste très rapide!) et plutôt optimiser mon code de façon à obtenir la plus petite de la performance une fois que les accidents ne se produisent (et ils le feront! Ils seront à moins que votre espace de hachage est au moins égal ou plus grand que votre espace de données et vous pouvez associer une unique valeur de hachage pour chaque ensemble de données).

Answer 2

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:

• Depuis les articles que vous êtes en utilisant comme entrée pour le hachage sont juste un ensemble de chaînes de caractères, il vous suffit de combiner les hashcodes pour chacun de ces chaînes. J'ai vu le pseudo-code proposé de faire cela, mais je ne sais pas du tout particulier à l'analyse 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 hashcodes à l'aide de

  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 d'autre, vous vous retrouvez avec une collision si les mêmes chaînes sont hachés dans un ordre différent.

• J'ai utilisé de la FNV à bon escient: http://www.isthe.com/chongo/tech/comp/fnv/

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

• Un autre bel article de Bob Jenkins, qui a été initialement publié en 1997, Médecin Dobb's Journal (l'article lié a des mises à jour): http://burtleburtle.net/bob/hash/doobs.html

Answer 3

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 permettant d'obtenir un taux de 100% sur cet ensemble d'entrées particulier. Sinon, il n'y a pas de réponse «juste» à cette question.

Answer 4

Je vais être boiteux ici et de donner une réponse théorique plutôt une pin-pointage de réponse, mais merci de prendre de la valeur.

D'abord il y a deux problèmes distincts :

un. La probabilité de Collision b. La Performance de hachage (c'est à dire: le temps, la cpu cycles, etc.)

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

Problème de traite de la différence entre le hashee et les espaces de hachage. Lorsque vous hachage d'un fichier de 1 ko (1024 octets) du fichier et la valeur de hachage a 32 octets, il y aura :

1,0907481356194159294629842447338 e+2466 (c'est à dire un nombre avec 2466 zéros) les combinaisons possibles des fichiers d'entrée

et le hachage de l'espace

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 particulier lorsque deux fichiers d'entrée auront exactement le même hash), puisque nous sommes réduction de 10^2466 cas à 10^77 cas.

La seule façon de minimiser le risque de collision est pour agrandir le hachage de l'espace et, par conséquent, de faire de la hah plus. Idéalement, la valeur de hachage aura la longueur du fichier, mais c'est en quelque sorte débile.

---

Le deuxième problème est la performance. Cela ne traite qu'avec l'algorithme de hachage. Bien sûr qu'un plus hachage sera plus que probablement besoin de plus de cycles de processeur, mais un algorithme plus intelligent peut-être pas. J'ai pas vraiment de réponse à cette question. C'est tout simplement trop difficile.

Cependant, vous pouvez l'évaluer/mesurer les différentes implémentations de hachage et de tirage de pré-conclusions de cette.

Bonne chance ;)

Answer 5

Le simple hashCode utilisé par la classe String de Java peut indiquer un algorithme approprié.

Vous trouverez ci-dessous 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;
  }