Quelles sont les structures de données Java ?

Les structures de données Java incluent : 1. Liste ; 2. Vecteur ; 3. ArrayList ; 5. Ensemble ; 7. LinkedHashSet ; .

L'environnement d'exploitation de cet article : système Windows10, Java 1.8, ordinateur Thinkpad T480.

Il existe plusieurs structures de données couramment utilisées en Java, qui sont principalement divisées en deux interfaces principales : Collection et map (l'interface ne fournit que des méthodes, pas des implémentations), et les structures de données finalement utilisées dans le programme sont héritées. à partir de ceux-ci La classe de structure de données de l'interface.

Collection---->Collections   
Map----->SortedMap------>TreeMap          Map------>HashMap
Collection---->List----->(Vector \ ArryList \ LinkedList)
Collection---->Set------>(HashSet \ LinkedHashSet \ SortedSet)

Liste (interface)

La liste est une collection ordonnée L'utilisation de cette interface peut contrôler avec précision la position d'insertion de chaque élément. Les utilisateurs peuvent utiliser l'index (la position de l'élément dans la liste, similaire à l'indice du tableau) pour accéder aux éléments de la liste, ce qui est similaire aux tableaux Java.

Vecteur

La liste basée sur un tableau (Array) encapsule en fait certaines fonctions que les tableaux n'ont pas à utiliser, il est donc difficile d'éviter les limitations des tableaux, et les performances sont également impossible Au-delà des tableaux. Par conséquent, lorsque cela est possible, nous devrions utiliser davantage les tableaux. Un autre point très important est que Vector est synchronisé avec les threads (synchronisé), ce qui constitue également une différence importante entre Vector et ArrayList.

ArrayList

Comme Vector, il s'agit d'une liste chaînée basée sur un tableau, mais la différence est qu'ArrayList n'est pas synchronisé. Par conséquent, il est meilleur que Vector en termes de performances, mais lors de l'exécution dans un environnement multithread, vous devez gérer vous-même la synchronisation des threads.

LinkedList

LinkedList est différente des deux listes précédentes. Elle n'est pas basée sur des tableaux, elle n'est donc pas limitée par les performances des tableaux.

Chaque nœud (Node) contient deux aspects de contenu :

1 Les données du nœud lui-même

2.

Ainsi, lors de l'ajout et de la suppression d'actions dans LinkedList, vous n'avez pas besoin de déplacer beaucoup de données comme ArrayList basé sur un tableau. Ceci peut être réalisé en modifiant simplement les informations pertinentes de nextNode. C'est l'avantage de LinkedList.

Résumé de la liste

Toutes les listes ne peuvent contenir qu'une table composée d'un seul objet de types différents, et non de paires clé-valeur. Par exemple : [ tom,1,c ]

Toutes les listes peuvent avoir les mêmes éléments, par exemple, Vector peut avoir [ tom,koo,too,koo ]

Toutes les listes peuvent y avoir sont des éléments nuls, tels que [tom,null,1]

La liste basée sur un tableau (Vector, ArrayList) convient aux requêtes, tandis que LinkedList convient aux opérations d'ajout et de suppression

Set ( interface)

Set est une collection qui ne contient pas d'éléments répétés

HashSet

Bien que Set et List implémentent tous deux l'interface Collection, leurs méthodes d'implémentation sont assez différentes. La liste est essentiellement basée sur Array. Mais Set est implémenté sur la base de HashMap. C'est la différence fondamentale entre Set et List. La méthode de stockage de HashSet consiste à utiliser la clé dans HashMap comme élément de stockage correspondant de Set. Cela sera clair en un coup d'œil si vous regardez l'implémentation de la méthode add(Object obj) de HashSet.

LinkedHashSet

Une sous-classe de HashSet, une liste chaînée.

SortedSet

Ordered Set, implémenté via SortedMap.

Map (interface)

Map est un conteneur qui associe des objets clés et des objets de valeur, et un objet de valeur peut être une Map, et ainsi de suite, formant ainsi un mappage à plusieurs niveaux. Pour les objets clés, comme Set, les objets clés d'un conteneur Map ne peuvent pas être répétés afin de maintenir la cohérence des résultats de la recherche. S'il y a deux objets clés identiques, vous souhaitez obtenir la valeur. objet correspondant à cet objet clé. Il y aura un problème. Peut-être que ce que vous obtiendrez n'est pas l'objet de valeur que vous pensiez, et le résultat sera une confusion. Par conséquent, le caractère unique de la clé est très important et correspond à la nature de. l'ensemble.

Bien entendu, lors de l'utilisation, l'objet valeur correspondant à une certaine clé peut changer. Dans ce cas, le dernier objet valeur modifié correspondra à la clé. Il n'y a aucune exigence d'unicité pour les objets de valeur. Vous pouvez mapper n'importe quel nombre de clés à un objet de valeur sans aucun problème (mais cela peut gêner votre utilisation. Vous ne savez pas ce que vous obtenez. L'objet de valeur correspond-il à cela ? clé).

(Partage de tutoriel vidéo gratuit : Tutoriel vidéo Java)

HashMap

Implémentation de l'interface Map basée sur la table de hachage. Cette implémentation fournit toutes les opérations de mappage facultatives et autorise les valeurs nulles et les clés nulles. (La classe HashMap est à peu près la même chose qu'une Hashtable, sauf qu'elle n'est pas synchronisée et autorise null.) Cette classe ne garantit pas l'ordre de la carte, et en particulier elle ne garantit pas que l'ordre soit immuable. De plus, HashMap n'est pas thread-safe, ce qui signifie qu'il peut y avoir des problèmes dans un environnement multithread, tandis que Hashtable est thread-safe.

