Quel est le plus rapide, recherche de hachage ou recherche binary?

Quand on donne un ensemble d’objects statiques (statiques dans le sens où ils ont été chargés une fois, voire jamais), dans lesquels des recherches simultanées répétées sont nécessaires avec des performances optimales, un HashMap ou un tableau avec une recherche binary avec un comparateur personnalisé?

La réponse est-elle une fonction de type object ou struct? Performances de hachage et / ou de fonction égale? Hash unicité? Taille de la liste? Hashset taille / taille du jeu?

La taille de l’ensemble que je cherche peut être comprise entre 500k et 10m – si cette information est utile.

Pendant que je cherche une réponse C #, je pense que la vraie réponse mathématique ne réside pas dans le langage, donc je n’inclus pas cette balise. Cependant, s’il existe des éléments spécifiques à C #, ces informations sont souhaitables.

Ok, je vais essayer d’être bref.

C # réponse courte:

Testez les deux approches différentes.

.NET vous donne les outils pour changer votre approche avec une ligne de code. Sinon, utilisez System.Collections.Generic.Dictionary et assurez-vous de l’initialiser avec un grand nombre comme capacité initiale ou vous passerez le rest de votre vie à insérer des éléments en raison du travail que GC doit effectuer pour collecter les anciennes baies.

Réponse plus longue:

Une table de hachage a des temps de recherche constants ALMOST et l’access à un élément dans une table de hachage dans le monde réel ne nécessite pas seulement de calculer un hachage.

Pour accéder à un élément, votre table de hachage fera quelque chose comme ceci:

  • Obtenez le hash de la clé
  • Obtenez le numéro de compartiment pour ce hachage (en général, la fonction de carte ressemble à ce compartiment = hash% bucketsCount)
  • Traverse la chaîne d’éléments (en gros, c’est une liste d’éléments qui partagent le même compartiment, la plupart des hashtables utilisent cette méthode pour gérer les collisions entre bucket / hash) qui commence dans ce compartiment et compare chaque clé à celle de l’élément que vous essayez d’append / supprimer / mettre à jour / vérifier s’il est contenu.

Les temps de recherche dépendent de la qualité et de la rapidité de votre fonction de hachage, du nombre de compartiments que vous utilisez et de la rapidité de comparaison des clés. Ce n’est pas toujours la meilleure solution.

Une explication meilleure et plus approfondie: http://en.wikipedia.org/wiki/Hash_table

Pour les très petites collections, la différence sera négligeable. Au bas de la fourchette (500 000 éléments), vous commencerez à voir une différence si vous faites beaucoup de recherches. Une recherche binary va être O (log n), alors qu’une recherche de hachage sera O (1), amortie . Ce n’est pas la même chose que la constante, mais vous devrez quand même avoir une fonction de hachage assez terrible pour obtenir de meilleures performances qu’une recherche binary.

(Quand je dis “terrible hash”, je veux dire quelque chose comme:

 hashCode() { return 0; } 

Ouais, c’est rapide lui-même, mais provoque votre carte de hachage à devenir une liste liée.)

ialiashkevich a écrit du code C # en utilisant un tableau et un dictionnaire pour comparer les deux méthodes, mais il a utilisé des valeurs longues pour les clés. Je voulais tester quelque chose qui exécuterait une fonction de hachage pendant la recherche, j’ai donc modifié ce code. Je l’ai modifié pour utiliser les valeurs de chaîne, et j’ai refactorisé les sections de remplissage et de recherche dans leurs propres méthodes afin de faciliter leur visualisation dans un profileur. J’ai également laissé dans le code qui utilisait les valeurs longues, juste comme sharepoint comparaison. Enfin, je me suis débarrassé de la fonction de recherche binary personnalisée et j’ai utilisé celle de la classe Array .

