Doublon possible:
Comment fonctionne Java hashmap?
Quelqu'un peut-il m'expliquer comment les HashSets en java fonctionnent et pourquoi ils sont plus rapides que les ArrayLists?
Réponses
Trop de publicités?
Bozho
Points
273663
Un HashSet est en réalité un HashMap où la valeur est toujours la même.
La façon dont fonctionne un HashMap est décrite en de nombreux endroits (on le trouve également appelé "table de hachage"). En résumé: il génère des hachages des clés (objets) et les positionne dans une table. Ensuite, chaque fois que vous recherchez une clé, son hachage est calculé et le seau dans la table est référencé directement. Cela signifie que vous avez juste une opération (meilleur cas) pour accéder à la carte.
Le HashSet contient simplement les clés, donc .contains(..) est en O(1). C'est le seul cas où un HashSet est plus rapide qu'un ArrayList (qui est en O(n)). L'itération est la même, l'ajout est le même.
Tout d'abord, HashSet, contrairement à ArrayList, est un Set : Il ne peut pas contenir de doublons alors que ArrayList le peut - ils sont donc conçus pour des usages différents. De plus, il ne garantit pas l'ordre - contrairement à une liste.
Deuxièmement - un HashSet est construit sur la structure de données table de hachage, ce qui permet un temps de recherche de O(1) pour un élément.
Remarquez que bien des fois, un HashSet est plus lent qu'un ArrayList - si vous voulez par exemple parcourir les éléments - généralement le faire dans un ArrayList sera plus rapide que dans un HashSet [à cause des mauvaises performances en cache du hachage, entre autres raisons]
Cratylus
Points
21838
Il s'agit de 2 structures de données différentes.
Le concept derrière HashSet est la recherche de clé.
C'est-à-dire que vous utilisez une transformation de la clé d'entrée pour obtenir un index de l'emplacement de la valeur dans un tableau.
Il s'agit d'une opération constante O(1) car un tableau permet un accès aléatoire.
La liste de tableaux est également une opération O(1) pour l'accès car elle est également prise en charge par un tableau. Mais seulement pour un accès et une insertion aléatoires.
La recherche en revanche est une opération O(N) pour une liste de tableaux car vous devez rechercher tous les éléments de la liste pour accéder à la valeur contrairement au HashSet où vous transformez simplement la clé et accédez au tableau. La recherche dans un HashSet est O(1)
Anony-Mousse
Points
24646
En fait, par exemple l'itération et l'ajout à un ArrayList sont plus rapides.
Et en fait, il est impossible de trier un HashSet.
Mais le plus rapide de tous est le NoOp. Rien n'est aussi rapide que le NoOp. Bien sûr, il ne fait pas grand-chose, le NoOp. Mais il le fait vraiment rapidement !
Vous devez être plus précis dans ce que vous considérez comme étant "plus rapide que".
