L'interfaccia Java Map fa parte del framework Java Collection, ma non è un sottotipo dell'interfaccia Collection. Quindi si comporta in modo diverso rispetto, ad esempio, agli elenchi o ad altri oggetti di raccolta. Ogni elemento di Map<Key, Value> rappresenta una coppia chiave-valore. Sia la chiave che il valore sono alcuni oggetti. Tutte le chiavi in una particolare mappa sono univoche, mentre i valori non lo sono, quindi possono essere duplicati. Potresti pensare a Map in Java come a una sorta di dizionario o catalogo di negozi online, dove puoi trovare qualsiasi articolo utilizzando il suo indice univoco. La chiave è un identificatore univoco del valore in una mappa. Ad esempio in Map<String, Item> String è un ID di un articolo del negozio online. Secondo le documentazioni Map ha le seguenti sottointerfacce:
Attacchi ;
ConcurrentMap<K,V> ;
ConcurrentNavigableMap<K,V> ;
LogicalMessageContext ;
Contesto messaggio ;
Mappa Navigabile<K,V> ;
SOAPMessageContext ;
Mappa ordinata<K,V> .
E implementa le classi:
Mappa astratta
Attributi
Provider di autenticazione
ConcurrentHashMap
ConcurrentSkipListMap
EnumMap
Mappa hash
Tabella hash
IdentityHashMap
LinkedHashMap
PrinterStateReasons
Proprietà
Fornitore
Suggerimenti per il rendering
SimpleBinding
TabularDataSupport
Mappa ad albero
UIDefaults
HashMap debole
Java AbstractMap è una classe astratta che implementa la maggior parte dell'interfaccia Map.
Java HashMap è una struttura dati per la memorizzazione di coppie chiave-valore utilizzando una tabella hash.
Java TreeMap è una struttura dati per utilizzare un albero, cioè display con chiavi ordinate.
WeakHashMap per utilizzare una hash table con chiavi deboli, display con valori che possono essere cancellati dal garbage collector se non vengono più utilizzati.
LinkedHashMap è una mappa con l'ordine di aggiunta di elementi, consente l'iterazione nell'ordine di inserimento.
EnumMap estende la classe AbstractMap per l'uso con le chiavi enum.
IdentityHashMap utilizza il controllo dell'equivalenza referenziale durante il confronto dei documenti, mappando con le chiavi confrontate utilizzando l'operazione
== invece del metodo
equals()
Qui siamo interessati alle implementazioni più popolari di Map Interface: HashMap, TreeMap e LinkedHashMap. A proposito, l'ordine degli elementi della mappa dipende da implementazioni specifiche. Supponiamo che TreeMap e LinkedHashMap abbiano un ordine prevedibile degli elementi, mentre HashMap no.
Metodi cartografici
Le operazioni principali di qualsiasi Mappa sono l'inserimento, la rimozione e la ricerca di elementi.
public Object put(Object key, Object value) inserisce un elemento nella mappa.
public void putAll(Map map) inserisce la mappa specificata all'interno della mappa.
public Object remove(Object key) elimina una voce in base alla chiave specificata.
public Object get(Chiave oggetto) restituisce il valore per la chiave specificata.
public boolean containsKey(Object key) cerca la chiave specificata da questa mappa
public Set keySet() restituisce una vista Set che contiene tutte le chiavi
public Set entrySet() restituisce una vista Set con tutte le chiavi ei valori.
Che cos'è HashMap
Che cos'è Hashmap? È l'implementazione più popolare dell'interfaccia Map<Key,Value>. Questa struttura di dati si basa sul principio dell'hashing.
Il principio principale del lavoro di HashMap: l'hashing
Per capire cos'è una hashmap e come funziona, parliamo prima di hashing e funzioni hash. Una funzione hash è solo una funzione in senso matematico. Quindi c'è un valore di input (un oggetto, un pezzo di dati) e la funzione lo converte utilizzando una regola appropriata in un valore di output: un hash. Abbastanza spesso l'hash è un numero esadecimale di lunghezza adeguata. Le regole dei processi di conversione potrebbero essere diverse, ma sono soggette ai seguenti principi:
Un particolare input (oggetto) ha un particolare codice hash.
Se due oggetti sono uguali, anche i loro codici hash sono uguali. Non è vero il contrario.
Se i codici hash sono diversi, gli oggetti sicuramente non sono uguali.
A volte oggetti diversi possono avere lo stesso codice hash. È un evento molto improbabile, chiamato "collisione" e una funzione hash di buona qualità dovrebbe ridurre al minimo la probabilità di collisioni.
In Java, ogni oggetto ha un codice hash. Viene calcolato dal metodo hashCode della classe Object, classe parentale di tutti gli oggetti Java. Di solito, gli sviluppatori eseguono l'override di questo metodo per le proprie classi e per i metodi uguali ad esso associati.
HashMap: come funziona
Quindi Class HashMap<K,V> come ogni implementazione di Map è costituita da chiavi e valori. Memorizza le chiavi utilizzando i principi di hashing. All'interno di HashMap le coppie chiave-valore sono memorizzate in "bucket", questi bucket insieme costruiscono una "tabella", un array interno di elenchi collegati e la sua dimensione iniziale è 16. HashMap in Java utilizza l'hashcode della chiave per determinare un bucket in cui la coppia chiave/valore dovrebbe mappare: la caratteristica complicata di HashMap è che ogni cella (bucket) della tabella [] conserva non solo una coppia ma diverse. Non sono memorizzati come oggetto esplicito (come LinkedList), ma come una catena implicita. La catena viene creata a causa del fatto che ogni coppia memorizza un collegamento alla coppia successiva. Cioè, tutte le coppie HashMap sono sparse su 16 catene. Quando inserisci una nuova coppia nella tabella, viene considerato l'hash della chiave. Questo hash non è una funzione hashcode incorporata nell'oggetto chiave. È considerato compreso tra 0 e 15. La coppia viene aggiunta alla catena di coppie memorizzate nel bucket con l'indice hash. Questo approccio ci dà l'accelerazione della ricerca. Durante la ricerca di una coppia per chiave, non è necessario esaminare l'intera tabella. Viene considerato l'hash della chiave e viene controllata solo la catena memorizzata nella cella con l'indice hash. Se ci sono troppe coppie nella HashMap, le catene diventano troppo lunghe. Quindi la dimensione dell'array aumenta, l'hash di tutti gli oggetti archiviati viene ricalcolato e questi vengono sparsi lungo nuove catene.
Dichiarazione HashMap
Se vai al codice HashMap della classe troverai la seguente dichiarazione:
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable
Dove K è il tipo di chiavi mantenute da questa mappa e V - il tipo di valori mappati. Questo è un esempio di dichiarazione HashMap con chiave Integer e valore String nel codice:
HashMap<Integer, String> myHashMap = new HashMap<Integer, String>();
Metodi HashMap
Ecco l'elenco dei metodi HashMap.
Object get(Object key) restituisce il valore per la chiave specificata;
L'oggetto put(Chiave k, Valore v) inserisce la mappatura del valore della chiave nella mappa;
Object remove(Object key) rimuove la mappatura per la chiave specificata da questa mappa se presente;
void clear() rimuove tutte le coppie chiave-valore dalla HashMap;
Object clone() restituisce una copia superficiale di questa istanza HashMap senza clonare chiavi e valori;
boolean containsKey(Object key) restituisce true se la chiave specificata viene trovata nella mappa, false se non lo è;
boolean containsValue(Object Value) restituisce true se la chiave specificata viene trovata nella mappa, false se non lo è;
boolean isEmpty() restituisce true se la mappa è vuota, false se non lo è;
Set keySet() restituisce il Set delle chiavi prelevate dalla mappa;
int size() restituisce la quantità di mappatura chiave-valore;
Collection values() restituisce una raccolta dei valori della mappa;
Object remove(Object key) rimuove la coppia chiave-valore per la chiave specificata;
void putAll(Map m) copia tutti gli elementi della mappa nell'altra mappa.
Esempio di mappa hash Java
Creiamo un programma con Java HashMap Example per dimostrare come funziona:
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);
}
}
}
Il risultato dell'esecuzione del programma:
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:
{}
Mappa ad albero
TreeMap in Java implementa anche l'interfaccia Map<Key,Value>, ma si basa sulla struttura dati ad albero Red-Black. Un albero è costituito da "nodi" e linee che collegano nodi - rami". Il nodo "radice" si trova nella parte superiore dell'albero. Dalla radice possono esserci rami e nodi. È una struttura gerarchica, si potrebbe pensare questi nodi come "figli" della radice. Il nodo figlio può avere i propri figli - nodi inferiori. I nodi senza figli sono chiamati "nodi finali" o "foglie". Un albero binario è un albero, in cui ogni nodo ha zero, uno , o due figli L'albero di ricerca binario è una struttura, in cui ogni nodo interno memorizza una chiave, e talvolta un valore associato, e ha due sotto-alberi distinti ("sinistra" e "destra"). Un albero di ricerca binario autobilanciato è un albero di ricerca binario basato su nodi che mantiene automaticamente la sua altezza (numero massimo di livelli sotto la radice) piccola a fronte di inserimenti ed eliminazioni arbitrarie di elementi. Un albero rosso-nero è un albero binario bilanciato con le proprietà:
Ogni nodo è rosso o nero
La radice è sempre nera
Ogni foglia è un nodo NIL (tipo di vuoto, nullo) ed è nera
Se un nodo è rosso, i suoi figli sono decisamente neri.
Ogni percorso semplice da un nodo a una foglia discendente contiene lo stesso numero di nodi neri.
Caratteristiche di una mappa ad albero
Una TreeMap utilizza una struttura di dati ad albero per memorizzare le chiavi come nodi e ordina le chiavi utilizzando l'algoritmo Red-Black Tree. Quindi, TreeMap mantiene le sue voci ordinate secondo l'ordine naturale delle sue chiavi. Per i numeri naturale è l'ordine crescente, per le stringhe l'ordine alfabetico. È possibile utilizzare un comparatore se è necessario modificare la logica dell'ordinamento. Ordinare gli oggetti in modo naturale è un grande vantaggio di TreeMap, così come trovare alcuni oggetti utilizzando diversi filtri e condizioni.
Metodi TreeMap
Object get(Chiave oggetto) restituisce il valore della chiave corrispondente;
Object put(Object key, Object value) inserisce una mappatura in una mappa;
Object remove(Object key) rimuove la mappatura per questa chiave da se TreeMap la contiene;
boolean containsKey(Object key) restituisce true se questa mappa contiene una mappatura per la chiave specificata;
boolean containsValue(Object value) restituisce true se TreeMap associa una o più chiavi al valore specificato;
Object firstKey() restituisce la prima chiave attualmente nella mappa ordinata;
L'oggetto lastKey() restituisce l'ultima chiave attualmente nella mappa ordinata;
void putAll(Map map) copia tutte le mappature dalla mappa specificata alla mappa;
Set entrySet() restituisce una vista impostata delle mappature
int size() restituisce la quantità di mappature chiave-valore
Collection values() restituisce una visualizzazione della raccolta dei valori
Object clone() restituisce una copia superficiale della TreeMap
void clear() rimuove tutti i mapping dalla TreeMap
SortedMap headMap(Object key_value) restituisce una vista della porzione di mappa inferiore al parametro key_value
Set keySet() restituisce una vista Set delle chiavi contenute nella mappa ad albero
SortedMap subMap(K fromKey, K toKey) restituisce una visualizzazione della porzione di questa mappa le cui chiavi vanno da fromKey, inclusivo, a toKey, esclusivo
L'oggetto firstKey() restituisce la prima chiave dalla TreeMap.
Esempio di mappa ad albero
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);
}
}
Il risultato dell'esecuzione del programma:
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 è una struttura dati che combina elenchi collegati e mappe hash. In effetti, LinkedHashMap estende la classe HashMap e implementa l'interfaccia Map, ma di cosa si tratta negli elenchi collegati? La dichiarazione di LinkedHashMap:
Map <Integer, String> linkedHashMap = new LinkedHashMap <Integer, String>();
Questa nuova linkedHashMap eredita proprietà da HashMap (come table, loadFactor, threshold, size, entrySet), ottiene anche due proprietà speciali:
header è la testa di una lista doppiamente collegata. Durante l'inizializzazione, si indica
accessOrder indica come ottenere l'accesso agli elementi utilizzando iteratore. Se true, nell'ordine dell'ultimo accesso. Se false, l'accesso avverrà nell'ordine in cui sono stati inseriti gli elementi.
Questo elenco collegato definisce l'ordine di iterazione. Di solito è l'ordine di inserimento delle chiavi nella mappa.
Metodi LinkedHashMap
Object get(Object key) restituisce il valore a cui è mappata la chiave specificata o null se questa mappa non contiene alcun mapping per la chiave
void clear() rimuove tutte le mappature dalla mappa.
boolean containsKey(Object key) restituisce true se l'elemento specificato è mappato da una o più chiavi
boolean removeEldestEntry(Map.Entry eldest) restituisce true se la mappa rimuove la voce meno recente dalla mappa
Set<Map.Entry<K,V>> entrySet() restituisce una vista Set delle mappature contenute in questa mappa
void forEach(BiConsumer<? super K,? super V> azione) esegue l'azione specificata per ogni voce in questa mappa finché tutte le voci non sono state elaborate o l'azione genera un'eccezione.
Object getOrDefault(Object key, V defaultValue) restituisce il valore a cui è mappata la chiave specificata. Se la mappa non contiene un mapping per la chiave restituisce defaultValue.
Set<K> keySet() restituisce una vista Set delle chiavi contenute nella mappa
boolean removeEldestEntry(Map.Entry<K,V> eldest) restituisce true se questa mappa deve rimuovere la voce meno recente
void replaceAll(BiFunction<? super K,? super V,? extends V> function) sostituisce ogni valore di voce con il risultato dell'invocazione della funzione data su quella voce finché tutte le voci non sono state elaborate o la funzione genera un'eccezione.
Collection<v>values() restituisce una visualizzazione Collection dei valori contenuti nella mappa
Esempio di 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);
}
}
Qui creiamo una nuova LinkedHashMap, aggiungendo cinque elementi, quindi la stampiamo usando l'iteratore e in modo classico. Come puoi vedere, LinkedHashMap mantiene l'ordine di inserimento. Dopodiché eliminiamo un elemento dalla nostra mappa, quindi aggiungiamo quello nuovo e successivamente - un altro elemento con la chiave, che è già sulla mappa. Sostituisce il vecchio valore associato a questa chiave. Il risultato dell'esecuzione del programma:
HashMap, TreeMap e LinkedHashMap sono le implementazioni delle interfacce Map. HashMap e LinkedHashMap sono strutture di dati che codificano le chiavi. TreeMap utilizza l'ordine naturale delle sue chiavi per organizzare un albero di ricerca. Ordine:
HashMap non mantiene alcun ordine.
TreeMap ordina le voci in ordine crescente di chiavi.
LinkedHashMap mantiene l'ordine di inserimento.
Chiavi nulle:
HashMap e LinkedHashMap consentono di avere una chiave nulla.
LinkedHashMap non consente chiavi nulle nel caso in cui le chiavi utilizzino l'ordinamento naturale o Comparator non supporta il confronto su letture nulle.
Facciamo un esempio di mappa Java che include tutte e tre le implementazioni esaminate in questo articolo:
Come possiamo vedere, l'ordine degli elementi in HashMap non è ovvio, in treeMap dipende dalle chiavi, in LinkedHashMap riguarda l'ordine di inserimento. Se proviamo a inserire la chiave nulla in linkedHashMap, otterremo NullPointerException, ma in linkedHashMap1, dove le chiavi sono String, possiamo farlo. Una mappa hash è la migliore implementazione di mappe generiche. Fornisce la massima velocità di ricerca, archiviazione rapida e operazioni di recupero, ma dovresti ricordare il suo ordinamento caotico. Una mappa hash collegata eredita i vantaggi di HashMap e ottiene un ordine per le chiavi. Tuttavia, contiene linkedList, che è relativamente costoso in termini di memoria. è più lento di HashMap nella ricerca e un po' più lento per aggiungere/rimuovere a causa del mantenimento dell'elenco collegato. Una mappa ad albero memorizza le chiavi ordinate in ordine crescente. Tuttavia, Per rafforzare ciò che hai imparato, ti suggeriamo di guardare una lezione video dal nostro corso Java
GO TO FULL VERSION