Interface cartographique en Java

Qu'est-ce que l'interface de carte Java

L'interface Java Map fait partie du framework Java Collection, mais ce n'est pas un sous-type de l'interface Collection. Il se comporte donc différemment par rapport, par exemple, aux listes ou à d'autres objets de collection. Chaque élément de Map<Key, Value> représente une paire clé-valeur. La clé et la valeur sont des objets. Toutes les clés d'une carte particulière sont uniques, tandis que les valeurs ne le sont pas, elles peuvent donc être dupliquées. Vous pouvez penser à Map en Java comme une sorte de dictionnaire ou de catalogue de boutique en ligne, où vous pouvez trouver n'importe quel article en utilisant son index unique. La clé est un identifiant unique de la valeur dans une Map. Par exemple, dans Map<String, Item> String est l'identifiant d'un article de la boutique en ligne. Selon les documentations, Map a les sous-interfaces suivantes :

Reliures ;

ConcurrentMap<K,V> ;

ConcurrentNavigableMap<K,V> ;

LogicalMessageContext ;

MessageContext ;

CarteNavigable<K,V> ;

SOAPMessageContext ;

Carte triée<K,V> .

Et implémente les classes :

RésuméCarte
Les attributs
Fournisseur d'authentification
ConcurrentHashMapConcurrentHashMap
ConcurrentSkipListMap
EnumMap
HashMap
Table de hachage
IdentityHashMapIdentityHashMap
LinkedHashMap
PrinterStateReasons
Propriétés
Fournisseur
Conseils de rendu
SimpleBindings
Prise en charge des données tabulaires
TreeMap
UIDefaults
WeakHashMap

Java AbstractMap est une classe abstraite qui implémente la plupart de l'interface Map.
Java HashMap est une structure de données permettant de stocker des paires clé-valeur à l'aide d'une table de hachage.
Java TreeMap est une structure de données permettant d'utiliser un arbre, c'est à dire d'afficher avec des clés triées.
WeakHashMap pour utiliser une table de hachage avec des clés faibles, afficher avec des valeurs pouvant être supprimées par le ramasse-miettes si elles ne sont plus utilisées.
LinkedHashMap est une carte avec l'ordre d'ajout des éléments, permet l'itération dans l'ordre d'insertion.
EnumMap étend la classe AbstractMap pour une utilisation avec les clés enum.

IdentityHashMap utilise la vérification d'équivalence référentielle lors de la comparaison de documents, le mappage avec des clés comparées à l'aide de l'opération == au lieu de la méthode equals ()

Ici, nous nous intéressons aux implémentations les plus populaires de Map Interface : HashMap, TreeMap et LinkedHashMap. Soit dit en passant, l'ordre des éléments de la carte dépend des implémentations spécifiques. Disons que TreeMap et LinkedHashMap ont un ordre prévisible des éléments, contrairement à HashMap.

Méthodes cartographiques

Les principales opérations de toute carte sont l'insertion, la suppression et la recherche d'éléments.

public Object put(Object key, Object value) insère un élément dans la carte.
public void putAll(Map map) insère la carte spécifiée à l'intérieur de la carte.
public Object remove(Object key) supprime une entrée en fonction de la clé spécifiée.
public Object get(Object key) renvoie la valeur de la clé spécifiée.
public boolean containsKey(Object key) recherche la clé spécifiée à partir de cette carte
public Set keySet() renvoie une vue Set qui contient toutes les clés
public Set entrySet() renvoie une vue Set avec toutes les clés et valeurs.

Qu'est-ce que HashMap

Qu'est-ce qu'HashMap ? C'est l'implémentation la plus populaire de l'interface Map<Key,Value>. Cette structure de données est basée sur le principe du hachage.

Le grand principe du travail de HashMap : le hachage

Pour comprendre ce qu'est un hashmap et comment il fonctionne, parlons d'abord du hachage et des fonctions de hachage. Une fonction de hachage n'est qu'une fonction au sens mathématique. Il y a donc une valeur d'entrée (un objet, une donnée) et la fonction la convertit en utilisant une règle appropriée en valeur de sortie - un hachage. Assez souvent, le hachage est un nombre hexadécimal d'une longueur appropriée. Les règles des processus de conversion peuvent être différentes, mais elles sont soumises aux principes suivants :

