Quand utiliser hashmaps ou treemaps?
Je sais que je peux utiliser TreeMap pour parcourir les éléments lorsque j'ai besoin de les trier. Mais est-ce juste? Il n'y a pas d'optimisation lorsque je veux juste consulter les cartes, ou des utilisations spécifiques optimales?
TreeMap garantit O(log n) recherche du temps (et de l'insertion, etc), alors que l' HashMap offre O(1) recherche du temps si le code de hachage disperse les clés de manière appropriée.
Sauf si vous avez besoin d'entrées pour être triés, je collerais avec HashMap. Ou il y a d' ConcurrentHashMap de cours. Je ne me souviens pas des détails sur les différences entre chacun d'entre eux, mais HashMap est parfaitement raisonnable option "défaut":)
Pour être complet, je dois préciser qu'il y avait une discussion sur un Débordement de Pile un mois ou si il ya sur le fonctionnement interne de diverses cartes. Voir les commentaires dans cette question, que je vais le copier dans cette réponse si bestsss est heureux pour moi de le faire.
Les tables de hashage (généralement) d'effectuer des opérations de recherche (rechercher) délimité au sein de la complexité de l' O(n)<=T(n)<=O(1), avec une moyenne de cas de la complexité de l' O(1 + n/k); toutefois, arbres binaires, (BST), effectuer des opérations de recherche (lookup) délimité au sein de la complexité de l' O(n)<=T(n)<=O(log_2(n)), avec une moyenne de cas de la complexité de l' O(log_2(n)). La mise en œuvre pour chacun d'eux (et tous) structure de données doit être connu (par vous), pour comprendre les avantages, les inconvénients, le temps de la complexité des opérations, et la complexité du code.
Par exemple, le nombre d'entrées dans une table de hachage ont souvent un nombre fixe d'entrées (une partie de ce qui peut ne pas être rempli à tous) avec des listes de collisions. Les arbres, sur l'autre main, généralement deux pointeurs (références) par nœud, mais cela peut être plus si la mise en œuvre permet plus de deux nœuds enfants par nœud, ce qui permet la croissance de l'arbre comme des nœuds sont ajoutés, mais peut ne pas permettre les doublons. (La valeur par défaut de la mise en œuvre d'une application Java TreeMap ne permettent pas de doublons)
Il existe des cas particuliers à prendre en compte, par exemple, que si le nombre d'éléments dans une structure de données augmente sans limite ou s'approche de la limite d'une partie sous-jacente de la structure de données? Qu'en est amorti opérations qui effectuent un certain rééquilibrage ou opération de nettoyage?
Par exemple, dans une table de hachage, lorsque le nombre d'éléments dans la table deviennent suffisamment grande, et l'arbitraire le nombre de collisions peuvent se produire. D'autre part, les arbres nécessitent habituellement viennent de ré-équilibrage de la procédure après l'insertion (ou la suppression).
Donc, si vous avez quelque chose comme un cache (Ex. le nombre d'éléments dans borné, ou la taille est connue), puis une table de hachage est probablement votre meilleur pari; toutefois, si vous avez quelque chose de plus comme un dictionnaire (Ex. remplis une fois et regardé plusieurs fois) puis je utiliser un arbre.
Ce n'est que dans le cas général, cependant, aucune information n'a été donnée). Vous devez comprendre les processus qui se passent comment ils arrivent à faire le bon choix en décidant de quelle structure de données à utiliser.
Quand j'ai besoin d'un multi-carte (à distance de recherche) ou triés à l'aplatissement d'une collection, il ne peut pas être une table de hachage.
La plus grande différence entre les deux est la structure sous-jacente utilisée dans la mise en œuvre.
HashMaps utiliser un tableau et d'une fonction de hachage pour stocker les éléments. Lorsque vous essayez d'insérer ou de supprimer un élément dans la matrice de la fonction de hachage convertit la clé dans un index sur le tableau où l'objet est/doivent être stockés (en ignorant les conflits). Alors que hashmaps sont généralement très rapides, car ils n'ont pas besoin de parcourir de grandes quantités de données, ils ralentissent quand ils sont remplis, car ils ont besoin de copier toutes les clés/valeurs dans une nouvelle matrice.
Les arborescences stocker les données dans une triés structure de l'arbre. Tout cela signifie qu'elles n'aurez jamais à allouer plus d'espace et de copier sur elle, opérations nécessitent qu'une partie des données déjà stockées être itéré. Il suffit parfois de changer de grandes quantités de la structure.
En dehors des deux Hashmaps ont généralement de meilleures performances lorsque vous n'avez pas besoin de tri.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
