Mécanisme et caractéristiques de la classe d'implémentation Collection souvent utilisés en Java

J'ai écrit un article "Importance de l'interface apprise de la collection Java". Étant donné que cet article s'est concentré sur l'interface de collection, cette fois, nous nous concentrerons sur les classes d'implémentation qui sont souvent utilisées et parlerons de l'implémentation interne, des fonctionnalités et de l'utilisation appropriée de chaque classe d'implémentation.

Classe d'implémentation expliquée cette fois

C'est une classe Collection que vous utiliserez probablement souvent.

• ArrayList
• LinkedList
• HashSet
• HashMap

HashMap n'est pas une collection mais une classe d'implémentation Map, mais comme il est souvent utilisé et a une forte relation avec HashSet, je vais l'expliquer avec HashSet.

Diagramme de classe

Le rôle de l'interface (Cliquez ici pour plus de détails (http://qiita.com/frost_star/items/14a12d64ccbe85a8ac3f))

ArrayList ~ Liste par tableau ~

ArrayList, comme son nom l'indique, est une implémentation de List by Array. Il a un tableau en interne et stocke, référence, insère, etc. des données dans le tableau. Par conséquent, afin de connaître les caractéristiques de ArrayList, il est nécessaire de connaître les caractéristiques du tableau.

Qu'est-ce qu'un tableau en premier lieu?

Un tableau réserve une zone contiguë en mémoire. Sa meilleure caractéristique est qu'il peut être référencé par des indices à grande vitesse. Étant donné que les zones sont continues, vous pouvez trouver l'adresse à laquelle vous souhaitez vous référer à l'aide de la formule suivante tant que vous connaissez l'adresse de départ, l'indice et la taille des données par élément.

Adresse à laquelle se référer=Adresse de départ+Indice x taille des données par un

Traitement interne de ArrayList

Puisque le tableau doit sécuriser une telle zone continue, il ne peut pas être modifié par rapport au nombre d'éléments déterminé à l'origine. Cependant, ArrayList vous permet d'ajouter des éléments de manière dynamique. ArrayList réalloue automatiquement un tableau lorsque vous ajoutez des éléments et que vous manquez de tableaux. La re-sécurisation est facile, mais en réalité c'est un processus très lourd car il traite un nouveau tableau avec 1,5 fois le nombre d'éléments que la taille d'origine et copie les données du tableau d'origine. Devenir. On dit qu'il vaut mieux déterminer la capacité initiale (argument du constructeur) dans ArrayList car cela réduit la fréquence d'exécution de ce processus de réallocation en déterminant la taille du tableau à allouer en premier.

De plus, les tableaux sont très vulnérables à l'insertion. En effet, la zone dans laquelle les données sont stockées est fixe, de sorte que le processus de déplacement de l'emplacement ne peut pas être effectué. Dans ArrayList, le processus d'insertion de données dans un emplacement arbitraire est implémenté par la méthode ʻadd`, mais cet interne réalloue également le tableau, et les données après la position d'insertion sont insérées en décalant l'index et en copiant. Nous travaillons pour faire de la place.

LinkedList ~ Liste par liste linéaire ~

Avez-vous déjà entendu parler d'une structure de données appelée liste linéaire? LinkedList est une implémentation de List basée sur la structure d'une liste linéaire.

Qu'est-ce qu'une liste linéaire?