Une entrée particulière (objet) a un code de hachage particulier.
Si deux objets sont égaux, leurs codes de hachage sont également égaux. L'inverse n'est pas vrai.
Si les codes de hachage sont différents, les objets ne sont certainement pas égaux.
Parfois, différents objets peuvent avoir le même code de hachage. Il s'agit d'un événement très improbable, appelé "collision" et une fonction de hachage de bonne qualité devrait minimiser la probabilité de collisions.

En Java, chaque objet a un code de hachage. Il est calculé par la méthode hashCode de la classe Object, classe parentale de tous les objets Java. Habituellement, les développeurs remplacent cette méthode pour leurs propres classes ainsi que les méthodes equals qui lui sont associées.

HashMap : comment ça marche

Donc Class HashMap<K,V> car chaque implémentation de Map se compose de clés et de valeurs. Il stocke les clés en utilisant les principes de hachage. À l'intérieur des paires clé-valeur HashMap sont stockées dans des "buckets", ces buckets construisent ensemble une "table", un tableau interne de listes liées et sa taille initiale est de 16. HashMap en Java utilise le hashcode de la clé pour déterminer un seau où la paire clé/valeur doit être mappée : la fonctionnalité délicate de HashMap est que chaque cellule (seau) de la table [] conserve non seulement une paire mais plusieurs. Ils ne sont pas stockés en tant qu'objet explicite (comme LinkedList), mais en tant que chaîne implicite. La chaîne est créée du fait que chaque paire stocke un lien vers la paire suivante. Autrement dit, toutes les paires HashMap sont dispersées sur 16 chaînes. Lorsque vous mettez une nouvelle paire dans la table, le hachage de la clé est pris en compte. Ce hachage n'est pas une fonction de code de hachage intégrée à l'objet clé. Il est considéré comme étant compris entre 0 et 15. La paire est ajoutée à la chaîne de paires stockées dans le bucket avec l'index de hachage. Cette approche nous donne une accélération de la recherche. Lors de la recherche d'une paire par clé, il n'est pas nécessaire de parcourir tout le tableau. Le hachage de la clé est pris en compte et seule la chaîne stockée dans la cellule avec l'index de hachage est vérifiée. S'il y a trop de paires dans le HashMap, les chaînes deviennent trop longues. Ensuite, la taille du tableau augmente, le hachage de tous les objets stockés est recalculé et ils sont dispersés le long de nouvelles chaînes.

Déclaration HashMap

Si vous allez dans le code de la classe HashMap, vous trouverez la déclaration suivante :

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable

Où K est le type de clés maintenues par cette carte et V - le type de valeurs mappées. Voici un exemple de déclaration HashMap avec une clé Integer et une valeur String dans votre code :

HashMap<Integer, String> myHashMap = new HashMap<Integer, String>();

Méthodes HashMap

Voici la liste des méthodes HashMap.

Object get(Object key) renvoie la valeur de la clé spécifiée ;
L'objet put(Key k, Value v) insère un mappage de valeur clé dans la carte ;
Object remove(Object key) supprime le mappage de la clé spécifiée de ce mappage s'il est présent ;
void clear() supprime toutes les paires clé-valeur du HashMap ;
Object clone() renvoie une copie superficielle de cette instance de HashMap sans cloner les clés et les valeurs ;
boolean containsKey(Object key) renvoie true si la clé spécifiée est trouvée dans la carte, false si ce n'est pas le cas ;
boolean containsValue(Object Value) renvoie true si la clé spécifiée est trouvée dans la carte, false si ce n'est pas le cas ;
boolean isEmpty() renvoie true si la carte est vide, false sinon ;
Set keySet() renvoie l'ensemble des clés extraites de la carte ;
int size() renvoie la quantité de mappage clé-valeur ;
Collection values() renvoie une collection des valeurs de la carte ;
Object remove(Object key) supprime la paire clé-valeur pour la clé spécifiée ;
void putAll(Map m) copie tous les éléments de la carte sur l'autre carte.

