Java
gilles81
Messages postés
67
Date d'inscription
Statut
Membre
Dernière intervention
-
kilian Messages postés 8732 Date d'inscription Statut Modérateur Dernière intervention -
kilian Messages postés 8732 Date d'inscription Statut Modérateur Dernière intervention -
Bonjour,
quelqu'un peut il me qu'elle est la différence entre un hasMap,treeMap,sortedMap.Avec quelques exemples svp
merci
quelqu'un peut il me qu'elle est la différence entre un hasMap,treeMap,sortedMap.Avec quelques exemples svp
merci
A voir également:
- Java
- Waptrick java football - Télécharger - Jeux vidéo
- Jeux java itel - Télécharger - Jeux vidéo
- Eclipse java - Télécharger - Langages
- Java apk - Télécharger - Langages
- Waptrick java voiture - Télécharger - Jeux vidéo
1 réponse
Salut,
C'est la même chose, dans l'absolu: un tableau dont les index sont des objets. Tu as une paire clé valeur pour chaque entrée.
Après c'est l'implémentation interne qui diffère. Un HashMap utilise une table de hachage.
https://fr.wikipedia.org/wiki/Table_de_hachage
Pratique car l'accés aux élément est assez rapide.
Au mieux il trouve l'élément que tu demandes du premier coup, au pire il va parcourir toutes les entrées.
Par contre tout est foutu dans le désordre dedans.
Un SortedMap c'est une tableau associatif ou les paires sont triés par clé. Donc si tu parcoures ton tableau avec un itérateur, tu iras de la clé la plus petite à la plus grande. Si les clés sont des chaînes, le tri se fait par ordre alphabétique.
Par contre l'accés à un élément particulier à partir de sa clé est moins rapide qu'avec un HashMap.
Il va parcourir toutes les clés dans l'ordre jusqu'à ce qu'il trouve l'élément.
Un TreeMap c'est un compromis entre les deux. Les clés sont triées et en même temps l'accés à un élément se fait assez rapidement, moins rapide en moyenne qu'avec un HashMap mais plus rapide qu'avec un SortedMap. Ca utilise un algorithme d'arbre bicolore:
https://fr.wikipedia.org/wiki/Arbre_rouge-noir
C'est la même chose, dans l'absolu: un tableau dont les index sont des objets. Tu as une paire clé valeur pour chaque entrée.
Après c'est l'implémentation interne qui diffère. Un HashMap utilise une table de hachage.
https://fr.wikipedia.org/wiki/Table_de_hachage
Pratique car l'accés aux élément est assez rapide.
Au mieux il trouve l'élément que tu demandes du premier coup, au pire il va parcourir toutes les entrées.
Par contre tout est foutu dans le désordre dedans.
Un SortedMap c'est une tableau associatif ou les paires sont triés par clé. Donc si tu parcoures ton tableau avec un itérateur, tu iras de la clé la plus petite à la plus grande. Si les clés sont des chaînes, le tri se fait par ordre alphabétique.
Par contre l'accés à un élément particulier à partir de sa clé est moins rapide qu'avec un HashMap.
Il va parcourir toutes les clés dans l'ordre jusqu'à ce qu'il trouve l'élément.
Un TreeMap c'est un compromis entre les deux. Les clés sont triées et en même temps l'accés à un élément se fait assez rapidement, moins rapide en moyenne qu'avec un HashMap mais plus rapide qu'avec un SortedMap. Ca utilise un algorithme d'arbre bicolore:
https://fr.wikipedia.org/wiki/Arbre_rouge-noir
Oui HashMap et TreeMap ont les mêmes méthodes. Simplement les classes qui implémentent SortedMap doivent implémenter des méthodes en plus comme firstKey(), lastKey() etc...
Voir: https://docs.oracle.com/javase/1.5.0/docs/api/java/util/SortedMap.html
Exactement Kilian.
Au mieux il trouve l'élément que tu demandes du premier coup, au pire il va parcourir toutes les entrées.
Oui, enfin, il ne parcourt que les entrées qui ont la même clé, ça ne parcourt quand même pas toutes les entrées de la hashmap, donc c'est toujours mieux qu'une linkedList.
En gros gilles81, pour résumer les propos de Kilian, la hashmap te permet d'accéder à tes éléments en O(1) (si ta fonction de hachage est bien choisie).
Le treemap te permet de faire des recherches sur tes éléments de la meilleure façon possible (complexité en recherche en O(n log n), donc le must du must), et les méthodes d'insertion et de suppression sont optimisées, mais toujours moins bien que pour une hashmap.
A toi de voir donc si tu as besoin d'avoir des éléments triés (auquel cas un treemap serait le bon choix), ou non (et là la hashmap serait la bonne solution).
Lis bien les liens de kilian pour bien comprendre les mécanismes internes aux différentes structures.
Cordialement.
Ah! J'me disais bien. Sur wikipedia ils disaient au pire en O(n), je comprenais pas pourquoi mais en fait c'est pour le cas où il y a la même clé plusieurs fois. Ouf, merci, j'ai rarement manipulé des tables de hachage alors... :-)
J'essayais justement de ne pas parler de complexité algorithmique et de traduire ces notions en "ressenti" mais puisqu'on y vient....
Alors quelques notions de complexité algorithmiques pour Gilles (s'il ne connait pas):
O(1) => Le résultat de la recherche d'un élément est immédiat.
O(n) => Le temps de recherche d'un élément est proportionel au nombre d'élements dans le tableau.
O(log(n)) => Euh... la recherche ne prend pas beaucoup de temps mais quand même plus qu'en O(1) :-)
En gros Gilles, avantages et inconvénients:
HashMap => Pas triés, opérations rapides sur les éléments (ajout/suppression/recherche)
TreeMap => Triés, opérations un peu moins rapides sur les éléments