TreeMap

TreeMap stocke les clés dans l'ordre,

HashTable

(1) Hashtable est une table de hachage et le contenu qu'elle stocke est la valeur de la clé mappage de paires (clé-valeur).

(2) Hashtable hérite de Dictionary et implémente les interfaces Map, Cloneable et java.io.Serializing.

(3) Les fonctions de table de hachage sont toutes synchrones, ce qui signifie qu'elles sont thread-safe. Ni sa clé ni sa valeur ne peuvent être nulles.

Différences entre plusieurs classes couramment utilisées

1. ArrayList : élément unique, haute efficacité, principalement utilisé pour la requête

2. Vecteur : élément unique, thread-safe, principalement utilisé pour les requêtes

3. LinkedList : élément unique, principalement utilisé pour l'insertion et la suppression

4. HashMap : les éléments sont par paires, les éléments peuvent être vides

5. HashTable : les éléments sont par paires, thread-safe, les éléments ne peuvent pas être nuls

Vector, ArrayList et LinkedList

Dans la plupart des cas, ArrayList est le meilleur en termes de performances, mais lorsque les éléments de La collection dont LinkedList a besoin fonctionnera mieux lors des insertions et des suppressions fréquentes, mais les performances des trois d'entre eux ne sont pas aussi bonnes que celles des tableaux. De plus, Vector est synchronisé avec les threads. Donc :

Si vous pouvez utiliser un tableau (le type d'élément est fixe, la longueur du tableau est fixe), veuillez essayer d'utiliser un tableau au lieu de List

S'il n'y a pas de suppression et d'insertion fréquentes ; opérations, il n'est pas nécessaire de trop réfléchir. Pour les problèmes de thread, ArrayList est préféré

Si utilisé dans des conditions multi-thread, vous pouvez envisager Vector

Si des suppressions et des insertions fréquentes sont nécessaires ; , LinkedList entre en jeu

Si vous ne savez rien, il n'y a rien de mal à utiliser ArrayList.

Pile

Une pile est une liste linéaire spéciale qui ne peut être insérée et supprimée qu'à une extrémité. Il stocke les données selon le principe du premier entré, dernier sorti. Les données qui entrent en premier sont poussées vers le bas de la pile. Enfin, les données de

sont en haut de la pile. pour être lues, les données sont extraites du haut de la pile (les dernières données sont poussées vers le bas de la pile lors de la lecture).

File d'attente

Une table linéaire spéciale qui permet uniquement les opérations de suppression à l'avant du tableau (avant) et les opérations d'insertion à l'arrière (arrière) du tableau. La fin qui effectue l'opération d'insertion

est appelée la queue de la file d'attente, et la fin qui effectue l'opération de suppression est appelée la tête de la file d'attente. Lorsqu’il n’y a aucun élément dans la file d’attente, on parle de file d’attente vide.

Tableau

En programmation, pour faciliter le traitement, plusieurs variables du même type sont organisées sous une forme ordonnée. Une collection de ces éléments de données similaires disposés séquentiellement est appelée un tableau. En langage C, les tableaux sont des types de données construits. Un tableau peut être décomposé en plusieurs éléments de tableau. Ces éléments de tableau

peuvent être des types de données de base ou des types construits. Par conséquent, selon le type d'éléments du tableau, les tableaux peuvent être divisés en diverses catégories telles que les tableaux numériques, les tableaux de caractères, les tableaux de pointeurs et les tableaux de structure.

Liste chaînée

Une structure de stockage non continue et non séquentielle sur les unités de stockage physiques. L'ordre logique des éléments de données est réalisé via l'ordre des liens du pointeur dans la liste chaînée.

Une liste chaînée se compose d'une série de nœuds (chaque élément de la liste chaînée est appelé un nœud), et les nœuds peuvent être générés dynamiquement au moment de l'exécution. Chaque nœud comprend deux parties :

L'une est le champ de données qui stocke les éléments de données et l'autre est le champ de pointeur qui stocke l'adresse du nœud suivant.

Arbre

Un arbre est un ensemble fini K contenant n (n>0) nœuds, et une relation N est définie dans K. N satisfait les conditions suivantes :

(1) Il n’y a et il n’y a qu’un seul nœud k0. Il n’a pas de prédécesseur pour la relation N. K0 est appelé nœud racine de l’arbre. Appelée racine (root)

(2) À l'exception de K0, chaque nœud de k a et n'a qu'un seul prédécesseur pour la relation N.

(3) Chaque nœud de K peut avoir m successeurs (m>=0) pour la relation N.

Tas

En informatique, un tas est une structure de données arborescente spéciale, chaque nœud a une valeur. Habituellement, ce que nous appelons la structure de données d'un tas fait référence à un tas binaire

. La caractéristique d'un tas est que le nœud racine a la valeur la plus petite (ou la plus grande), et les deux sous-arbres du nœud racine forment également un tas.

Table de hachage

S'il existe un enregistrement avec le mot-clé égal à K dans la structure, il doit se trouver à l'emplacement de stockage de f(K). Ainsi, les enregistrements recherchés peuvent être obtenus directement sans comparaison. La relation de correspondance f de

est appelée une fonction de hachage (Hash function), et la table construite sur la base de cette idée est une table de hachage.

Recommandations associées :

questions et réponses d'entretien Java

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!