Exemple Java HashMap

Créons un programme avec Java HashMap Example pour montrer comment cela fonctionne :

import java.util.HashMap;
import java.util.Map;
import java.util.Iterator;
import java.util.Set;

public class HashMap {

   public static void main(String[] args) {

       {

           // HashMap declaration
           HashMap<Integer, String> myHashMap = new HashMap<Integer, String>();

           //Adding elements into HashMap
           myHashMap.put(7, "Johnny");
           myHashMap.put(8, "Ivy");
           myHashMap.put(1, "Rick");
           myHashMap.put(4, "Stan");
           myHashMap.put(3, "Kyle");

           //print out the map content using Iterator
           Set set = myHashMap.entrySet();
           Iterator iterator = set.iterator();
           while (iterator.hasNext()) {
               Map.Entry mapEntry = (Map.Entry) iterator.next();
               System.out.print("key: " + mapEntry.getKey() + " value: ");
               System.out.println(mapEntry.getValue());
           }
           System.out.println("get an element from myHashMap via key and print the value out:");
           System.out.println(myHashMap.get(8));
           //print out hashMap on standard way:
           System.out.println(myHashMap);

           // Get values based on key
           String var = myHashMap.get(2);
           //here we'll get null, we don't have such a key
           System.out.println("Value with key 2: " + var);
           var = myHashMap.get(7);
           System.out.println("Value with key 7: " + var);

           // Remove values based on key
           myHashMap.remove(4);
           System.out.println("myHashMap after removing element:");
           System.out.println(myHashMap);
           myHashMap.clear();
           System.out.println("myHashMap after total clearing:");
           System.out.println(myHashMap);
       }

   }
}

Le résultat de l'exécution du programme :

key: 1 value: Rick
key: 3 value: Kyle
key: 4 value: Stan
key: 7 value: Johnny
key: 8 value: Ivy
get an element from myHashMap via key and print the value out:
Ivy
{1=Rick, 3=Kyle, 4=Stan, 7=Johnny, 8=Ivy}
Value with key 2: null
Value with key 7: Johnny
myHashMap after removing element:
{1=Rick, 3=Kyle, 7=Johnny, 8=Ivy}
myHashMap after total clearing:
{}

TreeMap

TreeMap en Java implémente également l'interface Map<Key,Value>, mais elle est basée sur une structure de données arborescente rouge-noire. Un arbre se compose de "nœuds" et de lignes qui relient les nœuds - les branches". Le nœud "racine" est au sommet de l'arbre. À partir de la racine, il peut y avoir des branches et des nœuds. C'est une structure hiérarchique, vous pouvez penser à ces nœuds comme "enfants" de la racine. Le nœud enfant peut avoir ses propres enfants - nœuds inférieurs. Les nœuds sans enfants sont appelés "nœuds finaux" ou "feuilles". Un arbre binaire est un arbre, où chaque nœud a zéro, un L'arbre de recherche binaire est une structure, où chaque nœud interne stocke une clé, et parfois une valeur associée, et a deux sous-arbres distincts ("gauche" et "droite"). Un arbre de recherche binaire auto-équilibré est un arbre de recherche binaire basé sur des nœuds qui maintient automatiquement sa hauteur (nombre maximal de niveaux sous la racine) petite face aux insertions et suppressions d'éléments arbitraires. Un arbre rouge-noir est un arbre binaire équilibré avec les propriétés :

Chaque nœud est soit rouge soit noir
La racine est toujours noire
Chaque feuille est un nœud NIL (sorte de vide, nul) et il est noir
Si un nœud est rouge, ses enfants sont définitivement noirs.
Chaque chemin simple d'un nœud à une feuille descendante contient le même nombre de nœuds noirs.

Fonctionnalités d'un TreeMap

Un TreeMap utilise une structure de données arborescente pour stocker les clés en tant que nœuds et trie les clés à l'aide de l'algorithme Red-Black Tree. Ainsi, TreeMap conserve ses entrées triées selon l'ordre naturel de ses clés. Pour les nombres, naturel est l'ordre croissant, pour les chaînes - l'ordre alphabétique. Vous pouvez utiliser un comparateur si vous avez besoin de changer la logique de commande. Le tri des objets de manière naturelle est un gros avantage de TreeMap, ainsi que la recherche de certains objets en utilisant différents filtres et conditions.