Voici ce code:

 class Program { private const long capacity = 10_000_000; private static void Main(ssortingng[] args) { testLongValues(); Console.WriteLine(); testSsortingngValues(); Console.ReadLine(); } private static void testSsortingngValues() { Dictionary dict = new Dictionary(); Ssortingng[] arr = new Ssortingng[capacity]; Stopwatch stopwatch = new Stopwatch(); Console.WriteLine("" + capacity + " Ssortingng values..."); stopwatch.Start(); populateSsortingngArray(arr); stopwatch.Stop(); Console.WriteLine("Populate Ssortingng Array: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); populateSsortingngDictionary(dict, arr); stopwatch.Stop(); Console.WriteLine("Populate Ssortingng Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); Array.Sort(arr); stopwatch.Stop(); Console.WriteLine("Sort Ssortingng Array: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); searchSsortingngDictionary(dict, arr); stopwatch.Stop(); Console.WriteLine("Search Ssortingng Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); searchSsortingngArray(arr); stopwatch.Stop(); Console.WriteLine("Search Ssortingng Array: " + stopwatch.ElapsedMilliseconds); } /* Populate an array with random values. */ private static void populateSsortingngArray(Ssortingng[] arr) { for (long i = 0; i < capacity; i++) { arr[i] = generateRandomString(20) + i; // concatenate i to guarantee uniqueness } } /* Populate a dictionary with values from an array. */ private static void populateStringDictionary(Dictionary dict, Ssortingng[] arr) { for (long i = 0; i < capacity; i++) { dict.Add(arr[i], arr[i]); } } /* Search a Dictionary for each value in an array. */ private static void searchStringDictionary(Dictionary dict, Ssortingng[] arr) { for (long i = 0; i < capacity; i++) { String value = dict[arr[i]]; } } /* Do a binary search for each value in an array. */ private static void searchStringArray(String[] arr) { for (long i = 0; i < capacity; i++) { int index = Array.BinarySearch(arr, arr[i]); } } private static void testLongValues() { Dictionary dict = new Dictionary(Int16.MaxValue); long[] arr = new long[capacity]; Stopwatch stopwatch = new Stopwatch(); Console.WriteLine("" + capacity + " Long values..."); stopwatch.Start(); populateLongDictionary(dict); stopwatch.Stop(); Console.WriteLine("Populate Long Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); populateLongArray(arr); stopwatch.Stop(); Console.WriteLine("Populate Long Array: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); searchLongDictionary(dict); stopwatch.Stop(); Console.WriteLine("Search Long Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); searchLongArray(arr); stopwatch.Stop(); Console.WriteLine("Search Long Array: " + stopwatch.ElapsedMilliseconds); } /* Populate an array with long values. */ private static void populateLongArray(long[] arr) { for (long i = 0; i < capacity; i++) { arr[i] = i; } } /* Populate a dictionary with long key/value pairs. */ private static void populateLongDictionary(Dictionary dict) { for (long i = 0; i < capacity; i++) { dict.Add(i, i); } } /* Search a Dictionary for each value in a range. */ private static void searchLongDictionary(Dictionary dict) { for (long i = 0; i < capacity; i++) { long value = dict[i]; } } /* Do a binary search for each value in an array. */ private static void searchLongArray(long[] arr) { for (long i = 0; i < capacity; i++) { int index = Array.BinarySearch(arr, arr[i]); } } /** * Generate a random string of a given length. * Implementation from https://stackoverflow.com/a/1344258/1288 */ private static String generateRandomString(int length) { var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; var stringChars = new char[length]; var random = new Random(); for (int i = 0; i < stringChars.Length; i++) { stringChars[i] = chars[random.Next(chars.Length)]; } return new String(stringChars); } } 

Voici les résultats avec plusieurs tailles de collections différentes. (Les temps sont en millisecondes.)

500000 valeurs longues ...
Populate Long Dictionary: 26
Remplir Long Array: 2
Recherche Dictionnaire long: 9
Rechercher Long tableau: 80

500000 Valeurs de chaîne ...
Populate Ssortingng Array: 1237
Populate Ssortingng Dictionary: 46
Sort Ssortingng Array: 1755
Dictionnaire de recherche: 27
Recherche dans un tableau: 1569

1000000 Longues valeurs ...
Populate Long Dictionary: 58
Peuplé Long Array: 5
Recherche Dictionnaire long: 23
Rechercher Long tableau: 136

1000000 Valeur de chaîne ...
Populate Ssortingng Array: 2070
Populate Ssortingng Dictionary: 121
Sort Ssortingng Array: 3579
Dictionnaire de recherche: 58
Tableau de recherche: 3267

3000000 Long valeurs ...
Populate Long Dictionary: 207
Remplir Long Array: 14
Recherche Dictionnaire long: 75
Recherche longue série: 435

3000000 Valeurs de chaîne ...
Populate Ssortingng Array: 5553
Populate Ssortingng Dictionary: 449
Sort Ssortingng Array: 11695
Dictionnaire de recherche: 194
Recherche dans un tableau: 10594

10000000 Longues valeurs ...
Populate Long Dictionary: 521
Remplir Long Array: 47
Recherche Dictionnaire long: 202
Recherche longue série: 1181

10000000 Valeurs de chaîne ...
Populate Ssortingng Array: 18119
Populate Ssortingng Dictionary: 1088
Sort Ssortingng Array: 28174
Dictionnaire de recherche: 747
Recherche dans un tableau: 26503

Et à titre de comparaison, voici la sortie du profileur pour la dernière exécution du programme (10 millions d'enregistrements et de recherches). J'ai mis en évidence les fonctions pertinentes. Ils sont tout à fait d'accord avec les parameters de chronométrage de chronomètre ci-dessus.

Sortie du profileur pour 10 millions d'enregistrements et de recherches

Vous pouvez voir que les recherches dans le dictionnaire sont beaucoup plus rapides que la recherche binary et (comme prévu) la différence est plus prononcée plus la collection est grande. Donc, si vous avez une fonction de hachage raisonnable (assez rapide avec peu de collisions), une recherche de hachage devrait battre la recherche binary pour les collections de cette plage.

Les réponses de Bobby, Bill et Corbin sont fausses. O (1) n’est pas plus lent que O (log n) pour un n fixe / borné:

log (n) est constant, donc il dépend du temps constant.

Et pour une fonction de hachage lente, avez-vous déjà entendu parler de md5?

L’algorithme de hachage de chaîne par défaut touche probablement tous les caractères et peut facilement être 100 fois plus lent que la moyenne des clés longues. Été là, fait ça.

Vous pourriez être en mesure d’utiliser (partiellement) une base. Si vous pouvez diviser en 256 blocs de taille approximativement identique, vous recherchez une recherche binary de 2k à 40k. Cela est susceptible de fournir de bien meilleures performances.

[Edit] Trop de gens votent contre ce qu’ils ne comprennent pas.

Les comparaisons de chaînes pour la recherche binary des ensembles sortingés ont une propriété très intéressante: elles sont plus lentes à mesure qu’elles se rapprochent de la cible. D’abord, ils vont casser le premier caractère, à la fin seulement le dernier. En supposant qu’un temps constant pour eux est incorrect.

La seule réponse raisonnable à cette question est: cela dépend. Cela dépend de la taille de vos données, de la forme de vos données, de votre implémentation de hachage, de votre implémentation de recherche binary et de l’emplacement de vos données (même si cela n’est pas mentionné dans la question). Quelques autres réponses en disent autant, alors je pourrais juste supprimer ceci. Cependant, il pourrait être intéressant de partager ce que j’ai appris des retours d’expérience avec ma réponse originale.

  1. J’ai écrit: « Les algorithmes de hachage sont O (1) alors que la recherche binary est O (log n). » – Comme noté dans les commentaires, la notation Big O estime la complexité et non la vitesse. C’est absolument vrai. Il convient de noter que nous utilisons généralement la complexité pour avoir une idée du temps et de l’espace requirejs par un algorithme. Ainsi, bien qu’il soit insensé de supposer que la complexité est ssortingctement la même que la vitesse, il est inhabituel d’estimer la complexité sans temps ou espace dans la tête. Ma recommandation: éviter la notation Big O.
  2. J’ai écrit: ” Alors que n s’approche de l’infini …” – Il s’agit de la chose la plus stupide que j’aurais pu inclure dans une réponse. L’infini n’a rien à voir avec votre problème. Vous mentionnez une limite supérieure de 10 millions. Ignorer l’infini. Comme les commentateurs le soulignent, de très grands nombres créeront toutes sortes de problèmes avec un hachage. (Les nombres très importants ne rendent pas non plus la recherche binary dans le parc.) Ma recommandation: ne mentionnez pas l’infini à moins que vous ne vouliez dire l’infini.
  3. Également à partir des commentaires: méfiez-vous des hachages de chaînes par défaut (vous êtes en train de hacher des chaînes? Vous ne mentionnez pas.), Les index de firebase database sont souvent des b-trees (matière à reflection). Ma recommandation: considérez toutes vos options. Considérons d’autres structures et approches de données … comme un sortinge à l’ ancienne (pour stocker et récupérer des chaînes) ou un arbre R (pour les données spatiales) ou un MA-FSA (automate à états finis acycliques minimaux – faible encombrement).

Compte tenu des commentaires, vous pouvez supposer que les personnes qui utilisent des tables de hachage sont dérangées. Les tables de hachage sont-elles imprudentes et dangereuses? Ces gens sont-ils fous?

Il s’avère qu’ils ne sont pas. Tout comme les arbres binarys sont bons pour certaines choses (traversée de données dans l’ordre, efficacité du stockage), les tables de hachage ont également leur heure de gloire. En particulier, ils peuvent très bien réduire le nombre de lectures nécessaires pour récupérer vos données. Un algorithme de hachage peut générer un emplacement et y accéder directement dans la mémoire ou sur le disque, tandis que la recherche binary lit les données lors de chaque comparaison pour décider de la prochaine lecture. Chaque lecture a le potentiel pour un échec de cache qui est un ordre de grandeur (ou plus) plus lent qu’une instruction CPU.

Cela ne veut pas dire que les tables de hachage sont meilleures que la recherche binary. Ils ne sont pas. Il ne faut pas non plus suggérer que toutes les implémentations de hachage et de recherche binary sont les mêmes. Ils ne sont pas. Si j’ai un point, c’est ceci: les deux approches existent pour une raison. C’est à vous de décider lequel convient le mieux à vos besoins.

Réponse originale:


Les algorithmes de hachage sont O (1) alors que la recherche binary est O (log n). Alors que n s’approche de l’infini, les performances de hachage s’améliorent par rapport à la recherche binary. Votre kilométrage variera en fonction de votre implémentation de hachage et de votre implémentation de recherche binary.

Discussion intéressante sur O (1) . Paraphrasé:

O (1) ne signifie pas instantané. Cela signifie que la performance ne change pas à mesure que la taille de n augmente. Vous pouvez concevoir un algorithme de hachage si lent que personne ne l’utilisera jamais et qu’il s’agira toujours de O (1). Je suis presque certain que .NET / C # ne souffre pas d’un hachage à coût prohibitif;)

Si votre ensemble d’objects est vraiment statique et immuable, vous pouvez utiliser un hachage parfait pour garantir les performances de O (1). J’ai vu gperf mentionné à quelques resockets, mais je n’ai jamais eu l’occasion de l’utiliser moi-même.

Les hachages sont généralement plus rapides, bien que les recherches binarys présentent de meilleures caractéristiques dans le pire des cas. Un access de hachage est généralement un calcul permettant d’obtenir une valeur de hachage pour déterminer le “compartiment” dans lequel un enregistrement sera placé. La performance dépendra généralement de la répartition uniforme des enregistrements et de la méthode utilisée pour effectuer une recherche dans le compartiment. Une mauvaise fonction de hachage (laissant quelques compartiments contenant de nombreux enregistrements) avec une recherche linéaire dans les compartiments entraînera une recherche lente. (Troisièmement, si vous lisez un disque plutôt que de la mémoire, il est probable que les compartiments de hachage soient contigus alors que l’arbre binary garantit un access non local.)

Si vous voulez généralement rapide, utilisez le hachage. Si vous voulez vraiment des performances garanties, vous pouvez utiliser l’arbre binary.

Surpris, personne n’a mentionné le hachage de coucou, qui fournit un O (1) garanti et, contrairement au hachage parfait, est capable d’utiliser toute la mémoire qu’il alloue, où un hachage parfait peut se traduire par un O (1) garanti allocation. La mise en garde? Le temps d’insertion peut être très lent, d’autant plus que le nombre d’éléments augmente, puisque toute l’optimisation est effectuée pendant la phase d’insertion.

Je crois qu’une version de ceci est utilisée dans le matériel de routeur pour des recherches d’IP.

Voir le texte du lien

Dictionary / Hashtable utilise plus de mémoire et prend plus de temps pour remplir la comparaison avec le tableau. Mais la recherche est effectuée plus rapidement par Dictionary plutôt que par recherche binary dans array.

Voici les chiffres pour 10 millions d’éléments Int64 à rechercher et à renseigner. Plus un exemple de code que vous pouvez exécuter vous-même.

Mémoire du dictionnaire: 462 836

Mémoire de masortingce: 88,376

Populate Dictionary: 402

Populate Array: 23

Dictionnaire de recherche: 176

Masortingce de recherche: 680

 using System; using System.Collections.Generic; using System.Diagnostics; namespace BinaryVsDictionary { internal class Program { private const long Capacity = 10000000; private static readonly Dictionary Dict = new Dictionary(Int16.MaxValue); private static readonly long[] Arr = new long[Capacity]; private static void Main(ssortingng[] args) { Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); for (long i = 0; i < Capacity; i++) { Dict.Add(i, i); } stopwatch.Stop(); Console.WriteLine("Populate Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); for (long i = 0; i < Capacity; i++) { Arr[i] = i; } stopwatch.Stop(); Console.WriteLine("Populate Array: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); for (long i = 0; i < Capacity; i++) { long value = Dict[i]; // Console.WriteLine(value + " : " + RandomNumbers[i]); } stopwatch.Stop(); Console.WriteLine("Search Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); for (long i = 0; i < Capacity; i++) { long value = BinarySearch(Arr, 0, Capacity, i); // Console.WriteLine(value + " : " + RandomNumbers[i]); } stopwatch.Stop(); Console.WriteLine("Search Array: " + stopwatch.ElapsedMilliseconds); Console.ReadLine(); } private static long BinarySearch(long[] arr, long low, long hi, long value) { while (low <= hi) { long median = low + ((hi - low) >> 1); if (arr[median] == value) { return median; } if (arr[median] < value) { low = median + 1; } else { hi = median - 1; } } return ~low; } } } 

Je soupçonne fortement que dans un ensemble de problèmes de taille ~ 1M, le hachage serait plus rapide.

Juste pour les chiffres:

une recherche binary nécessiterait environ 20 comparaisons (2 ^ 20 == 1M)

une recherche de hachage nécessiterait 1 calcul de hachage sur la clé de recherche et, éventuellement, une poignée de comparaisons pour résoudre les collisions éventuelles

Modifier: les numéros:

  for (int i = 0; i < 1000 * 1000; i++) { c.GetHashCode(); } for (int i = 0; i < 1000 * 1000; i++) { for (int j = 0; j < 20; j++) c.CompareTo(d); } 

times: c = "abcde", d = "rwerij" hashcode: 0.0012 secondes. Comparer: 2,4 secondes.

clause de non-responsabilité: en fait, l'parsing comparative d'une recherche de hachage par rapport à une recherche binary pourrait être meilleure que ce test non entièrement pertinent. Je ne suis même pas sûr que GetHashCode soit mémorisé sous le capot

Je dirais que cela dépend principalement de la performance du hachage et des méthodes de comparaison. Par exemple, lorsque vous utilisez des clés de chaîne très longues mais aléatoires, une comparaison donnera toujours un résultat très rapide, mais une fonction de hachage par défaut traitera toute la chaîne.

Mais dans la plupart des cas, la carte de hachage devrait être plus rapide.

Je me demande pourquoi personne n’a mentionné le hachage parfait .

Ce n’est pertinent que si votre jeu de données est corrigé depuis longtemps, mais qu’est-ce qu’il fait, il parsing les données et construit une fonction de hachage parfaite qui ne garantit aucune collision.

Assez propre, si votre dataset est constant et que le temps de calcul de la fonction est faible par rapport à l’exécution de l’application.

Cela dépend de la façon dont vous gérez les doublons pour les tables de hachage (voire pas du tout). Si vous souhaitez autoriser les doublons de clé de hachage (aucune fonction de hachage n’est parfaite), il rest O (1) pour la recherche de clé primaire, mais la recherche de la valeur “droite” peut être coûteuse. La réponse est alors théoriquement la plupart du temps, les hachages sont plus rapides. YMMV en fonction des données que vous y avez mises …

Ici, il est décrit comment les hachages sont construits et parce que l’Univers des clés est assez grand et que les fonctions de hachage sont construites pour être “très injectives” afin que les collisions se produisent rarement, le temps d’access pour une table de hachage n’est pas O (1) quelque chose basé sur certaines probabilités. Mais, il est raisonnable de dire que le temps d’access d’un hachage est presque toujours inférieur au temps O (log_2 (n))

Bien sûr, le hachage est le plus rapide pour un tel dataset.

Une façon d’accélérer encore davantage, puisque les données changent rarement, consiste à générer par programmation du code ad hoc pour effectuer la première couche de recherche en tant que déclaration de changement géant (si votre compilateur peut le gérer), le seau résultant.

La réponse dépend. Disons que le nombre d’éléments ‘n’ est très grand. Si vous êtes doué pour écrire une meilleure fonction de hachage, ce qui est moins grave, le hachage est le meilleur. Notez que la fonction de hachage est en cours d’exécution une seule fois lors de la recherche et qu’elle est dirigée vers le compartiment correspondant. Donc, ce n’est pas un gros problème si n est élevé.
Problème dans Hashtable: Mais le problème dans les tables de hachage est que si la fonction de hachage n’est pas bonne (plus de collisions se produisent), alors la recherche n’est pas O (1). Il tend vers O (n) car la recherche dans un compartiment est une recherche linéaire. Peut être pire qu’un arbre binary. problème dans l’arbre binary: Dans l’arbre binary, si l’arbre n’est pas équilibré, il tend également vers O (n). Par exemple, si vous avez inséré 1,2,3,4,5 dans un arbre binary qui serait plus probablement une liste. Donc, si vous pouvez voir une bonne méthode de hachage, utilisez une table de hachage. Sinon, vous feriez mieux d’utiliser un arbre binary.