Qu'est-ce qu'une classe de collection en Java ? Explication de la structure des classes de collection avec des exemples graphiques

1. Collections en Java

La classe collection en Java est la classe la plus fréquemment utilisée et la plus pratique en programmation Java. En tant que classe conteneur, la classe collection peut stocker n'importe quel type de données. Bien entendu, elle peut également être combinée avec des génériques pour stocker des types spécifiés (mais les génériques ne sont valides qu'au moment de la compilation et seront effacés au moment de l'exécution). Ce qui est stocké dans la classe collection n'est qu'une référence à l'objet, pas à l'objet lui-même. La capacité de la classe de collection peut être étendue de manière dynamique pendant l'exécution et fournit également de nombreuses méthodes pratiques, telles que la recherche de l'union et de l'intersection d'ensembles.

2. Structure de classe de collection

Les collections en Java incluent une variété de structures de données, telles que des listes chaînées, files d'attente, table de hachage, etc. Du point de vue de la structure d'héritage des classes, il peut être divisé en deux catégories principales. L'une est héritée de l'interface Collection. Ce type de collection comprend des classes de collection telles que List, Set et Queue. L'autre type est hérité de l'interface Map, qui comprend principalement des classes de collection liées aux tables de hachage. Jetons un coup d'œil au schéma de structure d'héritage de ces deux catégories :

1 Liste, Ensemble et Queue

La ligne pointillée verte sur la figure représente l'implémentation, la ligne continue verte représente l'héritage entre les interfaces et la ligne continue bleue représente l'héritage entre les classes.

(1) Liste : Nous utilisons davantage de listes, notamment ArrayList et LinkedList. La différence entre les deux est également évidente, comme le montre leurs noms. La couche inférieure d'ArrayList est implémentée via des tableaux, sa vitesse d'accès aléatoire est donc relativement rapide, mais pour les situations nécessitant des ajouts et des suppressions fréquents, l'efficacité est relativement faible. Pour LinkedList, la couche inférieure est implémentée via une liste chaînée, les opérations d'ajout et de suppression sont donc plus faciles à réaliser, mais l'efficacité de l'accès aléatoire est relativement faible.

Regardons d'abord l'efficacité d'insertion des deux :

package com.paddx.test.collection;
import java.util.ArrayList;
import java.util.LinkedList;
public class ListTest {
public static void main(String[] args) {
for(int i=;i<;i++){
}
long start = System.currentTimeMillis();
LinkedList<Integer> linkedList = new LinkedList<Integer>();
for(int i=;i<;i++){
linkedList.add(,i);
}
long end = System.currentTimeMillis();
System.out.println(end - start);
ArrayList<Integer> arrayList = new ArrayList<Integer>();
for(int i=;i<;i++){
arrayList.add(,i);
}
System.out.println(System.currentTimeMillis() - end);
}
}

Ce qui suit est le résultat de l'exécution locale :

23

1227

On peut voir que dans ce cas, l'efficacité d'insertion de LinkedList est bien supérieure à celle d'ArrayList. Bien sûr, c'est relativement extrême. situation. Comparons l'efficacité de l'accès aléatoire entre les deux :

package com.paddx.test.collection;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Random;
public class ListTest {
public static void main(String[] args) {
Random random = new Random();
for(int i=;i<;i++){
}
LinkedList<Integer> linkedList = new LinkedList<Integer>();
for(int i=;i<;i++){
linkedList.add(i);
}
ArrayList<Integer> arrayList = new ArrayList<Integer>();
for(int i=;i<;i++){
arrayList.add(i);
}
long start = System.currentTimeMillis();
for(int i=;i<;i++){
int j = random.nextInt(i+);
int k = linkedList.get(j);
}
long end = System.currentTimeMillis();
System.out.println(end - start);
for(int i=;i<;i++){
int j = random.nextInt(i+);
int k = arrayList.get(j);
}
System.out.println(System.currentTimeMillis() - end);
}
}

Ce qui suit est le résultat de mon exécution locale :

5277

6

Il est évident que l'efficacité de l'accès aléatoire d'ArrayList est de plusieurs ordres de grandeur supérieure à celle de LinkedList. Grâce à ces deux morceaux de code, nous devrions être en mesure de comprendre clairement les différences entre LinkedList et ArrayList et les scénarios applicables. Quant à Vector, il s'agit d'une version thread-safe d'ArrayList, tandis que Stack correspond à la structure de données de la pile. Ces deux-là sont rarement utilisés, je ne donnerai donc pas d'exemple ici.

(2) File d'attente : généralement, elle peut être complétée directement à l'aide de LinkedList. Comme le montre le diagramme de classes ci-dessus, LinkedList hérite de Deque, LinkedList a donc la fonction d'une file d'attente à double extrémité. . La caractéristique de PriorityQueue est de fournir une priorité pour chaque élément, et les éléments ayant une priorité élevée seront les premiers retirés de la file d'attente.

　(3) Set : La principale différence entre Set et List est que Set ne permet pas de répéter les éléments, tandis que List permet de répéter les éléments. La détermination de la duplication des éléments doit être déterminée en fonction de la méthode de hachage et de la méthode égale de l'objet. C'est pourquoi nous remplaçons généralement la méthode hashCode et la méthode equals pour les classes d'éléments de la collection. Prenons un exemple pour regarder la différence entre Set et List, ainsi que les fonctions de la méthode hashcode et de la méthode equals :