Méthodes TreeMap

Object get(Object key) renvoie la valeur de la clé correspondante ;
Object put(Object key, Object value) insère un mappage dans une carte ;
Object remove(Object key) supprime le mappage de cette clé si le TreeMap le contient ;
boolean containsKey(Object key) renvoie true si cette carte contient un mappage pour la clé spécifiée ;
boolean containsValue(Object value) renvoie true si le TreeMap mappe une ou plusieurs clés à la valeur spécifiée ;
L'objet firstKey() renvoie la première clé actuellement dans la carte triée ;
L'objet lastKey() renvoie la dernière clé actuellement dans la carte triée ;
void putAll(Map map) copie tous les mappages de la carte spécifiée vers la carte ;
Set entrySet() renvoie une vue d'ensemble des mappages
int size() renvoie la quantité de mappages clé-valeur
Collection values() renvoie une vue de collection des valeurs
Object clone() renvoie une copie superficielle du TreeMap
void clear() supprime tous les mappages du TreeMap
SortedMap headMap(Object key_value) renvoie une vue de la partie de la carte inférieure au paramètre key_value
Set keySet() renvoie une vue Set des clés contenues dans le treemap
SortedMap subMap(K fromKey, K toKey) renvoie une vue de la partie de cette carte dont les clés vont de fromKey, inclus, à toKey, exclusif
L'objet firstKey() renvoie la première clé du TreeMap.

Exemple de TreeMap

import java.util.TreeMap;
import java.util.Set;
import java.util.Iterator;
import java.util.Map;

public class TreeMapExample {

   public static void main(String args[]) {

       //TreeMap declaration
       TreeMap<Integer, String> myTreeMap = new TreeMap<Integer, String>();

       //put elements to TreeMap
       myTreeMap.put(1, "Stuart");
       myTreeMap.put(23, "Michael");
       myTreeMap.put(7, "Johnny");
       myTreeMap.put(5, "Ivy");
       myTreeMap.put(2, "Alex");

       //Display and print out myTreeMap using Iterator
       Set set = myTreeMap.entrySet();
       Iterator iterator = set.iterator();
       while (iterator.hasNext()) {
           Map.Entry myEntry = (Map.Entry) iterator.next();
           System.out.print("key: " + myEntry.getKey() + " value: ");
           System.out.println(myEntry.getValue());
       }
       //TreeMap printed in classical way
       System.out.println(myTreeMap);
       //removing an element with the key =2
       myTreeMap.remove(2);
       //myTreeMap after removing:
       System.out.println(myTreeMap);
   }
}

Le résultat de l'exécution du programme :

key: 1 value: Stuart
key: 2 value: Alex
key: 5 value: Ivy
key: 7 value: Johnny
key: 23 value: Michael
{1=Stuart, 2=Alex, 5=Ivy, 7=Johnny, 23=Michael}
{1=Stuart, 5=Ivy, 7=Johnny, 23=Michael}

LinkedHashMap

LinkedHashMap est une structure de données qui combine des listes liées et des cartes de hachage. En effet, LinkedHashMap étend la classe HashMap et implémente l'interface Map, mais qu'en est-il des listes chaînées ? La déclaration de LinkedHashMap :

Map <Integer, String> linkedHashMap = new LinkedHashMap <Integer, String>();

Ce nouveau linkedHashMap hérite des propriétés de HashMap (telles que table, loadFactor, threshold, size, entrySet), obtient également deux propriétés spéciales :

header est la tête d'une liste doublement chaînée. Lors de l'initialisation, il s'indique
accessOrder indique comment accéder aux éléments à l'aide de l'itérateur. Si vrai, dans l'ordre du dernier accès. Si false, l'accès se fera dans l'ordre dans lequel les éléments ont été insérés.

Cette liste chaînée définit l'ordre des itérations. Habituellement, c'est l'ordre d'insertion des clés dans la carte.

Méthodes LinkedHashMap

