Performances de HashSet vs. List

406

Il est clair que les performances de recherche de la HashSet<T>classe générique sont supérieures à celles de la List<T>classe générique . Il suffit de comparer la clé basée sur le hachage avec l'approche linéaire dans leList<T> classe.

Cependant, le calcul d'une clé de hachage peut lui-même prendre quelques cycles de processeur, donc pour une petite quantité d'éléments, la recherche linéaire peut être une véritable alternative à la HashSet<T> .

Ma question: où est le seuil de rentabilité?

Pour simplifier le scénario (et pour être juste) supposons que la List<T>classe utilise la Equals()méthode de l'élément pour identifier un élément.

Michael Damatov
la source
7
Si vous voulez vraiment réduire le temps de recherche, pensez également aux tableaux et aux tableaux triés. Pour répondre correctement à cette question, un benchmark est nécessaire, mais vous devez nous en dire plus sur T. De plus, les performances de HashSet peuvent être affectées par le temps d'exécution de T.GetHashCode ().
Eldritch Conundrum

Réponses:

821

Beaucoup de gens disent qu'une fois que vous atteignez la taille où la vitesse est en fait une préoccupation qui HashSet<T>battra toujours List<T>, mais cela dépend de ce que vous faites.

Disons que vous en avez un List<T>qui ne comportera en moyenne que 5 articles. Sur un grand nombre de cycles, si un seul élément est ajouté ou supprimé à chaque cycle, il est préférable d’utiliser a List<T>.

J'ai fait un test pour cela sur ma machine, et, bien, il doit être très très petit pour en tirer un avantage List<T>. Pour une liste de chaînes courtes, l'avantage a disparu après la taille 5, pour les objets après la taille 20.

1 item LIST strs time: 617ms
1 item HASHSET strs time: 1332ms

2 item LIST strs time: 781ms
2 item HASHSET strs time: 1354ms

3 item LIST strs time: 950ms
3 item HASHSET strs time: 1405ms

4 item LIST strs time: 1126ms
4 item HASHSET strs time: 1441ms

5 item LIST strs time: 1370ms
5 item HASHSET strs time: 1452ms

6 item LIST strs time: 1481ms
6 item HASHSET strs time: 1418ms

7 item LIST strs time: 1581ms
7 item HASHSET strs time: 1464ms

8 item LIST strs time: 1726ms
8 item HASHSET strs time: 1398ms

9 item LIST strs time: 1901ms
9 item HASHSET strs time: 1433ms

1 item LIST objs time: 614ms
1 item HASHSET objs time: 1993ms

4 item LIST objs time: 837ms
4 item HASHSET objs time: 1914ms

7 item LIST objs time: 1070ms
7 item HASHSET objs time: 1900ms

10 item LIST objs time: 1267ms
10 item HASHSET objs time: 1904ms

13 item LIST objs time: 1494ms
13 item HASHSET objs time: 1893ms

16 item LIST objs time: 1695ms
16 item HASHSET objs time: 1879ms

19 item LIST objs time: 1902ms
19 item HASHSET objs time: 1950ms

22 item LIST objs time: 2136ms
22 item HASHSET objs time: 1893ms

25 item LIST objs time: 2357ms
25 item HASHSET objs time: 1826ms

28 item LIST objs time: 2555ms
28 item HASHSET objs time: 1865ms

31 item LIST objs time: 2755ms
31 item HASHSET objs time: 1963ms

34 item LIST objs time: 3025ms
34 item HASHSET objs time: 1874ms

37 item LIST objs time: 3195ms
37 item HASHSET objs time: 1958ms

40 item LIST objs time: 3401ms
40 item HASHSET objs time: 1855ms

43 item LIST objs time: 3618ms
43 item HASHSET objs time: 1869ms

46 item LIST objs time: 3883ms
46 item HASHSET objs time: 2046ms

49 item LIST objs time: 4218ms
49 item HASHSET objs time: 1873ms

Voici ces données affichées sous forme de graphique:

entrez la description de l'image ici

Voici le code:

static void Main(string[] args)
{
    int times = 10000000;


    for (int listSize = 1; listSize < 10; listSize++)
    {
        List<string> list = new List<string>();
        HashSet<string> hashset = new HashSet<string>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add("string" + i.ToString());
            hashset.Add("string" + i.ToString());
        }

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove("string0");
            list.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");


        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove("string0");
            hashset.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }


    for (int listSize = 1; listSize < 50; listSize+=3)
    {
        List<object> list = new List<object>();
        HashSet<object> hashset = new HashSet<object>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add(new object());
            hashset.Add(new object());
        }

        object objToAddRem = list[0];

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove(objToAddRem);
            list.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");



        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove(objToAddRem);
            hashset.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }

    Console.ReadLine();
}
innominate227
la source
8
Merci beaucoup! C'est une excellente explication, je cherchais quelque chose qui pourrait être ajouté et supprimé plus rapidement qu'un List<T>moteur de jeu, et comme j'ai généralement un volume élevé d'objets, ce genre de collection serait parfait.
redcodefinal
17
Il existe en fait une collection dans le framework .NET qui bascule entre une liste et une implémentation hastable en fonction du nombre d'éléments qu'il contient: HybridDictionary .
MgSam
8
MS semble avoir abandonné sa pensée, car il ne dispose que d'une version non générique.
MgSam
47
Aussi complète que soit cette réponse, elle ne répond pas à la question d'origine concernant les performances de recherche liste vs hashset. Vous testez la vitesse à laquelle vous pouvez les insérer et les supprimer, ce qui prend beaucoup plus de temps et des caractéristiques de performances différentes que la recherche. Réessayez, en utilisant .Contains, et votre graphique changera considérablement.
Robert McKee
5
@hypehuman, le processeur ne peut pas travailler directement sur les données de la mémoire système, mais extrait les données de la mémoire dans son cache pour y travailler. Il y a un délai important entre la demande de mémoire à déplacer et la mémoire qui arrive réellement, de sorte que le CPU demandera souvent un plus grand morceau de mémoire contiguë à déplacer à la fois. L'idée derrière cela est que la mémoire nécessaire à l'instruction suivante est probablement très proche de la mémoire utilisée par l'instruction précédente et est donc souvent déjà dans le cache. Lorsque vos données sont dispersées dans la mémoire, les chances de chance sont réduites.
Roy T.
70

Vous regardez mal. Oui, une recherche linéaire d'une liste battra un HashSet pour un petit nombre d'éléments. Mais la différence de performances n'a généralement pas d'importance pour les collections aussi petites. Ce sont généralement les grandes collections dont vous devez vous soucier, et c'est là que vous pensez en termes de Big-O . Cependant, si vous avez mesuré un véritable goulot d'étranglement sur les performances de HashSet, vous pouvez essayer de créer une liste hybride / HashSet, mais vous le ferez en effectuant de nombreux tests de performances empiriques - sans poser de questions sur SO.

Eloff
la source
5
de grandes collections dont vous devez vous soucier . On peut redéfinir cette question en termes de when small collection becomes large enough to worry about HashSet vs List?dizaines, dizaines de milliers, milliards d'éléments?
om-nom-nom le
8
Non, vous verrez une différence de performances considérable au-dessus de quelques centaines d'éléments. Le point est toujours d'utiliser un HashSet si vous faites les types d'accès auxquels HashSet est bon (par exemple, l'élément X dans l'ensemble.) Si votre collection est si petite qu'une liste est plus rapide, il est très rare que ces recherches sont en fait un goulot d'étranglement dans votre application. Si vous pouvez le mesurer, vous pouvez essayer de l'optimiser, mais sinon vous perdez votre temps.
Eloff
15
Et si vous avez une petite collection qui est frappée plusieurs fois en boucle? Ce n'est pas un scénario rare.
dan-gph
3
@ om-nom-nom - Je pense que le fait est que peu importe où se situe le point de basculement, car: "Si les performances sont un souci, utilisez HashSet<T> . Dans les cas en petit nombre où cela List<T>pourrait être plus rapide, la différence est insignifiante . "
Scott Smith
66

Il est essentiellement inutile de comparer deux structures de performances qui se comportent différemment. Utilisez la structure qui exprime l'intention. Même si vous dites que vous List<T>n'auriez pas de doublons et que l'ordre d'itération n'a pas d'importance ce qui le rend comparable à un HashSet<T>, c'est toujours un mauvais choix à utiliserList<T> car il est relativement moins tolérant aux pannes.

Cela dit, je vais inspecter certains autres aspects de la performance,

