―Hashmap--
Avantages: une vitesse de requête super rapide et des structures de données qui peuvent atteindre l'O (1) la complexité du temps est le hashmap. Données de stockage dynamiques de longueur variable (par rapport aux tableaux).
Inconvénients: la valeur de hachage doit être calculée en plus, et si elle n'est pas gérée correctement, elle prendra un espace supplémentaire.
―Comment utiliser Hashmap -
Habituellement, nous utilisons Hashmap comme suit
Map <Integer, string> maps = new HashMap <Integer, String> (); maps.put (1, "a"); maps.put (2, "b");
Le code ci-dessus crée un nouveau hashmap et insère deux données. Les types de données de base ne sont pas acceptés ici pour faire K et V.
Si vous écrivez ceci, il y aura des problèmes:
Map <int, double> maps = new hashmap <int, double> ();
Pourquoi utilisons-nous de cette façon? Veuillez consulter le code source:
classe publique Hashmap <k, v> étend AbstractMap <k, v> implémente la carte <k, v>, clonable, sérialisable
Il s'agit de la définition de la classe d'implémentation HashMap.
―HashMap est une structure de données de longueur de variable dynamique -
Lorsque vous utilisez HashMap, afin d'améliorer l'efficacité de l'exécution, nous définissons souvent la capacité d'initialisation de HashMap:
Map <string, string> rm = new hashmap <string, string> (2)
Ou utilisez des cartes de classe d'outils de Guava pour créer facilement une collection et initialiser la valeur avec la taille appropriée.
Map <string, object> map = maps.newhashmapwithexpectedSize (7);
Alors pourquoi l'utiliser comme ça? Regardons leur constructeur source.
Constructeur sans paramètres:
public hashmap () {this.loadfactor = default_load_factor; threshold = (int) (default_initial_capacity * default_load_factor); table = new entrée [default_initial_capacity]; init (); } Public Hashmap () {
this.loadfactor = default_load_factor;
threshold = (int) (default_initial_capacity * default_load_factor);
table = new entrée [default_initial_capacity];
init ();
}
/ ** * construit une <tt> hashmap </ tt> vide avec la capacité initiale * spécifiée et le facteur de charge par défaut (0,75). * * @param InitialCapacity La capacité initiale. * @throws illégalargumentException si la capacité initiale est négative. * / public hashmap (int initialCapacity) {this (initialCapacity, default_load_factor); }Explication des noms:
Default_load_factor // Facteur de chargement par défaut, 0,75 s'il n'est pas spécifié. Default_Initial_Capacity // La capacité d'initialisation par défaut, la valeur par défaut est 16 seuil // La valeur de seuil (YU) est calculée en fonction du facteur de charge et de la capacité d'initialisation. <Span Style = "Color: RGB (54, 46, 43); Font-Family:" Microsoft Yahei ";"> Le seuil signifie que lorsque la taille de Hashmap est supérieure au seuil, l'opération de redimension sera effectuée.
Nous savons donc que si nous appelons le constructeur sans paramètre, nous obtiendrons un tableau de 16 capacités.
La question est donc de savoir si la capacité initiale ne suffit pas?
Les tableaux sont de longueur fixe, comment utiliser des données de longueur fixe pour représenter des données de longueur incertaine? La réponse est d'en trouver une plus longue, mais elle réduit l'efficacité lorsque les redimensions. Nous recommandons donc que HashMap ait une capacité fiable lors de l'initialisation.
«HashMap Put Method ll
public v put (k key, v valeur) {if (key == null) // Si la clé est vide, une différence entre hashmap et hashtable renvoie putFornullKey (valeur); int hash = hash (key.hashcode ()); // cadre la valeur de hachage en fonction du code de hash de la clé int i = indexFor (hash, table.length); // cadre l'indice du tableau à placer en fonction de la valeur de hachage pour (entrée <k, v> e = table [i]; e! = Null; e = e.next) {// Le tout pour la boucle implémente que si k existe, puis remplace v objet k; if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldValue = e.Value; e.Value = valeur; e.recordAccess (this); Retour OldValue; }} modCount ++; // Counter Addentry (hachage, clé, valeur, i); // Ajouter à l'arrêt Retour null; }Si les données insérées dépassent la capacité existante, elle sera exécutée
Addentry (hachage, clé, valeur, i);
void Addentry (int hash, k key, v valeur, int bucketIndex) {entrée <k, v> e = table [bucketIndex]; table [bucketIndex] = nouvelle entrée <k, v> (hachage, clé, valeur, e); if (size ++> = threshold) <span style = "couleur: # ff0000;"> <strong> redimensit (2 * table.length);}Ici, si le seuil de taille actuel ++> s'affiche, la taille actuelle sera étendue deux fois et redimensionner (2 * Table.Length) sera exécuté. Alors, comment se développent-ils?
void Resize (int newCapacity) {entrée [] oldTable = table; int oldcapacity = oldTable.length; if (oldcapacity == maximum_capacity) {threshold = Integer.max_value; retour; } Entrée [] newtable = new Entry [newCapacity]; <span style = "Color: RGB (51, 51, 51); Font-Family: Arial;"> Nouveau un nouveau tableau, </span> <strong> <span style = "Color: # ff0000;"> Transfer (NewTable); </span> </strong> // transférer le tableau vers un nouveau tableau Table = NewTable; threshold = (int) (newCapacity * loadFactor); // recalcule la capacité}Comment le transfert du tableau de transfert est-il transféré?
void transfert (entrée [] newtable) {entrée [] src = table; int newcapacity = newtable.length; pour (int j = 0; j <src.length; j ++) {entrée <k, v> e = src [j]; if (e! = null) {src [j] = null; do {entrée <k, v> next = e.next; int i = <strong> <span style = "couleur: # ff0000;"> indexFor (e.hash, newcapacity); // recalcule l'indice en fonction de la capacité de valeur de hachage </span> </strong> e.next = newtable [i]; newtable [i] = e; e = suivant; } while (e! = null); }}}«Le nombre d'exécutions supplémentaires de l'expansion de Hashmap-
Donc, si nous voulons ajouter un hashmap de 1000 éléments, si nous utilisons la valeur par défaut, combien de calculs supplémentaires ai-je besoin pour calculer?
Quand il est supérieur à 16 * 0,75 = 12, il doit être recalculé 12 fois
Lorsqu'il est supérieur à 16 * 2 * 0,75 = 24, 24 calculs supplémentaires sont nécessaires.
...
Lorsqu'il est supérieur à 16 * n * 0,75 = 768, 768 calculs supplémentaires sont nécessaires.
Nous avons donc calculé 12 + 24 + 48 +… + 768 fois dans le processus d'extension
Par conséquent, il est fortement recommandé de spécifier manuellement la taille initiale si nous connaissons la portée du projet comme ceci:
Map <Integer, String> Maps = new HashMap <Integer, String> (1000);
Résumé: C'est pourquoi l'efficacité d'exécution de HashMAP est gravement réduite si elle dépasse la capacité initiale pendant l'utilisation.
Ce qui précède concerne l'utilisation de HashMap dans cet article sur l'analyse du code source Java, j'espère que cela sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!