Object get(Object key) renvoie la valeur à laquelle la clé spécifiée est mappée, ou null si cette carte ne contient aucun mappage pour la clé
void clear() supprime tous les mappages de la carte.
boolean containsKey(Object key) renvoie true si l'élément spécifié est mappé par une ou plusieurs clés
booléen removeEldestEntry(Map.Entry plus ancien) renvoie vrai si la carte supprime son entrée la plus ancienne de la carte
Set<Map.Entry<K,V>> entrySet() renvoie une vue Set des mappages contenus dans cette carte
void forEach(BiConsumer<? super K,? super V> action) exécute l'action donnée pour chaque entrée de cette carte jusqu'à ce que toutes les entrées aient été traitées ou que l'action lève une exception.
Object getOrDefault(Object key, V defaultValue) renvoie la valeur à laquelle la clé spécifiée est mappée. Si la carte ne contient pas de mappage pour la clé, renvoie defaultValue.
Set<K> keySet() renvoie une vue Set des clés contenues dans la carte
boolean removeEldestEntry(Map.Entry<K,V> eldest) renvoie vrai si cette carte doit supprimer son entrée la plus ancienne
void replaceAll(BiFunction<? super K,? super V,? extend V> function) remplace chaque valeur d'entrée par le résultat de l'appel de la fonction donnée sur cette entrée jusqu'à ce que toutes les entrées aient été traitées ou que la fonction lève une exception.
Collection<v>values() renvoie une vue Collection des valeurs contenues dans la carte

Exemple LinkedHashMap

import java.util.LinkedHashMap;
import java.util.Set;
import java.util.Iterator;
import java.util.Map;
   public class HashLinkedListExample {
       public static void main(String args[]) {
           // LinkedHashMap Declaration
           LinkedHashMap<Integer, String> myLinkedHashMap =
                   new LinkedHashMap<Integer, String>();

           //Adding elements into LinkedHashMap
           myLinkedHashMap.put(7, "Johnny");
           myLinkedHashMap.put(12, "Rick");
           myLinkedHashMap.put(1, "Kyle");
           myLinkedHashMap.put(5, "Percy");
           myLinkedHashMap.put(85, "Sebastian");

           // Generate a Set of entries
           Set set = myLinkedHashMap.entrySet();

           // Display and print out the nodes  of LinkedHashMap
           Iterator iterator = set.iterator();
           while(iterator.hasNext()) {
               Map.Entry me = (Map.Entry)iterator.next();
               System.out.print("key: "+ me.getKey() +
                       " value: "+me.getValue()+"\n");
           }
           //print out HashLinkedMap on standard way:
           System.out.println(myLinkedHashMap);
           myLinkedHashMap.put(21, "Ivy");
           System.out.println(myLinkedHashMap);
           myLinkedHashMap.remove(12);
           System.out.println(myLinkedHashMap);
           myLinkedHashMap.put(12, "Ronny");
           System.out.println(myLinkedHashMap);
           myLinkedHashMap.put(1, "Stan");
           System.out.println(myLinkedHashMap);
       }
   }

Ici, nous créons un nouveau LinkedHashMap, en ajoutant cinq éléments, puis l'imprimons à l'aide d'un itérateur et de manière classique. Comme vous pouvez le voir, LinkedHashMap maintient l'ordre d'insertion. Après cela, nous supprimons un élément de notre carte, puis ajoutons le nouveau et plus tard - un élément de plus avec la clé, qui est déjà sur la carte. Elle remplace l'ancienne valeur mappée à cette clé. Le résultat du programme en cours d'exécution :

key: 7 value: Johnny
key: 12 value: Rick
key: 1 value: Kyle
key: 5 value: Percy
key: 85 value: Sebastian
{7=Johnny, 12=Rick, 1=Kyle, 5=Percy, 85=Sebastian}
{7=Johnny, 12=Rick, 1=Kyle, 5=Percy, 85=Sebastian, 21=Ivy}
{7=Johnny, 1=Kyle, 5=Percy, 85=Sebastian, 21=Ivy}
{7=Johnny, 1=Kyle, 5=Percy, 85=Sebastian, 21=Ivy, 12=Ronny}
{7=Johnny, 1=Stan, 5=Percy, 85=Sebastian, 21=Ivy, 12=Ronny}