+------------+--------+-------------+-----------+----------+----------+-----------+
| Collection | Random | Containment | Insertion | Addition |  Removal | Memory    |
|            | access |             |           |          |          |           |
+------------+--------+-------------+-----------+----------+----------+-----------+
| List<T>    | O(1)   | O(n)        | O(n)      | O(1)*    | O(n)     | Lesser    |
| HashSet<T> | O(n)   | O(1)        | n/a       | O(1)     | O(1)     | Greater** |
+------------+--------+-------------+-----------+----------+----------+-----------+
  • Même si l'addition est O (1) dans les deux cas, elle sera relativement plus lente dans HashSet car elle implique des coûts de précalcul du code de hachage avant de le stocker.

  • L'évolutivité supérieure de HashSet a un coût de mémoire. Chaque entrée est stockée en tant que nouvel objet avec son code de hachage. Cet article pourrait vous donner une idée.

nawfal
la source
11
Ma question (il y a six ans) ne concernait pas la performance théorique .
Michael Damatov
1
HashSet permet un accès aléatoire avec ElementAt (), et je pense que ce serait le temps O (n). En outre, vous pouvez peut-être indiquer dans votre tableau si chaque collection autorise les doublons (par exemple, les listes le font, mais les hashsets ne le permettent pas).
Dan W
1
@DanW dans le tableau, je compare uniquement les performances, pas les caractéristiques comportementales. Merci pour le conseil ElementAt.
nawfal
1
ElementAt est juste une extension LINQ .. il ne fait rien que vous ne pouvez pas faire et optimise mieux dans une autre méthode que vous ajoutez vous-même. Je pense que le tableau était plus logique sans considérer ElementAt puisque toutes les autres méthodes existent explicitement sur ces classes.
Dinerdo
1
Merci pour ce tableau, dans mon cas d'utilisation, je dois ajouter et supprimer des cibles à une collection remplie chaque fois qu'elles sont activées / désactivées et cela m'a aidé à faire le bon choix (HashSet).
Casey Hofland
50

Que ce soit pour utiliser un HashSet <> ou une liste <> se résume à la façon dont vous devez accéder à votre collection . Si vous devez garantir l'ordre des articles, utilisez une liste. Si vous ne le faites pas, utilisez un HashSet. Laissez Microsoft s'inquiéter de la mise en œuvre de leurs algorithmes et objets de hachage.

Un HashSet accédera aux éléments sans avoir à énumérer la collection (complexité de O (1) ou à proximité), et parce qu'une Liste garantit l'ordre, contrairement à un HashSet, certains éléments devront être énumérés (complexité de O (n)).

coeur
la source
La liste peut potentiellement calculer le décalage de l'élément spécifique par son index (car tous les éléments sont du même type et occupent potentiellement la même taille de mémoire). Donc, la liste n'est pas nécessaire énumère ses éléments
Lu55
@ Lu55 - La question concerne la recherche d'un article dans une collection. Un scénario typique est que la collection est dynamique - des éléments peuvent avoir été ajoutés ou supprimés depuis la dernière fois que vous avez cherché un élément donné - donc un index n'a pas de sens (car il aura changé). Si vous avez une collection statique (qui ne changera pas pendant que vous effectuez vos calculs), ou si les éléments ne sont jamais supprimés et sont toujours ajoutés à la fin, alors a Listest préférable, car vous pouvez vous souvenir d'un index - c'est la situation que vous décrivent.
ToolmakerSteve
Vous pouvez utiliser un SortedSet si vous devez trier un HashSet. Encore beaucoup plus rapide qu'une liste.
live-love
25

Je pensais juste que je ferais sonner quelques repères pour différents scénarios pour illustrer les réponses précédentes:

  1. Quelques (12 - 20) petites chaînes (longueur comprise entre 5 et 10 caractères)
  2. Beaucoup (~ 10K) de petites cordes
  3. Quelques longues chaînes (longueur entre 200 et 1000 caractères)
  4. Nombreuses (~ 5K) longues cordes
  5. Quelques entiers
  6. Beaucoup (~ 10 K) entiers

