Marquez-le, et en même temps, vous pouvez bien combiner HashCode () et Equals (). HashCode () n'est pas égal, il doit être différent de pouvoir déduire equals (); hashcode () est égal, equals () peut être égal ou peut être égal.
Parce que lorsque HashMap obtient, comparez d'abord HashCode, puis comparez les égaux, HashCode == && est égal, les deux sont vrais, il est donc considéré comme la même clé
1. Présentation de Hashmap:
Hashmap est une implémentation asynchrone de l'interface MAP basée sur la table de hachage. Cette implémentation fournit toutes les opérations de mappage en option et permet l'utilisation de valeurs nulles et de clés nulles. Cette classe ne garantit pas l'ordre des mappages, en particulier il ne garantit pas que l'ordre durera.
2. Structure de données de Hashmap:
Dans le langage de programmation Java, il existe deux structures de base, l'une est un tableau et l'autre est un pointeur simulé (référence). HashMap est en fait une structure de données "Liste liée", c'est-à-dire une combinaison de tableaux et de listes liées.
Comme on peut le voir sur la figure ci-dessus, la couche sous-jacente de hashmap est une structure de tableau, et chaque élément du tableau est une autre liste liée. Lorsqu'un nouveau hashmap est créé, un tableau sera initialisé.
Le code source est le suivant:
/ ** * Le tableau, redimensionné comme nécessaire. V Valeur; Entrée <K, V> Suivant;
On peut voir que l'entrée est l'élément du tableau.
3. Implémentation d'accès Hashmap:
1) Stockage:
public v put (k key, V valeur) {// hashmap permet des clés nuls et des valeurs nulles. // Lorsque la clé est nul, appelez la méthode putfornullkey et placez la valeur à la première position du tableau. if (key == null) return putFornullKey (valeur); int hash = hash (key.hashcode ()); int i = indexfor (hash, table.length); pour (entrée <k, v> e = table [i]; e! = null; e = e.next) {objet k; || key.equals (k))) {v oldvalue = e.value; qu'il n'y a pas encore de saisie. modCount ++; // ajouter la clé et la valeur à l'index i. Addentry (hachage, clé, valeur, i); D'après le code source ci-dessus, nous pouvons voir que lorsque nous mettons l'élément dans HashMap, nous recalculons d'abord la valeur de hachage en fonction du code de hash de la clé, et en fonction de la valeur de hachage, la position de cet élément dans le tableau (c'est-à-dire, indiqueur ), si la table Ceux sont placés à la fin de la chaîne. S'il n'y a pas d'élément à cette position dans le tableau, mettez l'élément directement à cette position dans le tableau.
La méthode Addentry (hachage, clé, valeur, i) place la paire de valeurs clés à l'indice I de la table de tableau en fonction de la valeur de hachage calculée. Addentry est une méthode d'autorisations d'accès aux packages fournies par HashMap, le code est le suivant:
void Addentry (int hash, k key, v valeur, int bucketIndex) {// Obtenez l'entrée sur l'entrée d'index BucketIndex spécifiée <k, v> e = table [bucketIndex]; Index et laissez le nouveau point d'entrée à la table d'entrée d'origine [BucketIndex] = nouvelle entrée <k, v> (hachage, clé, valeur, e); (Size ++> = seuil) // Développez la longueur de l'objet de table pour deux fois l'original. redimensionner (2 * table.Length); Lorsque le système décide de stocker la paire de valeurs clés dans le hashmap, la valeur de l'entrée n'est pas du tout prise en compte, et il calcule et détermine simplement l'emplacement de stockage de chaque entrée en fonction de la clé. Nous pouvons traiter complètement la valeur de la collection de cartes comme une pièce jointe à la clé.
La méthode du hachage (int h) recalcule le hachage une fois basé sur le code de hash de la clé. Cet algorithme ajoute des calculs élevés pour prévenir les conflits de hachage provoqués lorsque le faible bit reste inchangé et lorsque le haut bit change.
hachage statique (int h) {h ^ = (h >>> 20) ^ (h >>> 12); Nous pouvons voir que pour trouver un élément dans Hashmap, nous devons trouver la position correspondante dans le tableau en fonction de la valeur de hachage de la clé. Comment calculer cette position est l'algorithme de hachage. Comme mentionné précédemment, la structure de données de HashMap est une combinaison de tableaux et de listes liées, donc bien sûr, nous espérons que les positions de l'élément dans ce hashmap devraient être réparties autant que possible, de sorte que le nombre d'éléments à chaque position soit uniquement un. Efficacité de la requête.
Pour tout objet donné, tant que sa valeur de retour HashCode () est la même, la valeur de code de hachage calculée par le programme appelant la méthode de hash (int h) est toujours la même. La première chose à laquelle nous pensons est de modulo la valeur de hachage à la longueur du tableau, de sorte que la distribution des éléments est relativement uniforme. Cependant, l'opération "modulo" consomme beaucoup, et ceci se fait dans HashMap: appelez la méthode indexfor (int h, inty longueur) pour calculer quel index l'objet doit être stocké dans le tableau de table.
Le code de la méthode indexfor (int h, int le long) est le suivant:
static int indexfor (int h, int le long) {return h & (longueur-1);Cette méthode est très intelligente. termes de vitesse. Dans le constructeur HashMap, il y a le code suivant:
Capacité int = 1; while (capacité <initialCapacity) Capacité << = 1;
Ce code garantit que la capacité de Hashmap est toujours à la puissance n de 2 pendant l'initialisation, c'est-à-dire que la longueur du tableau sous-jacent est toujours à la puissance n de 2.
Lorsque la longueur est toujours à la puissance N de 2, l'opération H & (Longueur-1) est équivalente à la longueur du modulo, c'est-à-dire la longueur de H%, mais et a une efficacité plus élevée que%.
Cela semble très simple, mais c'est en fait assez mystérieux.
En supposant que les longueurs de tableau sont de 15 et 16, et les codes de hachage optimisés sont respectivement de 8 et 9, puis le résultat après l'opération est le suivant:
H & (Table.Length-1) Hash Table.Length-1
8 & (15-1): 0100 et 1110 = 0100
9 & (15-1): 0101 et 1110 = 0100
-------------------------------------------------- -------------------------------------------------- ---------------------------- ---------------------- -------------------------------------------------- -------------------------------------------------- ------ -------------------------------------------- -------------------------------------------------- ----------------------------------
8 & (16-1): 0100 et 1111 = 0100
9 & (16-1): 0101 et 1111 = 0101
Comme on peut le voir à partir de l'exemple ci-dessus: lorsqu'ils sont "as" avec 15-1 (1110), le même résultat est produit, c'est-à-dire qu'ils seront positionnés à la même position dans le tableau, ce qui crée une collision, 8 et 9 sera placé à la même position dans le tableau pour former une liste liée. En même temps, nous pouvons également constater que lorsque la longueur du tableau est de 15, la valeur de hachage sera "comme" avec 15-1 (1110), le dernier bit sera toujours 0 et 0001, 0011, 0101, 1001 , 1011, 0111, 0111, 1101 ne peuvent jamais stocker des éléments, et l'espace est beaucoup gaspillé. Les chances de collision sont encore augmentées et la lente efficacité de la requête! Lorsque la longueur du tableau est de 16, c'est-à-dire lorsqu'elle est à la puissance n de 2, la valeur sur chaque bit du nombre binaire obtenu par 2N-1 est 1, ce qui rend le bit faible de la somme du hachage d'origine lorsque C'est et sur le bit bas, de sorte que le bit bas du hachage de somme obtenu est le même, couplé à la méthode de hachage (int h) optimise davantage le code de hash de la clé et ajoute des calculs élevés, de sorte que seulement deux valeurs De la même valeur de hachage sera placée à la même position dans le tableau pour former une liste liée.
Par conséquent, lorsque la longueur du tableau est de n pouvoirs de 2, la probabilité que différentes clés puissent calculer le même index est plus petite, de sorte que les données seront distribuées uniformément sur le tableau, ce qui signifie que la probabilité de collision est petite, relative, à la requête au niveau de Cette fois, vous n'avez pas à traverser la liste liée à un certain endroit, donc l'efficacité de la requête sera plus élevée.
Selon le code source de la méthode de put ci-dessus, lorsque le programme essaie de mettre une paire de valeurs de clé dans un hashmap, le programme détermine d'abord l'emplacement de stockage de l'entrée en fonction de la valeur de retour hashcode () de la clé: si la Clé de deux entrées La valeur de retour HashCode () est la même, et leur emplacement de stockage est le même. Si les clés de ces deux entrées renvoient True à travers la comparaison égale, la valeur de l'entrée nouvellement ajoutée remplacera la valeur de l'entrée d'origine dans la collection, mais que la clé ne remplacera pas. Si les clés de ces deux entrées reviennent fausses par rapport à la comparaison égale, l'entrée nouvellement ajoutée formera une chaîne d'entrée avec l'entrée d'origine dans la collection, et la nouvelle entrée ajoutée est située à la tête de la chaîne d'entrée - les détails sont continués à voir La description de la méthode Addentry ().
2) Lire:
public v get (objet clé) {if (key == null) getFornullkey (); int hash = hash (key.hashcode ()); . Retour E.Value;} Retour null;} Avec l'algorithme de hachage stocké ci-dessus comme base, il est facile de comprendre ce code. À partir du code source ci-dessus, nous pouvons voir que lors de l'obtention d'un élément dans HashMap, calculez d'abord le code de hash de la clé, trouvez un élément à la position correspondante dans le tableau, puis trouvez l'élément requis dans la liste liée de la position correspondante à travers la méthode égale de la clé.
3) Pour résumer, HashMap traite la valeur clé dans son ensemble en bas, et cet ensemble est un objet d'entrée. Le hashmap sous-jacent utilise un tableau d'entrée [] pour stocker toutes les paires de valeurs clés. La méthode égale.
4. Rédige de Hashmap (Rehash):
Comme il y a de plus en plus d'éléments dans le hashmap, les chances de conflit de hachage augmentent et supérieures, car la durée du tableau est fixe. Par conséquent, afin d'améliorer l'efficacité de la requête, le tableau de hashmap doit être étendu. apparaît: les données du tableau d'origine doivent être recalculées et placées dans le nouveau tableau, qui est redimensionné.
Alors, quand Hashmap sera-t-il élargi? Lorsque le nombre d'éléments dans le hashmap dépasse la taille du tableau * LoadFactor, le tableau est élargi. C'est-à-dire, par défaut, la taille du tableau est de 16. Ensuite, lorsque le nombre d'éléments dans Hashmap dépasse 16 * 0,75 = 12, la taille du tableau est étendue à 2 * 16 = 32, c'est-à-dire le double de la taille, puis le recalculer. .
5. Paramètres de performance Hashmap:
Hashmap contient les constructeurs suivants:
Hashmap (): construire un hashmap avec une capacité initiale de 16 et un facteur de charge de 0,75.
Hashmap (int initialCapacity): construire un hashmap avec la capacité initiale et un facteur de charge de 0,75.
Hashmap (int initialCapacity, float chargefactor): crée un hashmap avec la capacité initiale spécifiée et le facteur de charge spécifié.
Le constructeur de base de HashMap, HashMap (int initialCapacity, Float LoadFactor), a deux paramètres, ils sont la capacité initiale initiale et le facteur de charge chargefactor.
Capacité initiale: la capacité maximale de Hashmap, c'est-à-dire la longueur du réseau sous-jacent.
ChargeFactor: Le facteur de charge chargefacteur est défini comme: le nombre réel d'éléments d'une table de hachage (n) / la capacité d'une table de hachage (M).
Le facteur de charge mesure le degré d'utilisation d'un espace de table de hachage. Pour les tables de hachage utilisant la méthode de la liste liée, le temps moyen pour trouver un élément est O (1 + a). Le facteur de charge est trop si petit, alors les données de la table de hachage seront trop rares, provoquant un grave gaspillage d'espace.
Dans la mise en œuvre de HashMap, la capacité maximale de HashMAP est déterminée par le champ de seuil:
La copie de code est la suivante:
threshold = (int) (capacité * chargefactor);
Sur la base de la formule de définition du facteur de charge, on peut voir que le seuil est le nombre maximal d'éléments autorisés en fonction de la charge et de la capacité. Le facteur de charge par défaut 0,75 est un choix équilibré pour l'efficacité spatiale et temporelle. Lorsque la capacité dépasse cette capacité maximale, la capacité de hashmap redimensionnée est le double de la capacité:
if (size ++> = threshold) redimensider (2 * table.length);
6. Mécanisme de faillite:
Nous savons que java.util.hashmap n'est pas un thread-safe, donc si d'autres threads modifient la carte pendant le processus d'utilisation de l'itérateur, une conception de laModification concurrente sera lancée, qui est la stratégie dite d'échec.
Cette stratégie est implémentée dans le code source via le champ ModCount. ITERATOR'S HAUTSMODCOUNT.
Hashiterator () {attendumodCount = modCount; ; Pendant le processus d'itération, déterminez si le modCount et le ModCount attendu sont égaux.
Notez que ModCount est déclaré volatil, garantissant la visibilité des modifications entre les threads.
Entrée finale <k, v> nextEntry () {if (modCount! = attendModCount) New concurrentModificationException (); Dans l'API de Hashmap, il est indiqué:
Les itérateurs renvoyés par la "méthode de vue de la collecte" de toutes les classes de hashmap échouent rapidement: une fois l'itérateur créé, si le mappage est modifié à partir de la structure, sauf si elle est transmise par la méthode de suppression de l'itérateur, toute autre manière. Jetez une conception de laModification concurrent si la modification est effectuée. Par conséquent, face à des modifications simultanées, l'itérateur échouera bientôt complètement sans risquer un comportement incertain arbitraire à des moments incertains à l'avenir.
Notez que le comportement de défaillance rapide de l'itérateur ne peut pas être garanti. Fast Fail Iterator lance une conception concurrente-motification lorsqu'elle fonctionne le mieux. Par conséquent, il est faux d'écrire des programmes qui reposent sur cette exception, et la bonne façon est: le comportement de défaillance rapide de l'itérateur ne doit être utilisé que pour détecter les erreurs de programme.