Une liste linéaire est une structure de données qui traite les données et les liens (références à l'élément suivant) comme un seul objet (nœud), et peut gérer des chaînes de données en concaténant les nœuds.

L'avantage de cette structure de données est que vous pouvez accéder aux éléments en suivant les liens au sein de chaque nœud, tant que vous connaissez la racine (référence au premier nœud). Par conséquent, il n'est pas nécessaire que chaque nœud existe dans une zone contiguë comme un tableau. De plus, lors de l'insertion de données, il vous suffit de modifier les références des nœuds avant et après, vous n'avez donc pas besoin d'un processus de copie à grande échelle comme ArrayList.

Traitement interne de LinkedList

L'inconvénient des listes linéaires est un accès aléatoire lent. Par exemple, pour accéder au 2ème élément, suivez le lien depuis la racine de manière semi-répétée, comme [Racine] -> [0ème élément] -> [1er élément] -> [2ème élément]. Je dois y aller. Dans LinkedList, afin d'accélérer au maximum l'accès aléatoire, nous avons imaginé des moyens de rendre les liens bidirectionnels et de garder une référence au dernier élément. Cependant, plus il y a d'éléments, plus l'accès aléatoire est inévitable.

De plus, comme chaque nœud a une référence en tant que champ en plus des données, il utilise plus de mémoire qu'un ArrayList avec le même nombre d'éléments.

HashSet ~ Défini à l'aide de la valeur de hachage ~

HashSet est une classe d'implémentation de Set, contrairement aux deux listes précédentes. Autrement dit, il n'autorise pas les éléments en double et n'autorise pas l'accès aléatoire. En outre, HashSet ne préserve pas l'ordre.

Ne pas autoriser les doublons signifie que lorsque vous ajoutez un élément, vous devez déterminer si l'élément existe déjà dans l'ensemble. HashSet fait bon usage des tableaux, des listes linéaires et des valeurs de hachage pour obtenir une vérification rapide de l'existence.

Qu'est-ce qu'une valeur de hachage?

La valeur de hachage est une valeur calculée à partir des données d'origine par un calcul basé sur une formule spécifique. La même valeur de hachage peut être calculée à partir des mêmes données, mais elle est conçue de telle sorte que si les données sont légèrement différentes, les valeurs seront considérablement différentes. En outre, même si elle est irréversible et que la valeur de hachage peut être calculée à partir des données, les données ne peuvent pas être restaurées à partir de la valeur de hachage. La valeur de hachage elle-même est largement utilisée dans le monde du traitement de l'information, comme l'authentification, le contrôle de validité et le cryptage.

Valeur de hachage en Java

La valeur de hachage en Java est une valeur d'identification d'une instance, et est un entier de type int calculé par la méthode hashCode. La méthode hashCode est définie avec le type Object. Sur la base de la caractéristique que "la même valeur de hachage peut être calculée à partir des mêmes données de valeur de hachage", la même valeur de hachage doit être renvoyée entre les instances où la méthode ʻequals` renvoie true, et inversement, si les données sont différentes, elles sont aussi similaires que possible. Cela ne devrait pas être une valeur.

Traitement interne de HashSet

HashSet réalise une confirmation d'existence à grande vitesse en faisant bon usage de cette valeur de hachage. HashSet réserve un tableau de taille s lorsqu'il est instancié. Lors du stockage d'une instance ʻe, HashSet trouve d'abord la valeur de hachage avec ʻe.hashCode () puis calcule où elle doit être stockée. Trouvez le reste (reste de la division) de ʻe.hashCode () et s et stockez ʻe à cet endroit.

array[ e.hashCode() % s ] = e;

Puisque l'emplacement de stockage est calculé à partir de ʻe.hashCode ()% s`, il n'est pas nécessaire de rechercher le tableau un par un lors de la vérification de l'existence, et la valeur de hachage de l'instance donnée est calculée et l'instance est là. Vous pouvez confirmer l'existence en vérifiant s'il y en a.

En cas de collision

C'est juste une théorie idéale. En fait, la taille du tableau s est petite par rapport à la valeur de hachage, donc le phénomène qu'il y a déjà des données à l'endroit où vous avez essayé de les stocker se produit. C'est ce qu'on appelle une collision. En cas de conflit, HashSet stocke les données dans une structure de données avec des liens vers l'élément suivant comme une liste linéaire lors du stockage des données. Ensuite, en cas de collision, les données seront connectées en tant qu'élément suivant après l'élément existant. Cela vous permet de vérifier l'existence en recherchant uniquement les groupes qui ont la même valeur de ʻe.hashCode ()% s`, même s'il ne s'agit pas d'une seule référence.

redimensionner

Plus vous avez de données, plus vous risquez de vous heurter. Par exemple, si vous stockez 11 éléments de données lorsque s = 10, vous aurez certainement une collision (principe du nid de colombe). Par conséquent, lorsque le nombre de données augmente, le tableau est réalloué avec une grande capacité et les données sont réinsérées. La réinsertion des données ici n'est pas une simple copie, mais la structure des données n'est pas perturbée car la réinsertion des données est effectuée de sorte que la correspondance entre l'indice du tableau et ʻe.hashCode ()% s` ne soit pas interrompue.

remplacement de hashCode

HashSet détermine l'emplacement de stockage par la valeur de hashCode. Par conséquent, les performances de l'expression hashCode sont directement liées à la probabilité de collision du HashSet. Dans un cas extrême, si le contenu de hashCode est traité pour toujours renvoyer une constante comme return 0;, un conflit se produira à chaque fois que des données sont stockées et les performances de recherche seront inférieures à LinkedList. Par conséquent, il est important de remplacer la méthode hashCode appropriée pour la classe de l'élément que vous stockez. Cependant, il existe une forte possibilité de conflit avec le hashCode Oreore. Le mieux est d'utiliser la méthode ʻObjects.hashCode`.

Objects.hashCode(Champ 1,Champ 2,Champ 3);

Étant donné que l'argument est un argument variable, vous pouvez transmettre des données de plusieurs types d'objets. Cependant, étant donné que la valeur de hachage finale est calculée à l'aide de la valeur de hachage obtenue par hashCode de chaque champ, il est également nécessaire de remplacer la méthode hashCode dans chaque classe de champ.

HashSet et HashMap

Jusqu'à présent, nous avons parlé de l'implémentation interne de HashSet, mais c'est en fait un mensonge. Comme je l'ai écrit dans Another article, l'implémentation interne de HashSet est en fait réalisée par HashMap. Ainsi, l'implémentation interne dont nous avons parlé jusqu'à présent était en fait l'implémentation interne de HashMap. Cependant, comme l'implémentation du traitement interne ne dépend que de HashMap, le comportement est le même pour les deux.

L'histoire de HashMap

Comme pour HashMap, HashMap est une classe d'implémentation de Map qui contient des valeurs dans deux paires de données, Key et Value. La clé correspond à la partie données du HashSet expliquée précédemment. Étant donné que les données sont stockées à l'aide de la valeur de hachage de l'instance de clé, il est possible de rechercher des données à partir de la clé à grande vitesse. La valeur est simplement la valeur associée à Key et est stockée avec Key. Dans HashSet, en définissant une valeur statique comme Value, il est implémenté à l'aide de HashMap sans consommer de mémoire supplémentaire.

Comparaison de chaque classe d'implémentation

En résumé, comparons les performances de chaque classe d'implémentation en notation d'ordre. Si vous ne comprenez pas la notation d'ordre, * O * (n) est plus lent que * O * (1).

Comparaison des performances

*: Un redimensionnement peut se produire

Par comparaison, vous pouvez voir les caractéristiques de chaque classe d'implémentation. Par exemple, s'il y a beaucoup d'insertions, LinkedList, s'il y a beaucoup d'accès aléatoires, ArrayList, etc., la classe qui convient dépend du contenu de traitement, alors sélectionnez une classe d'implémentation appropriée.