Et pour chaque scénario, recherche des valeurs qui apparaissent:

  1. Au début de la liste ("start", index 0)
  2. Vers le début de la liste ("tôt", index 1)
  3. Au milieu de la liste ("milieu", nombre d'index / 2)
  4. Vers la fin de la liste ("en retard", nombre d'index-2)
  5. À la fin de la liste ("end", index count-1)

Avant chaque scénario, j'ai généré des listes de chaînes aléatoires de taille aléatoire, puis j'ai alimenté chaque liste en un hachage. Chaque scénario s'est exécuté 10 000 fois, essentiellement:

(test du pseudocode)

stopwatch.start
for X times
    exists = list.Contains(lookup);
stopwatch.stop

stopwatch.start
for X times
    exists = hashset.Contains(lookup);
stopwatch.stop

Exemple de sortie

Testé sur Windows 7, 12 Go de RAM, 64 bits, Xeon 2,8 GHz

---------- Testing few small strings ------------
Sample items: (16 total)
vgnwaloqf diwfpxbv tdcdc grfch icsjwk
...

Benchmarks:
1: hashset: late -- 100.00 % -- [Elapsed: 0.0018398 sec]
2: hashset: middle -- 104.19 % -- [Elapsed: 0.0019169 sec]
3: hashset: end -- 108.21 % -- [Elapsed: 0.0019908 sec]
4: list: early -- 144.62 % -- [Elapsed: 0.0026607 sec]
5: hashset: start -- 174.32 % -- [Elapsed: 0.0032071 sec]
6: list: middle -- 187.72 % -- [Elapsed: 0.0034536 sec]
7: list: late -- 192.66 % -- [Elapsed: 0.0035446 sec]
8: list: end -- 215.42 % -- [Elapsed: 0.0039633 sec]
9: hashset: early -- 217.95 % -- [Elapsed: 0.0040098 sec]
10: list: start -- 576.55 % -- [Elapsed: 0.0106073 sec]


---------- Testing many small strings ------------
Sample items: (10346 total)
dmnowa yshtrxorj vthjk okrxegip vwpoltck
...

Benchmarks:
1: hashset: end -- 100.00 % -- [Elapsed: 0.0017443 sec]
2: hashset: late -- 102.91 % -- [Elapsed: 0.0017951 sec]
3: hashset: middle -- 106.23 % -- [Elapsed: 0.0018529 sec]
4: list: early -- 107.49 % -- [Elapsed: 0.0018749 sec]
5: list: start -- 126.23 % -- [Elapsed: 0.0022018 sec]
6: hashset: early -- 134.11 % -- [Elapsed: 0.0023393 sec]
7: hashset: start -- 372.09 % -- [Elapsed: 0.0064903 sec]
8: list: middle -- 48,593.79 % -- [Elapsed: 0.8476214 sec]
9: list: end -- 99,020.73 % -- [Elapsed: 1.7272186 sec]
10: list: late -- 99,089.36 % -- [Elapsed: 1.7284155 sec]


---------- Testing few long strings ------------
Sample items: (19 total)
hidfymjyjtffcjmlcaoivbylakmqgoiowbgxpyhnrreodxyleehkhsofjqenyrrtlphbcnvdrbqdvji...
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0018266 sec]
2: list: start -- 115.76 % -- [Elapsed: 0.0021144 sec]
3: list: middle -- 143.44 % -- [Elapsed: 0.0026201 sec]
4: list: late -- 190.05 % -- [Elapsed: 0.0034715 sec]
5: list: end -- 193.78 % -- [Elapsed: 0.0035395 sec]
6: hashset: early -- 215.00 % -- [Elapsed: 0.0039271 sec]
7: hashset: end -- 248.47 % -- [Elapsed: 0.0045386 sec]
8: hashset: start -- 298.04 % -- [Elapsed: 0.005444 sec]
9: hashset: middle -- 325.63 % -- [Elapsed: 0.005948 sec]
10: hashset: late -- 431.62 % -- [Elapsed: 0.0078839 sec]


---------- Testing many long strings ------------
Sample items: (5000 total)
yrpjccgxjbketcpmnvyqvghhlnjblhgimybdygumtijtrwaromwrajlsjhxoselbucqualmhbmwnvnpnm
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: list: start -- 132.73 % -- [Elapsed: 0.0021517 sec]
3: hashset: start -- 231.26 % -- [Elapsed: 0.003749 sec]
4: hashset: end -- 368.74 % -- [Elapsed: 0.0059776 sec]
5: hashset: middle -- 385.50 % -- [Elapsed: 0.0062493 sec]
6: hashset: late -- 406.23 % -- [Elapsed: 0.0065854 sec]
7: hashset: early -- 421.34 % -- [Elapsed: 0.0068304 sec]
8: list: middle -- 18,619.12 % -- [Elapsed: 0.3018345 sec]
9: list: end -- 40,942.82 % -- [Elapsed: 0.663724 sec]
10: list: late -- 41,188.19 % -- [Elapsed: 0.6677017 sec]


---------- Testing few ints ------------
Sample items: (16 total)
7266092 60668895 159021363 216428460 28007724
...

Benchmarks:
1: hashset: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: hashset: end -- 100.45 % -- [Elapsed: 0.0016284 sec]
3: list: early -- 101.83 % -- [Elapsed: 0.0016507 sec]
4: hashset: late -- 108.95 % -- [Elapsed: 0.0017662 sec]
5: hashset: middle -- 112.29 % -- [Elapsed: 0.0018204 sec]
6: hashset: start -- 120.33 % -- [Elapsed: 0.0019506 sec]
7: list: late -- 134.45 % -- [Elapsed: 0.0021795 sec]
8: list: start -- 136.43 % -- [Elapsed: 0.0022117 sec]
9: list: end -- 169.77 % -- [Elapsed: 0.0027522 sec]
10: list: middle -- 237.94 % -- [Elapsed: 0.0038573 sec]


---------- Testing many ints ------------
Sample items: (10357 total)
370826556 569127161 101235820 792075135 270823009
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0015132 sec]
2: hashset: end -- 101.79 % -- [Elapsed: 0.0015403 sec]
3: hashset: early -- 102.08 % -- [Elapsed: 0.0015446 sec]
4: hashset: middle -- 103.21 % -- [Elapsed: 0.0015618 sec]
5: hashset: late -- 104.26 % -- [Elapsed: 0.0015776 sec]
6: list: start -- 126.78 % -- [Elapsed: 0.0019184 sec]
7: hashset: start -- 130.91 % -- [Elapsed: 0.0019809 sec]
8: list: middle -- 16,497.89 % -- [Elapsed: 0.2496461 sec]
9: list: end -- 32,715.52 % -- [Elapsed: 0.4950512 sec]
10: list: late -- 33,698.87 % -- [Elapsed: 0.5099313 sec]
drzaus
la source
7
Intéressant. Merci d'avoir exécuté cela. Malheureusement, je soupçonne que ces discussions déclenchent des restructurations inutiles. Avec un peu de chance, la plupart des gens retiennent que dans votre pire scénario absolu, il Listne faut que 0,17 millisecondes pour effectuer une seule recherche et ne nécessitera probablement pas de substitution HashSetjusqu'à ce que la fréquence de recherche atteigne des niveaux absurdes. D'ici là, l'utilisation de List est généralement le moindre des problèmes.
Paul Walls
Ce ne sont pas des informations réelles pour l'instant .. Ou peut-être que c'est faux à l'origine ... J'ai juste vérifié les petites valeurs de 2 à 8 caractères. List / HashSet ont été créés pour chaque 10 valeurs ... HashSet plus lent pour 30% ... Si la capacité dans List est utilisée, la différence est même de ~ 40%. HashSet devient plus rapide pour 10% seulement si nous listons est sans capacité spécifiée et vérifie chaque valeur avant d'ajouter à travers la liste entière.
Maxim
Si le nombre d'objets est réduit à 4, alors List revient à nouveau, même dans le pire des cas (avec une différence de 10%). Je ne recommande donc pas d'utiliser HashSet pour une petite collection de chaînes (disons <20). Et c'est ce qui est différent de vos "quelques petits" tests.
Maxim
1
@Maxim ne peut pas vraiment dire que mes résultats sont "faux" - c'est ce qui s'est passé sur ma machine. YMMV. En fait, je les ai à nouveau exécutés ( gist.github.com/zaus/014ac9b5a78b267aa1643d63d30c7554 ) sur un nouvel ordinateur SSD Win10 4,0 GHz 16 Go et j'ai obtenu des résultats similaires. La conclusion que je vois est que les performances de hachage étaient plus cohérentes, peu importe où se trouvait la clé de recherche ou la taille de la liste, tandis que les performances de la liste variaient énormément de meilleures à plus de 300 fois plus lentement. Mais comme PaulWalls l'a initialement indiqué, nous parlons de # micro-optimisation sérieuse.
drzaus
@Maxim pour référence: dotnetfiddle.net/5taRDd - n'hésitez pas à jouer avec.
drzaus
10

