Pourquoi certaines structures de données de collecte ne maintiennent-elles pas l'ordre d'insertion ? Quelle est la particularité d'atteindre par rapport au maintien de l'ordre d'insertion? Gagnons-nous quelque chose si nous ne maintenons pas l'ordre?
Réponses
Trop de publicités?
La performance.
Si vous voulez l'ordre d'insertion d'origine, il y a les classes, qui maintiennent une liste liée supplémentaire dans l'ordre d'insertion. La plupart du temps, vous ne vous souciez pas, de sorte que vous utilisez un , ou vous voulez un ordre naturel, de sorte que vous utilisez `` . Dans l'un ou l'autre de ces cas, pourquoi devriez-vous payer le coût supplémentaire de la liste liée?
josefx
Points
8417
Les collections de ne pas maintenir l'ordre d'insertion. Certains juste valeur par défaut pour ajouter une nouvelle valeur à la fin. Le maintien de l'ordre d'insertion n'est utile que si l'ordre de priorité des objets par la ou les utiliser pour trier les objets d'une certaine façon.
Quant à savoir pourquoi certaines collections de la maintenir par défaut et d'autres ne le font pas, c'est principalement causée par la mise en œuvre et parfois seulement une partie des collections de la définition.
Les listes de maintenir l'ordre d'insertion que d'ajouter une nouvelle entrée à la fin ou le début est le plus rapide de la mise en œuvre du complément(d'Objet ) de la méthode.
Définit Le HashSet et TreeSet implémentations de ne pas maintenir l'ordre d'insertion comme les objets sont triés pour la recherche rapide et le maintien de l'ordre d'insertion aurait besoin de mémoire supplémentaire. Il en résulte un gain de performance depuis la commande d'insertion est presque jamais intéressant pour les Ensembles.
ArrayDeque un deque peut être utilisé pour de simples québec et de la pile si vous voulez avoir un "first in first out" ou "first in last out" de son comportement, exiger que la ArrayDeque maintient l'ordre d'insertion. Dans ce cas, l'ordre d'insertion est maintenu en tant que partie centrale de la classes de contrat.
Michael Borgwardt
Points
181658
- L'ordre d'insertion est par nature ne sont pas maintenus dans des tables de hachage , c'est comment ils fonctionnent (lire liés à l'article de comprendre les détails). Il est possible d'ajouter une logique de maintenir l'ordre d'insertion (comme dans l'
LinkedHashMap), mais qui prend plus de code, et à l'exécution, plus de mémoire et plus de temps. La perte de performance est généralement pas significatif, mais il peut l'être. - Pour
TreeSet/Map, la raison principale de les utiliser est le naturel de l'itération de l'ordre et d'autres fonctionnalités ajoutées dans l'SortedSet/Mapinterface.
Thorbjørn Ravn Andersen
Points
38688
Dépend de ce que vous avez besoin de la mise en œuvre pour bien faire. L'ordre d'insertion n'est généralement pas intéressant donc il n'est pas nécessaire de le maintenir afin que vous puissiez réorganiser pour obtenir de meilleures performances.
Pour Maps, c'est généralement HashMap et TreeMap qui est utilisé. En utilisant des codes de hachet, les entrées peuvent être mises en petits groupes faciles à rechercher. Le TreeMap maintient un ordre trié des entrées insérées au prix d'une recherche plus lente, mais plus facile à trier qu'un HashMap.
Colin Hebert
Points
40084
Lorsque vous utilisez un HashSet (ou une table de hachage), les données sont stockées dans des "compartiments" basé sur le hachage de l'objet. De cette façon, vos données est plus facile d'accès parce que vous n'avez pas à chercher pour ce type particulier de données dans l'ensemble, vous avez juste à regarder dans la bonne seau.
De cette façon, vous pouvez augmenter les performances sur des points précis.
Chaque Collection de la mise en œuvre de ses particularité de faire mieux pour une utilisation dans une certaine condition. Chacune de ces particularités ont un coût. Donc, si vous n'avez pas vraiment besoin (par exemple l'ordre d'insertion) vous feriez mieux d'utiliser une mise en œuvre qui ne le proposent pas et s'intègre mieux à vos exigences.
