Question Comment fonctionnent les HashSets dans Java? [dupliquer]


Duplication possible:
Comment fonctionne le hashmap Java? 

Quelqu'un peut-il m'expliquer comment HashSets dans Java fonctionne et pourquoi ils sont plus rapides que d'utiliser ArrayLists?


16
2018-02-02 20:52


origine


Réponses:


Premier, HashSet, contrairement à ArrayList est un Ensemble: Il ne peut pas contenir de doublons ArrayList peuvent - donc ils sont construits à des fins différentes. Il ne garantit pas non plus la commande - encore une fois, contrairement à une liste.

Deuxièmement - un HashSet est construit sur le table de hachage structure de données, qui permet O(1) chercher du temps pour un élément.

Notez que plusieurs fois, un HashSet est Ralentissez alors un ArrayList - si tu veux répéter sur des éléments par exemple - le fait généralement dans un ArrayList sera plus rapide que dans un HashSet [en raison d'une mauvaise performance du hachage du cache, entre autres raisons]


14
2018-02-02 20:56



UNE HashSet est en fait un HashMap où la valeur est toujours la même.

La façon dont un HashMap les œuvres sont décrites dans de nombreux endroits (on parle aussi de "hashtable"). En bref: il génère des hachages de clés (objets) et les positionne dans une table. Ensuite, chaque fois que vous recherchez une clé, son hachage est calculé et le compartiment de la table est référencé directement. Cela signifie que vous n'avez qu'une seule opération (le meilleur des cas) pour accéder à la carte.

le HashSet contient simplement les clés, donc .contains(..) est O(1). Ça et remove(..) sont les seules opérations HashSet est plus rapide qu'un ArrayList (qui est O (n)). L'itération est la même, l'addition est la même.


19
2018-02-02 20:56



Ce sont 2 structures de données différentes.

Le concept derrière HashSet est la vérification des clés.
C'est à dire. Vous utilisez une transformation de la clé d'entrée pour obtenir un index de l'emplacement de la valeur dans un tableau.
Ceci est une constante O(1) opération depuis un tableau permet un accès aléatoire.

Le arraylist est aussi O(1) opération pour l'accès car il est également soutenu par un tableau. Mais uniquement pour un accès aléatoire et une insertion.

le chercher mais est O(N) opération pour un arraylist puisque vous devez rechercher tous les éléments de la liste pour obtenir la valeur contrairement à la HashSet où il vous suffit de transformer la clé et d'accéder au tableau. Rechercher dans un HashSet est O(1)


1
2018-02-02 21:03



En fait, par exemple itérer sur et ajouter à un ArrayList est plus rapide.

Et diable, vous ne pouvez même pas Trier un HashSet.

Mais le plus rapide est le NoOp. Il n'y a rien à distance aussi rapide que le NoOp. Certes, cela ne fait pas grand chose, le NoOp. Mais c'est vraiment rapide à ça!

Vous devez être plus précis dans ce que vous considérez comme "plus rapide que".


0
2018-02-02 21:01