Le seuil de rentabilité dépendra du coût de calcul du hachage. Les calculs de hachage peuvent être triviaux, ou non ... :-) Il y a toujours la classe System.Collections.Specialized.HybridDictionary pour vous aider à ne pas avoir à vous soucier du seuil de rentabilité.

Walden Leverich
la source
1
Vous devez également prendre en compte le coût d'une comparaison. Dans le cas de Contains (T), le HashSet fera une comparaison pour vérifier qu'il n'a pas de collision Hash vers la liste faisant une comparaison sur chaque élément qu'il regarde avant de trouver le bon. Vous devez également prendre en compte la distribution des hachages générés par T.GetHashCode () comme si cela renvoyait toujours la même valeur que vous faites essentiellement HashSet faire la même chose que List.
Martin Brown
6

La réponse, comme toujours, est " Cela dépend ". Je suppose que les balises dont vous parlez C #.

Votre meilleur pari est de déterminer

  1. Un ensemble de données
  2. Conditions d'utilisation

et écrire quelques cas de test.

Cela dépend également de la façon dont vous triez la liste (si elle est triée), du type de comparaison à effectuer, de la durée de l'opération "Comparer" pour l'objet particulier de la liste, ou même de la manière dont vous avez l'intention d'utiliser le collection.

Généralement, le meilleur choix n'est pas tellement basé sur la taille des données avec lesquelles vous travaillez, mais plutôt sur la façon dont vous avez l'intention d'y accéder. Avez-vous chaque élément de données associé à une chaîne particulière ou à d'autres données? Une collection basée sur le hachage serait probablement la meilleure. L'ordre des données que vous stockez est-il important, ou allez-vous avoir besoin d'accéder à toutes les données en même temps? Une liste régulière peut alors être meilleure.