package com.paddx.test.collection;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
public class SetTest {
public static void main(String[] args) {
Person p1 = new Person("lxp",10);
Person p2 = new Person("lxp",10);
Person p3 = new Person("lxp",20);
ArrayList<Person> list = new ArrayList<Person>();
list.add(p1);
System.out.println("---------");
list.add(p2);
System.out.println("---------");
list.add(p3);
System.out.println("List size=" + list.size());
System.out.println("----分割线-----");
Set<Person> set = new HashSet<Person>();
set.add(p1);
System.out.println("---------");
set.add(p2);
System.out.println("---------");
set.add(p3);
System.out.println("Set size="+set.size());
}
static class Person{
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public boolean equals(Object o) {
System.out.println("Call equals();name="+name);
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
return name.equals(person.name);
}
@Override
public int hashCode() {
System.out.println("Call hashCode(),age="+age);
return age;
}
}
}

Les résultats d'exécution du code ci-dessus sont les suivants :

---------
---------
List size=3
----分割线-----
Call hashCode(),age=10
---------
Call hashCode(),age=10
Call equals();name=lxp
---------
Call hashCode(),age=20
Set size=2

D'après les résultats, on peut voir que lorsque des éléments sont ajoutés à la liste, aucune opération supplémentaire n'est effectuée et peut être répétée. Avant d'ajouter le Set, vous devez d'abord exécuter la méthode hashCode. Si la valeur renvoyée existe déjà dans l'ensemble, vous devez continuer à exécuter la méthode égal. Si le résultat renvoyé par la méthode égal est également vrai, cela prouve que l'élément. existe déjà et sera écrasé par le nouvel élément. Les anciens éléments, si les valeurs hashCode renvoyées sont différentes, sont directement ajoutés à la collection. N'oubliez pas ici que pour les éléments de la collection, les éléments avec des valeurs hashCode différentes ne doivent pas être égaux, mais les éléments inégaux peuvent avoir la même valeur hashCode.

La différence entre HashSet et LinkedHashSet est que ce dernier peut garantir que l'ordre des éléments insérés dans l'ensemble est cohérent avec l'ordre de sortie. La différence entre TresSet est qu'il est trié selon Comparator. Par défaut, il est classé par ordre croissant selon l'ordre naturel des caractères.

(4) Iterable : Sur cette image, vous pouvez voir que la classe Collection hérite d'Iterable. La fonction de cette interface est de fournir la fonction de parcours d'éléments, c'est-à-dire toutes les classes de collection. (à l'exception des classes liées à Map) fournissent toutes la fonction de traversée d'éléments. Iterable contient l'itérateur d'Iterator. Son code source est le suivant Si vous êtes familier avec le modèle d'itérateur, il devrait être facile à comprendre.

public interface Iterator<E> {
boolean hasNext();
E next();
void remove();
}

2. Carte :

Map类型的集合最大的优点在于其查找效率比较高，理想情况下可以实现O(1)的时间复杂度。Map中最常用的是HashMap，LinkedHashMap与HashMap的区别在于前者能够保证插入集合的元素顺序与输出顺序一致。这两者与TreeMap的区别在于TreeMap是根据键值进行排序的，当然其底层的实现也有本质的区别，如HashMap底层是一个哈希表，而TreeMap的底层数据结构是一棵树。我们现在看下TreeMap与LinkedHashMap的区别：

package com.paddx.test.collection;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;
public class MapTest {
public static void main(String[] args) {
Map<String,String> treeMap = new TreeMap<String,String>();
Map<String,String> linkedMap = new LinkedHashMap<String, String>();
treeMap.put("b",null);
treeMap.put("c",null);
treeMap.put("a",null);
for (Iterator<String> iter = treeMap.keySet().iterator();iter.hasNext();){
System.out.println("TreeMap="+iter.next());
}
System.out.println("----------分割线---------");
linkedMap.put("b",null);
linkedMap.put("c",null);
linkedMap.put("a",null);
for (Iterator<String> iter = linkedMap.keySet().iterator();iter.hasNext();){
System.out.println("LinkedHashMap="+iter.next());
}
}
}

运行上述代码，执行结果如下：

TreeMap=a
TreeMap=b
TreeMap=c
----------分割线---------
LinkedHashMap=b
LinkedHashMap=c
LinkedHashMap=a

　　从运行结果可以很明显的看出这TreeMap和LinkedHashMap的区别，前者是按字符串排序进行输出的，而后者是根据插入顺序进行输出的。细心的读者可以发现，HashMap与TreeMap的区别，与之前提到的HashSet与TreeSet的区别是一致的，在后续进行源码分析的时候，我们可以看到HashSet和TreeSet本质上分别是通过HashMap和TreeMap来实现的，所以它们的区别自然也是相同的。HashTable现在已经很少使用了，与HashMap的主要区别是HashTable是线程安全的，不过由于其效率比较低，所以通常使用HashMap，在多线程环境下，通常用CurrentHashMap来代替。

三、总结

　　本文只是从整体上介绍了Java集合框架及其继承关系。除了上述类，集合还提供Collections和Arrays两个工具类，此外，集合中排序跟Comparable和Comparator紧密相关。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!