Java Map-grensesnittet er en del av Java Collection-rammeverket, men det er ikke en undertype av Collection-grensesnittet. Så det oppfører seg på en annen måte sammenlignet med for eksempel lister eller andre samlingsobjekter. Hvert element i Map<Nøkkel, Verdi> representerer et nøkkelverdi-par. Både nøkkel og verdi er noen objekter. Alle nøkler i et bestemt kart er unike, mens verdier ikke er det, så de kan dupliseres. Du tenker kanskje på kart i Java, for eksempel en slags ordbok eller nettbutikkkatalog, hvor du kan finne ethvert element ved hjelp av den unike indeksen. Nøkkelen er en unik identifikator for verdien i et kart. For eksempel i Map<String, Item> String er en ID for en vare fra nettbutikken. I følge dokumentasjon har Map de neste undergrensesnittene:
Bindinger ;
Concurrent Map<K,V> ;
ConcurrentNavigableMap<K,V> ;
LogicalMessageContext ;
MessageContext ;
Navigable Map<K,V> ;
SOAPMessageContext ;
Sortert kart<K,V> .
Og implementerer klasser:
Abstrakt kart
Attributter
AuthProvider
ConcurrentHashMap
Concurrent SkipListMap
EnumMap
HashMap
Hastbar
IdentityHashMap
LinkedHashMap
PrinterStateReasons
Egenskaper
Forsørger
Gjengivelsestips
Enkle bindinger
TabularDataSupport
Trekart
UID-standarder
WeakHashMap
Java AbstractMap er en abstrakt klasse som implementerer det meste av kartgrensesnittet.
Java HashMap er en datastruktur for lagring av nøkkel-verdi-par ved hjelp av en hash-tabell.
Java TreeMap er en datastruktur for å bruke et tre, dvs. visning med sorterte nøkler.
WeakHashMap for å bruke en hash-tabell med svake taster, visning med verdier som kan slettes av søppelsamleren hvis de ikke lenger brukes.
LinkedHashMap er et kart med rekkefølgen av å legge til elementer, tillater iterasjon i innsettingsrekkefølgen.
EnumMap utvider AbstractMap -klassen for bruk med enum-nøkler.
IdentityHashMap bruker referanseekvivalenskontroll ved sammenligning av dokumenter, kartlegging med nøkler sammenlignet med
==- operasjon i stedet for
equals()- metoden
Her er vi interessert i de mest populære implementeringene av Map Interface: HashMap, TreeMap og LinkedHashMap. For øvrig avhenger rekkefølgen av kartelementer av spesifikke implementeringer. Si, TreeMap og LinkedHashMap har forutsigbar rekkefølge av elementene, mens HashMap ikke har det.
Kartmetoder
Hovedoperasjonene til ethvert kart er innsetting, fjerning og søk etter elementer.
public Object put(Objektnøkkel, Objektverdi) setter inn et element i kartet.
public void putAll(Map map) setter inn det angitte kartet inne i kartet.
public Object remove(Object key) sletter en oppføring i henhold til den angitte nøkkelen.
public Object get(Objektnøkkel) returnerer verdien for den angitte nøkkelen.
public boolean containsKey(Objektnøkkel) søker etter den angitte nøkkelen fra dette kartet
public Set keySet() returnerer en Set-visning som inneholder alle nøklene
public Set entrySet() returnerer en Set-visning med alle nøklene og verdiene.
Hva er HashMap
Hva er HashMap? Det er den mest populære implementeringen av Map<Key,Value>-grensesnittet. Denne datastrukturen er basert på hashing-prinsippet.
Hovedprinsippet for HashMap-arbeid: hashing
For å forstå hva som er et hashmap og hvordan det fungerer, la oss først snakke om hashing og hash-funksjoner. En hash-funksjon er bare en funksjon i matematisk forstand. Så det er en inngangsverdi (et objekt, et stykke data) og funksjon konverterer den ved å bruke en riktig regel til utdataverdi - en hash. Ganske ofte er hash et heksadesimalt tall med riktig lengde. Reglene for konverteringsprosesser kan være forskjellige, men de er underlagt følgende prinsipper:
En bestemt inngang (objekt) har en bestemt hash-kode.
Hvis to objekter er like, er hashkodene også like. Det motsatte er ikke sant.
Hvis hash-kodene er forskjellige, er objektene definitivt ikke like.
Noen ganger kan forskjellige objekter ha samme hash-kode. Det er en svært usannsynlig hendelse, kalt "kollisjon", og en hash-funksjon av god kvalitet bør minimere sannsynligheten for kollisjoner.
I Java har hvert objekt en hash-kode. Den beregnes ved hjelp av hashCode-metoden til Object-klassen, foreldreklassen til alle Java-objekter. Vanligvis overstyrer utviklere denne metoden for sine egne klasser, så vel som metoder knyttet til den.
HashMap: hvordan det fungerer
Så Class HashMap<K,V> som hver kartimplementering består av nøkler og verdier. Den lagrer nøkler ved hjelp av hashing-prinsipper. Inne i HashMap er nøkkelverdi-parene lagret i "bøtter", disse bøttene danner sammen en "tabell", en intern rekke koblede lister og dens opprinnelige størrelse er 16. HashMap i Java bruker nøkkelens hashkode for å bestemme en bøtte hvor nøkkel/verdi-paret skal kartlegges: Det vanskelige med HashMap er at hver celle (bøtte) i tabellen [] holder ikke bare ett par, men flere. De lagres ikke som et eksplisitt objekt (som LinkedList), men som en implisitt kjede. Kjeden er opprettet på grunn av at hvert par lagrer en lenke til neste par. Det vil si at alle HashMap-parene er spredt over 16 kjeder. Når du legger inn et nytt par i tabellen, vurderes hashen til nøkkelen. Denne hashen er ikke en hashkodefunksjon innebygd i nøkkelobjektet. Det anses å være i området 0-15. Paret legges til kjeden av par som er lagret i bøtta med hash-indeksen. Denne tilnærmingen gir oss søkeakselerasjon. Når du søker etter et par med nøkkel, er det ikke nødvendig å gå gjennom hele tabellen. Hash-verdien til nøkkelen vurderes og kun kjeden som er lagret i cellen med hash-indeksen blir sjekket. Hvis det er for mange par i HashMap, blir kjedene for lange. Deretter øker størrelsen på matrisen, hashen til alle lagrede objekter beregnes på nytt, og de blir spredt langs nye kjeder.
HashMap-erklæring
Hvis du går til klassen HashMap-koden vil du finne neste erklæring:
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable
Der K er typen nøkler som vedlikeholdes av dette kartet og V - typen kartlagte verdier. Dette er et eksempel på HashMap-erklæring med heltallsnøkkel og strengverdi i koden din:
HashMap<Integer, String> myHashMap = new HashMap<Integer, String>();
HashMap-metoder
Her er listen over HashMap-metoder.
Object get(Objektnøkkel) returnerer verdien for den angitte nøkkelen;
Objekt put(Key k, Verdi v) setter inn nøkkelverditilordning i kartet;
Objekt fjern(Objektnøkkel) fjerner tilordningen for den angitte nøkkelen fra dette kartet hvis det finnes;
void clear() fjerner alle nøkkelverdi-parene fra HashMap;
Object clone() returnerer en grunn kopi av denne HashMap-forekomsten uten å klone nøklene og verdiene;
boolean containsKey(Objektnøkkel) returnerer true hvis den spesifiserte nøkkelen finnes i kartet, false hvis ikke;
boolean containsValue(Object Value) returnerer true hvis den angitte nøkkelen er funnet i kartet, false hvis ikke;
boolean isEmpty() returnerer true hvis kartet er tomt, usant hvis det ikke er det;
Set keySet() returnerer settet med nøkler hentet fra kartet;
int size() returnerer mengden nøkkelverdi-tilordning;
Collection values() returnerer en samling av kartets verdier;
Object remove(Object key) fjerner nøkkelverdi-paret for den angitte nøkkelen;
void putAll(Map m) kopierer alle elementene i kartet til det andre kartet.
Eksempel på Java HashMap
La oss lage et program med Java HashMap Eksempel for å demonstrere hvordan det fungerer:
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);
}
}
}
Resultatet av å kjøre programmet:
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:
{}
Trekart
TreeMap i Java implementerer også Map<Key,Value>-grensesnittet, men det er basert på rød-svart tredatastruktur. Et tre består av "noder" og linjer som forbinder noder - grener. "Root"-noden er på toppen av treet. Fra roten kan det være grener og noder. Det er en hierarkisk struktur, du tenker kanskje på disse nodene som "barn" av roten. Barneknute kan ha sine egne barn - nedre noder. Noder uten barn kalles "endenoder" eller "blader". Et binært tre er et tre, der hver node har null, en , eller to barn. Det binære søketreet er en struktur der hver intern node lagrer en nøkkel, og noen ganger en assosiert verdi, og har to adskilte undertrær ("venstre" og "høyre"). Et selvbalanserende binært søketre er et nodebasert binært søketre som automatisk holder høyden (maksimalt antall nivåer under roten) liten i møte med vilkårlige elementinnsettinger og slettinger. Et rød-svart tre er et balansert binært tre med egenskapene:
Hver node er enten rød eller svart
Roten er alltid svart
Hvert blad er en NIL (type tom, null) node og den er svart
Hvis en node er rød, er barna definitivt svarte.
Hver enkel vei fra en node til et etterkommerblad inneholder samme antall svarte noder.
Et TreeMap-funksjoner
Et TreeMap bruker en tredatastruktur for å lagre nøklene som noder og sorterer nøklene ved hjelp av Red-Black Tree-algoritmen. Så TreeMap holder oppføringene sortert i henhold til den naturlige rekkefølgen av nøklene. For tall er naturlig stigende rekkefølge, for strenger - alfabetisk rekkefølge. Du kan bruke en komparator hvis du trenger å endre bestillingslogikken. Å sortere objekter på en naturlig måte er en stor fordel med TreeMap, i tillegg til å finne noen objekter ved hjelp av ulike filtre og forhold.
TreeMap-metoder
Objekt get(Objektnøkkel) returnerer verdien til den tilsvarende nøkkelen;
Object put(Objektnøkkel, Objektverdi) setter inn en tilordning i et kart;
Object remove(Object key) fjerner tilordningen for denne nøkkelen fra hvis TreeMap inneholder den;
boolean containsKey(Objektnøkkel) returnerer true hvis dette kartet inneholder en tilordning for den angitte nøkkelen;
boolean containsValue(Objektverdi) returnerer true hvis TreeMap tilordner én eller flere nøkler til den angitte verdien;
Objekt firstKey() returnerer den første nøkkelen i det sorterte kartet;
Objekt lastKey() returnerer den siste nøkkelen for øyeblikket i det sorterte kartet;
void putAll(Map map) kopierer alle tilordninger fra det angitte kartet til kartet;
Set entrySet() returnerer en settvisning av tilordningene
int size() returnerer antallet nøkkelverdi-tilordninger
Collection values() returnerer en samlingsvisning av verdiene
Object clone() returnerer en grunn kopi av TreeMap
void clear() fjerner alle tilordninger fra TreeMap
SortedMap headMap(Object key_value) returnerer en visning av delen av kartet som er mindre enn parameteren nøkkelverdi
Set keySet() returnerer en Set-visning av nøklene i trekartet
SortedMap subMap(K fromKey, K toKey) returnerer en visning av delen av dette kartet hvis nøkler strekker seg fra fromKey, inklusive, til toKey, exclusive
Objekt firstKey() returnerer den første nøkkelen fra TreeMap.
TreeMap eksempel
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);
}
}
Resultatet av å kjøre programmet:
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 er en datastruktur som kombinerer koblede lister og hash-kart. Faktisk utvider LinkedHashMap HashMap-klassen og implementerer Map-grensesnittet, men hva er det med koblede lister? Erklæringen fra LinkedHashMap:
Map <Integer, String> linkedHashMap = new LinkedHashMap <Integer, String>();
Dette nye linkedHashMap arver egenskaper fra HashMap (som tabell, loadFactor, threshold, size, entrySet), får også to spesielle egenskaper:
header er hodet på en dobbeltlenket liste. Under initialiseringen indikerer den seg selv
accessOrder indikerer hvordan du får tilgang til elementer ved hjelp av iterator. Hvis sant, i rekkefølgen til siste tilgang. Hvis falsk, vil tilgangen være i den rekkefølgen elementene ble satt inn.
Denne koblede listen definerer iterasjonsrekkefølgen. Vanligvis er det rekkefølgen på nøkler som settes inn i kartet.
LinkedHashMap-metoder
Objekt get(Objektnøkkel) returnerer verdien som den angitte nøkkelen er tilordnet til, eller null hvis dette kartet ikke inneholder noen tilordning for nøkkelen
void clear() fjerner alle tilordningene fra kartet.
boolean containsKey(Object key) returnerer true hvis det angitte elementet er kartlagt av én eller flere nøkler
boolean removeEldestEntry(Map.Entry eldest) returnerer true hvis kartet fjerner sin eldste oppføring fra kartet
Set<Map.Entry<K,V>> entrySet() returnerer en Set-visning av tilordningene i dette kartet
void forEach(BiConsumer<? super K,? super V> handling) utfører den gitte handlingen for hver oppføring i dette kartet til alle oppføringer er behandlet eller handlingen gir et unntak.
Objekt getOrDefault(Objektnøkkel, V defaultValue) returnerer verdien som den angitte nøkkelen er tilordnet til. Hvis kartet ikke inneholder en tilordning for nøkkelen, returnerer standardverdien.
Set<K> keySet() returnerer en Set-visning av nøklene i kartet
boolean removeEldestEntry(Map.Entry<K,V> eldest) returnerer true hvis dette kartet skal fjerne sin eldste oppføring
void replaceAll(BiFunction<? super K,? super V,? utvider V>-funksjonen) erstatter hver oppføringsverdi med resultatet av å påkalle den gitte funksjonen på den oppføringen til alle oppføringer er behandlet eller funksjonen gir et unntak.
Collection<v>values() returnerer en samlingsvisning av verdiene i kartet
LinkedHashMap eksempel
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);
}
}
Her lager vi et nytt LinkedHashMap, legger til fem elementer, og skriver det ut ved hjelp av iterator og på en klassisk måte. Som du kan se, opprettholder LinkedHashMap innsettingsrekkefølgen. Etter det sletter vi et element fra kartet vårt, legger til det nye og senere - ett element til med nøkkelen, som allerede er på kartet. Den erstatter den gamle verdien som er tilordnet denne nøkkelen. Resultatet av å kjøre programmet:
HashMap, TreeMap og LinkedHashMap er implementeringer av kartgrensesnitt. HashMap og LinkedHashMap er datastrukturer som hasheser nøkler. TreeMap bruker den naturlige rekkefølgen til nøklene for å organisere et søketre. Rekkefølge:
HashMap opprettholder ingen rekkefølge.
TreeMap sorterer oppføringene i stigende rekkefølge av nøkler.
Som vi kan se er ikke rekkefølgen på elementer i HashMap åpenbar, i treeMap avhenger det av nøkler, i LinkedHashMap handler det om innsettingsrekkefølge. Hvis vi prøver å sette null-nøkkel inn i linkedHashMap, får vi NullPointerException, men i linkedHashMap1, der nøkler er String, kan vi gjøre det. Et hash-kart er den beste kartimplementeringen for generelle formål. Den gir maksimal søkehastighet, rask lagring og gjenfinningsoperasjoner, men du bør huske på den kaotiske rekkefølgen. Et koblet hash-kart arver HashMap-fordeler og får en bestilling på nøklene. Den inneholder imidlertid linkedList, som er relativt kostbar når det gjelder minne. det er tregere enn HashMap i søking og litt tregere for å legge til/fjerne på grunn av opprettholdelse av lenket liste. Et trekart lagrer nøkler sortert i stigende rekkefølge. Derimot, For å forsterke det du lærte, foreslår vi at du ser en videoleksjon fra vårt Java-kurs
GO TO FULL VERSION