Additionnel:

Bien sûr, mes commentaires ci-dessus supposent que «performance» signifie l'accès aux données. Autre chose à considérer: que recherchez-vous lorsque vous dites "performance"? La performance de la valeur individuelle est-elle recherchée? S'agit-il de la gestion de grands ensembles de valeurs (10000, 100000 ou plus)? Est-ce la performance de remplir la structure de données avec des données? Supprimer des données? Accéder à des bits de données individuels? Remplacement des valeurs? Itérer sur les valeurs? Utilisation de la mémoire? Vitesse de copie des données? Par exemple, si vous accédez aux données par une valeur de chaîne, mais que votre principale exigence de performances est une utilisation minimale de la mémoire, vous pouvez rencontrer des problèmes de conception conflictuels.

Robert P
la source
5

Vous pouvez utiliser un HybridDictionary qui détecte automatiquement le point de rupture et accepte les valeurs nulles, ce qui le rend essentiellement identique à un HashSet.

Muis
la source
1
A voté pour cette idée, mais personne ne l'utilisera jamais aujourd'hui. Dites non aux non génériques. Un dictionnaire est également un mappage de valeurs-clés, l'ensemble ne l'est pas.
nawfal
4

Ça dépend. Si la réponse exacte est vraiment importante, faites un profilage et découvrez. Si vous êtes sûr que vous n'aurez jamais plus d'un certain nombre d'éléments dans l'ensemble, optez pour une liste. Si le nombre est illimité, utilisez un HashSet.

Adam Rosenfield
la source
3

Cela dépend de ce que vous hachez. Si vos clés sont des entiers, vous n'avez probablement pas besoin de beaucoup d'éléments avant que le HashSet ne soit plus rapide. Si vous le saisissez sur une chaîne, il sera plus lent et dépend de la chaîne d'entrée.

Vous pourriez sûrement concocter assez facilement une référence?

Peter
la source
3

Un facteur que vous ne prenez pas en compte est la robustesse de la fonction GetHashcode (). Avec une fonction de hachage parfaite, le HashSet aura clairement de meilleures performances de recherche. Mais à mesure que la fonction de hachage diminue, le temps de recherche du HashSet diminue également.

JaredPar
la source
0

Dépend de beaucoup de facteurs ... Implémentation de la liste, architecture CPU, JVM, sémantique de boucle, complexité de la méthode des égaux, etc. les recherches battent haut et bas les recherches linéaires, et la différence ne fait que s'aggraver à partir de là.

J'espère que cela t'aides!

Kyle
la source
1
JVM ... ou CLR :-)
bvgheluwe