HashMap, TreeMap, LinkedHashMap Comparaison

HashMap, TreeMap et LinkedHashMap sont les implémentations des interfaces Map. HashMap et LinkedHashMap sont des structures de données qui hachent les clés. TreeMap utilise l'ordre naturel de ses clés pour organiser un arbre de recherche. Commande:

HashMap ne maintient aucun ordre.
TreeMap trie les entrées dans l'ordre croissant des clés.
LinkedHashMap maintient l'ordre d'insertion.

Clés nulles :

HashMap et LinkedHashMap permettent d'avoir une clé nulle.
LinkedHashMap n'autorise pas les clés nulles si les clés utilisent l'ordre naturel ou si Comparator ne prend pas en charge la comparaison sur les valeurs nulles.

Prenons un exemple de carte Java qui inclut les trois implémentations examinées dans cet article :

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.TreeMap;

public class CompMapImpl {


    public static void main(String[] args) {
        HashMap<Integer, String> hashMap = new HashMap<>();
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        LinkedHashMap<Integer, String> linkedHashMap = new LinkedHashMap<>();
        hashMap.put(5, "Ivy");
        hashMap.put(null, "Joker");
        hashMap.put(1, "First");
        hashMap.put(2, "Kyle");
        hashMap.put(-2, "Paul");
        hashMap.put(3, "Sandy");


        treeMap.put(5, "Ivy");
        //treeMap.put(null,"Joker");
        treeMap.put(1, "First");
        treeMap.put(2, "Kyle");
        treeMap.put(-2, "Paul");
        treeMap.put(3, "Sandy");

        linkedHashMap.put(5, "Ivy");
        linkedHashMap.put(null, "Joker");
        linkedHashMap.put(1, "First");
        linkedHashMap.put(2, "Kyle");
        linkedHashMap.put(-2, "Paul");
        linkedHashMap.put(3, "Sandy");
        System.out.println("HashMap");
        System.out.println(hashMap);
        System.out.println("TreeMap");
        System.out.println(treeMap);
        System.out.println("LinkedHashMap");
        System.out.println(linkedHashMap);


        LinkedHashMap<String, String> linkedHashMap1= new LinkedHashMap<> ();
        linkedHashMap1.put(null, "Andy");
        System.out.println(linkedHashMap1);
    }
}

Voici le résultat de l'exécution de ce programme :

HashMap
{null=Joker, 1=First, -2=Paul, 2=Kyle, 3=Sandy, 5=Ivy}
TreeMap
{-2=Paul, 1=First, 2=Kyle, 3=Sandy, 5=Ivy}
LinkedHashMap
{5=Ivy, null=Joker, 1=First, 2=Kyle, -2=Paul, 3=Sandy}
{null=Andy}

Comme nous pouvons le voir, l'ordre des éléments dans HashMap n'est pas évident, dans treeMap cela dépend des clés, dans LinkedHashMap il s'agit de l'ordre d'insertion. Si nous essayons de mettre une clé nulle dans linkedHashMap, nous obtiendrons NullPointerException, mais dans linkedHashMap1, où les clés sont String, nous pouvons le faire. Une carte de hachage est la meilleure implémentation de carte à usage général. Il offre une vitesse de recherche maximale, un stockage rapide et des opérations de récupération, mais vous devez vous rappeler de son ordre chaotique. Une carte de hachage liée hérite des avantages de HashMap et obtient un ordre pour les clés. Cependant, il contient linkedList, qui est relativement coûteux en termes de mémoire. il est plus lent que HashMap dans la recherche et un peu plus lent pour ajouter/supprimer en raison du maintien de la liste liée. Une arborescence stocke les clés triées par ordre croissant. Cependant, Pour renforcer ce que vous avez appris, nous vous suggérons de regarder une leçon vidéo de notre cours Java

Plus de lecture :
Comment mettre à jour la valeur d'une clé existante dans HashMap Méthode HashMap getOrDefault en Java Méthode KeySet dans java.util.Map