Les tables linéaires, les listes liées et les tables de hachage sont couramment utilisées. Lors du développement de Java, JDK nous a fourni une série de classes correspondantes pour implémenter des structures de données de base. Ces classes sont toutes dans le package java.util. Cet article tente d'expliquer aux lecteurs le rôle de chaque classe et comment les utiliser correctement grâce à une description simple.
Collection ├List │✜LinkedList │✜ArrayList │└Vector │└stack └set map ├hashTable ├hashmap └weakhashmap
Interface de collecte
La collection est l'interface de collection la plus élémentaire. Une collection représente un ensemble d'objets, c'est-à-dire les éléments de la collection (éléments). Certaines collections permettent les mêmes éléments tandis que d'autres ne le font pas. Certains peuvent trier mais d'autres ne le peuvent pas. Le SDK Java ne fournit pas de classes directement héritées de la collection. Les classes fournies par le SDK Java sont toutes des "sous-interfaces" qui sont héritées de la collection telles que la liste et le set.
Toutes les classes qui implémentent l'interface de collection doivent fournir deux constructeurs standard: le constructeur sans paramètre est utilisé pour créer une collection vide, et un constructeur de paramètres de collection est utilisé pour créer une nouvelle collection, qui a les mêmes éléments que la collection entrante. Ce dernier constructeur permet à l'utilisateur de copier une collection.
Comment itérer à travers chaque élément d'une collection? Quel que soit le type réel de la collection, il prend en charge une méthode Iterator (), qui renvoie un itérateur, et utilise cet itérateur pour accéder à chaque élément de la collection un par un.
Les usages typiques sont les suivants:
Iterator it = collection.iterator (); // Obtenez un iterator while (it.hasnext ()) {objet obj = it.next (); // Obtenez l'élément suivant} Les deux interfaces dérivées de l'interface de collection sont la liste et le définition.
Interface de liste
La liste est une collection commandée, et l'utilisation de cette interface vous permet de contrôler avec précision la position de chaque insertion d'élément. Les utilisateurs peuvent utiliser des index (la position des éléments dans la liste, similaire aux indices de tableau) pour accéder aux éléments de la liste, ce qui est similaire aux tableaux de Java.
Contrairement à l'ensemble mentionné ci-dessous, la liste permet les mêmes éléments.
En plus de la méthode Iterator () qui a la méthode Iterator () nécessaire, la liste fournit également une méthode ListeTiterator (), qui renvoie une interface ListIterator. Par rapport à l'interface d'itérateur standard, ListIterator a plus de méthodes telles que ADD (), permettant d'ajouter, de supprimer, de définir des éléments et de traverser vers l'avant ou vers l'arrière.
Les classes courantes qui implémentent les interfaces de liste incluent LinkedList, ArrayList, Vector et Stack.
Classe LinkedList
LinkedList implémente l'interface de liste, permettant des éléments nuls. De plus, LinkedList fournit des méthodes supplémentaires Get, Supprimer, INSERT à l'en-tête ou à la queue de la liste Linked. Ces opérations permettent à LinkedList d'être utilisé comme pile, file d'attente ou file d'attente bidirectionnelle.
Notez que LinkedList n'a pas de méthode synchrone. Si plusieurs threads accèdent à une liste en même temps, vous devez implémenter vous-même l'accès à la synchronisation. Une solution consiste à construire une liste synchrone lors de la création:
List list = collections.SynchronizedList (new LinkedList (...));
Classe ArrayList
ArrayList implémente les tableaux de taille variable. Il permet tous les éléments, y compris null. ArrayList n'est pas synchronisé.
Le temps d'exécution de la taille, iSempty, get, set méthodes est constant. Cependant, la surcharge de la méthode ADD est une constante amortie, et il faut du temps (n) pour ajouter n éléments. Les autres méthodes ont un temps d'exécution linéaire.
Chaque instance ArrayList a une capacité, qui est de la taille du tableau utilisé pour stocker des éléments. Cette capacité peut augmenter automatiquement à mesure que de nouveaux éléments sont constamment ajoutés, mais l'algorithme de croissance n'est pas défini. Lorsqu'un grand nombre d'éléments doivent être insérés, la méthode d'assurance peut être appelée avant d'insérer pour augmenter la capacité de la liste Array pour améliorer l'efficacité de l'insertion.
Comme LinkedList, ArrayList n'est également pas synchronisé.
Classe vectorielle
Le vecteur est très similaire à ArrayList, mais le vecteur est synchrone. Bien que l'itérateur créé par Vector soit la même interface que l'itérateur créé par ArrayList, car le vecteur est synchronisé, lorsqu'un itérateur est créé et est utilisé, un autre thread modifie le statut du vecteur (par exemple, l'ajout ou la suppression de certains éléments), donc l'exception doit être prise.
Classe de pile
Stack Hérite de Vector, implémentant une dernière pile de premier out. La pile fournit 5 méthodes supplémentaires pour permettre à Vector d'être utilisée comme pile. Les méthodes de base push et pop et la méthode PEEK obtiennent les éléments en haut de la pile, la méthode vide teste si la pile est vide et la méthode de recherche détecte la position d'un élément dans la pile. La pile est juste créée et est une pile vide.
Définir l'interface
SET est une collection qui ne contient pas d'éléments en double, c'est-à-dire que deux éléments E1 et E2 ont e1.equals (e2) = false, et Set a au plus un élément nul.
De toute évidence, le constructeur de Set a une contrainte et le paramètre de collecte passé ne peut pas contenir d'éléments en double.
Veuillez noter: les objets mutables doivent être exploités avec soin. Si un élément mutable dans un ensemble modifie son propre état, il provoque l'objet.equals (objet) = true pour causer certains problèmes.
Interface cartographique
Veuillez noter que la carte n'hérite pas de l'interface de collecte, et MAP fournit un mappage de la clé à la valeur. Une carte ne peut pas contenir la même touche et chaque clé ne peut cartographier qu'une seule valeur. L'interface MAP offre trois types de vues de la collection. Le contenu de la carte peut être considéré comme un ensemble de collections de clés, un ensemble de collections de valeur ou un ensemble de mappages de valeurs clés.
Classe de hachage
Hashtable implémente l'interface MAP pour implémenter une table de hachage avec un mappage de valeurs de clé. Tout objet non nulle peut être utilisé comme clé ou valeur.
Utilisez Put (Key, Value) pour ajouter des données, utilisez Get (Key) pour récupérer les données. La surcharge de temps de ces deux opérations de base est constante.
Le hachage ajuste les performances par les paramètres de capacité initiale et de facteur de charge. Habituellement, le facteur de charge par défaut 0,75 peut mieux atteindre le temps et l'équilibre de l'espace. L'augmentation du facteur de charge peut économiser de l'espace, mais le temps de recherche correspondant augmentera, ce qui affectera les opérations comme Get and Put.
Un exemple simple d'utilisation d'un hashtable est le suivant: Mettez 1, 2 et 3 dans un hashtable, et leurs clés sont "une", "deux", "trois" respectivement:
Nombres de hashtable = new hashTable ();
nombres.put ("un", nouvel entier (1));
nombres.put ("deux", nouvel entier (2));
nombres.put ("trois", nouvel entier (3));
Pour éliminer un nombre, comme 2, utilisez la clé correspondante:
Entier n = (entier) nombres.get ("deux");
System.out.println ("deux =" + n);
Étant donné qu'un objet en tant que clé déterminera la position de la valeur correspondante en calculant sa fonction de hachage, tout objet en tant que clé doit implémenter le code de hash et égal aux méthodes. Le HashCode et l'égalité des méthodes héritent de l'objet de classe racine. Si vous utilisez une classe personnalisée comme clé, soyez très prudent. Selon la définition de la fonction de hachage, si les deux objets sont les mêmes, c'est-à-dire obj1.equals (obj2) = vrai, leur code de hash doit être le même, mais si les deux objets sont différents, leurs codes de hashs peuvent ne pas être différents. Si les codes de hash de deux objets différents sont les mêmes, ce phénomène est appelé conflit. Le conflit augmentera les frais généraux de temps de fonctionnement du tableau de hachage. Par conséquent, essayez de définir la méthode HashCode () pour accélérer le fonctionnement de la table de hachage.
Si le même objet a des codes de hash différents, l'opération sur la table de hachage aura des résultats inattendus (la méthode GET attendue renvoie NULL). Pour éviter ce problème, il vous suffit de vous souvenir d'une seule chose: vous devez réécrire la méthode Equals et HashCode en même temps, plutôt que d'écrire l'une d'entre elles.
Le haschable est synchronisé.
Classe de hashmap
Hashmap est similaire à Hashable, la différence est que le hashmap est asynchrone et permet une valeur nul et une clé nul et une clé nul. , mais lorsque Hashmap est considéré comme une collection (la méthode VALEUR () peut renvoyer une collection), sa surcharge de temps de sous-opération itérative est proportionnelle à la capacité de HashMAP. Par conséquent, si les performances des opérations d'itération sont très importantes, ne définissez pas la capacité d'initialisation du hashmap pour être trop élevée ou si le facteur de charge est trop faible.
Classe faiblehashmap
LowerHashMap est un hashmap amélioré qui met en œuvre la «référence faible» à la clé. Si une clé n'est plus référencée à l'extérieur, la clé peut être recyclée par GC.
Résumer
Si la pile, la file d'attente et d'autres opérations sont impliquées, vous devriez envisager d'utiliser la liste. Pour les éléments qui doivent être rapidement insérés et supprimés, vous devez utiliser LinkedList. Si les éléments doivent être accessibles rapidement, vous devez utiliser ArrayList.
Package de classe java.util.collections
La classe java.util.collections contient de nombreuses méthodes utiles qui peuvent faciliter le travail des programmeurs, mais ces méthodes ne sont généralement pas entièrement utilisées. Javadoc donne la description la plus complète de la classe de collections: "Cette classe contient une classe statique dédiée qui peut fonctionner ou renvoyer une collection.
»1.2 Méthodes incluses
Iterator, ArrayList, éléments, tampon, carte, collections
LIEZI:
import java.util.arraylist; import java.util.collection; Importer java.util.collections; Importer java.util.comparator; Importer java.util.list; classe publique CollectionsSort {public CollectionsSort () {} public static void main (String [] args) {Double Array [] = {111, 111, 23, 456, 231}; List list = new ArrayList (); List li = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (new double (array [i])); //list.add(""+Array@i]); } double arr [] = {111}; for (int j = 0; j <arr.length; j ++) {li.add (new double (arr [j])); }}2. Opérations spécifiques
1) Trier (trier)
Utilisez la méthode de tri pour trier la liste spécifiée dans l'ordre croissant en fonction de l'ordre naturel des éléments. Tous les éléments de la liste doivent implémenter l'interface comparable. Tous les éléments de cette liste doivent être comparés les uns aux autres en utilisant le comparateur spécifié
Double Array [] = {112, 111, 23, 456, 231}; for (int i = 0; i <array.length; i ++) {list.add (new double (array [i])); } Collection.Sort (liste); for (int i = 0; i <array.length; i ++) {System.out.println (li.get (i)); } // Résultat: 112 111,23,456,2312) mélange
L'algorithme d'arrangement hybride fait exactement le contraire: il perturbe toutes les permutations qui peuvent être trouvées dans une liste. Autrement dit, la liste est réarrangée en fonction de l'entrée de la source aléatoire, une telle arrangement a la même possibilité (en supposant que la source aléatoire est juste). Cet algorithme est très utile pour implémenter un jeu de chance. Par exemple, il peut être utilisé pour mélanger une liste d'objets de carte représentant un jeu de cartes. De plus, il est également très utile lors de la génération de cas de test.
CollectionS.Shuffling (list) Double Array [] = {112, 111, 23, 456, 231}; for (int i = 0; i <array.length; i ++) {list.add (new double (array [i])); } Collection.Shuffle (liste); for (int i = 0; i <array.length; i ++) {System.out.println (li.get (i)); } // Résultat: 112 111,23,456,2313) inverser
Utilisez la méthode inverse pour trier la liste spécifiée par ordre décroissant en fonction de l'ordre naturel des éléments.
Collection.Reverse (list) Double Array [] = {112, 111, 23, 456, 231}; for (int i = 0; i <array.length; i ++) {list.add (new double (array [i])); } Collections. inverse (liste); for (int i = 0; i <array.length; i ++) {System.out.println (li.get (i)); } // Résultat: 231 456,23,111,112 4) Remplacez tous les éléments de la liste spécifiée par l'élément spécifié. String str [] = {"dd", "aa", "bb", "cc", "ee"}; pour (int j = 0; j <str.length; j ++) {li.add (new String (str [j])); } Collections.fill (li, "aaa"); for (int i = 0; i <li.size (); i ++) {System.out.println ("list [" + i + "] =" + li.get (i)); } // Résultat: aaa, aaa, aaa, aaa5) Copier (Copier)
Utilisez deux paramètres, une liste cible et une liste source, pour copier l'élément source sur la cible et écraser son contenu. La liste cible est au moins tant que la source. S'il est plus long, les éléments restants de la liste cible ne sont pas affectés.
Collection.Copy (List, Li): Ce dernier paramètre est la liste cible, la précédente est la liste source
Double Array [] = {112, 111, 23, 456, 231}; List list = new ArrayList (); List li = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (new double (array [i])); } double arr [] = {1131,333}; String str [] = {"dd", "aa", "bb", "cc", "ee"}; for (int j = 0; j <arr.length; j ++) {li.add (new double (arr [j])); } Collections.copy (list, li); for (int i = 0; i <list.size (); i ++) {System.out.println ("list [" + i + "] =" + list.get (i)); } // Résultat: 1131,333,23,456,2316) Renvoie le plus petit élément des collections (min)
Renvoie le plus petit élément de la collection donnée en fonction de l'ordre dans lequel le comparateur spécifié est généré. Tous les éléments de la collection doivent être comparés les uns aux autres via le comparateur spécifié
Collection.Min (list) Double Array [] = {112, 111, 23, 456, 231}; List list = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (new double (array [i])); } Collection.Min (liste); for (int i = 0; i <list.size (); i ++) {System.out.println ("list [" + i + "] =" + list.get (i)); } // Résultat: 237) Renvoie le plus petit élément (max) dans les collections
Renvoie l'élément maximum de la collection donnée en fonction de l'ordre dans lequel le comparateur spécifié est généré. Tous les éléments de la collection doivent être comparés les uns aux autres via le comparateur spécifié
Collection.max (list) Double Array [] = {112, 111, 23, 456, 231}; List list = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (new double (array [i])); } Collection.max (list); for (int i = 0; i <list.size (); i ++) {System.out.println ("list [" + i + "] =" + list.get (i)); } // Résultat: 4568) LastIndexofSublist
Renvoie la position de départ de la liste cible spécifiée qui est apparue pour la dernière fois dans la liste des sources spécifiées
int count = collections.LastIndexofSublist (list, li); Double Array [] = {112, 111, 23, 456, 231}; List list = new ArrayList (); List li = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (new double (array [i])); } double arr [] = {111}; String str [] = {"dd", "aa", "bb", "cc", "ee"}; for (int j = 0; j <arr.length; j ++) {li.add (new double (arr [j])); } Int locations = collections. LastIndexofSublist (List, Li); System.out.println ("===" + emplacements); // Résultat 39) INDEXOFSUBLIST
Renvoie la position de départ de la première fois que la liste cible spécifiée apparaît dans la liste des sources spécifiées
int count = collections.IndexofSublist (list, li); Double Array [] = {112, 111, 23, 456, 231}; List list = new ArrayList (); List li = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (new double (array [i])); } double arr [] = {111}; String str [] = {"dd", "aa", "bb", "cc", "ee"}; for (int j = 0; j <arr.length; j ++) {li.add (new double (arr [j])); } Int locations = collections.IndexofSublist (list, li); System.out.println ("===" + emplacements); // Résultat 110) Rotation
Déplacer cycliquement les éléments dans la liste spécifiée en fonction de la distance spécifiée
Collection.Rotate (List, -1);
S'il s'agit d'un nombre négatif, il se déplace positivement, et s'il se déplace positivement, il se déplace positivement.
Double Array [] = {112, 111, 23, 456, 231}; List list = new ArrayList (); for (int i = 0; i <array.length; i ++) {list.add (new double (array [i])); } Collection.Rotate (List, -1); for (int i = 0; i <list.size (); i ++) {System.out.println ("list [" + i + "] =" + list.get (i)); } // Résultat: 111,23,456,231,112L'article ci-dessus discute brièvement de la collecte des classes d'implémentation et de la carte des structures de données couramment utilisées en Java. C'est tout le contenu que j'ai partagé avec vous. J'espère que vous pourrez vous faire référence et j'espère que vous pourrez soutenir Wulin.com plus.