pourquoi il est préférable de convertir HashSet à TreeSet ensuite travailler directement avec TreeSet

Question

Dans de nombreux endroits dans le Web, y compris le site web du soleil, la phrase suivante apparaît:

Il généralement plus rapide de la préforme actions sur hashSet puis convertir le hashset à treeset.

bien, je suis un peu confus, thats correct qui ajoutent élément hashset est o(1) et objet en ajoutant treeset (noir & arbre rouge) est o(logn) mais quand je convertir le HashSet au TreeSet i besoin de trier mes données qui est o(nlogn) alors pourquoi il est plus rapide de travailler avec hashset, puis le convertir en treeset? je sais que si vous préformez enlever ou élément existant donc il y a une différence entre hash et arbre mais je ne pense pas que ce soit le facteur auquel se réfère le soleil (du moins je l'espère puisque cela ressemble à une très petite chose) autre chose est les méthodes hashcode peut être pas si bon, puis l'ajout d'éléments au hachage ne sera pas o(1) ou la méthode hashcode peut être compliquée. donc généralement je ne comprends pas la phrase. Quelqu'un peut-il m'aider?

Answer 1

Cela dépend du nombre d'opérations effectuées dans la table de hachage avant de copier les éléments dans l'arborescence triée. Si tout ce que vous faites est d'insérer n éléments distincts à la table de hachage, alors non, il ne sera pas plus rapide de le faire, puis les copier dans l'arbre :)

Un ensemble hashed d'éléments peut être converti en un arbre trié par soit: en utilisant un tri normal puis en construisant l'arbre à partir de cela, ou en insérant les éléments dans l'arbre un à la fois. Le premier signifie une copie/traversal supplémentaire; le dernier moyen supplémentaire pour maintenir un arbre équilibré (bien que si vous itérez une table de hachage, vous obtenez les éléments dans un ordre aléatoire, ce qui signifie que vous pourriez probablement éviter la plupart des rééquilibrage).

Les tables de hachage sont en effet plus rapides que les arborescences de recherche pour les opérations bien supportées (insérer/modifier/supprimer), mais cela ne vaut vraiment pas la peine de faire ce que Sun recommande. une accélération globale précieuse de ce qui sera probablement une légère amélioration. Les tables de hachage ont un avantage encore plus important sur les arbres triés lorsque la comparaison de clés est coûteuse (comme avec les chaînes), car pour les grands ensembles, moins d'objets auront une collision de hachage que l'arbre de recherche est profond. pour mettre en cache le code de hachage pour les clés déjà dans l'ensemble, en sautant la comparaison coûteuse pour (probablement) tous sauf le résultat correspondant.