De Java Map-interface maakt deel uit van het Java Collection-framework, maar is geen subtype van de Collection-interface. Het gedraagt zich dus op een andere manier in vergelijking met bijvoorbeeld lijsten of andere verzamelobjecten. Elk element van Map<Key, Value> vertegenwoordigt een sleutel-waardepaar. Zowel sleutel als waarde zijn enkele objecten. Alle sleutels in een bepaalde kaart zijn uniek, terwijl waarden dat niet zijn, dus ze kunnen worden gedupliceerd. Je zou kunnen denken aan Map in Java, zoals een soort woordenboek of online winkelcatalogus, waar je elk item kunt vinden met behulp van zijn unieke index. De sleutel is een unieke identificatie van de waarde in een kaart. Bijvoorbeeld in Map<String, Item> String is een ID van een item uit de online winkel. Volgens de documentatie heeft Map de volgende subinterfaces:
Bindingen ;
ConcurrentMap<K,V> ;
ConcurrentNavigableMap<K,V> ;
LogischeBerichtContext ;
BerichtContext ;
Navigeerbare Kaart<K,V> ;
SOAPBerichtContext ;
SortedMap<K,V> .
En implementeert klassen:
Abstracte kaart
attributen
AuthProvider
GelijktijdigeHashMap
ConcurrentSkipListMap
EnumMap
Hash kaart
Hashtabel
IdentityHashMap
LinkedHashMap
PrinterStateReasons
Eigenschappen
Aanbieder
WeergaveHints
SimpleBindings
TabularDataSupport
TreeMap
UIDfouten
ZwakkeHashMap
Java AbstractMap is een abstracte klasse die het grootste deel van de kaartinterface implementeert.
Java HashMap is een gegevensstructuur voor het opslaan van sleutel-waardeparen met behulp van een hashtabel.
Java TreeMap is een datastructuur om een boom te gebruiken, dwz weergave met gesorteerde sleutels.
WeakHashMap om een hashtabel met zwakke sleutels te gebruiken, weergave met waarden die door de vuilnisman kunnen worden verwijderd als ze niet meer worden gebruikt.
LinkedHashMap is een kaart met de volgorde van het toevoegen van elementen, maakt iteratie in de invoegvolgorde mogelijk.
EnumMap breidt de klasse AbstractMap uit voor gebruik met enum-sleutels.
IdentityHashMap gebruikt referentie-equivalentiecontrole bij het vergelijken van documenten, mapping met sleutels vergeleken met
== operatie in plaats van
equals() methode
Hier zijn we geïnteresseerd in de meest populaire implementaties van Map Interface: HashMap, TreeMap en LinkedHashMap. Overigens hangt de volgorde van kaartelementen af van specifieke implementaties. Stel dat TreeMap en LinkedHashMap een voorspelbare volgorde van de elementen hebben, terwijl HashMap dat niet heeft.
Methoden in kaart brengen
De belangrijkste bewerkingen van elke kaart zijn het invoegen, verwijderen en zoeken van elementen.
public Object put (Object key, Object value) voegt een element in de kaart in.
public void putAll(Map map) voegt de opgegeven kaart in de kaart in.
public Object remove (Object-sleutel) verwijdert een invoer volgens de opgegeven sleutel.
public Object get (Objectsleutel) retourneert de waarde voor de opgegeven sleutel.
public boolean comesKey(Object key) zoekt de gespecificeerde sleutel van deze kaart
public Set keySet() retourneert een setweergave die alle sleutels bevat
public Set entrySet() retourneert een setweergave met alle sleutels en waarden.
Wat is HashMap
Wat is HashMap? Het is de meest populaire implementatie van de Map<Key,Value>-interface. Deze datastructuur is gebaseerd op het hashing-principe.
Het belangrijkste principe van HashMap-werk: hashen
Om te begrijpen wat een hashmap is en hoe het werkt, laten we het eerst hebben over hashing en hash-functies. Een hash-functie is slechts een functie in wiskundige zin. Er is dus een invoerwaarde (een object, een stuk gegevens) en de functie converteert deze met behulp van een juiste regel naar uitvoerwaarde - een hash. Vrij vaak is hash een hexadecimaal getal van een juiste lengte. Regels voor conversieprocessen kunnen verschillen, maar ze zijn onderworpen aan de volgende principes:
Een bepaalde invoer (object) heeft een bepaalde hashcode.
Als twee objecten gelijk zijn, zijn hun hashcodes ook gelijk. Het omgekeerde is niet waar.
Als de hashcodes verschillend zijn, zijn de objecten zeker niet gelijk.
Soms kunnen verschillende objecten dezelfde hashcode hebben. Het is een zeer onwaarschijnlijke gebeurtenis, genaamd "botsing" en een hashfunctie van goede kwaliteit zou de kans op botsingen moeten minimaliseren.
In Java heeft elk object een hashcode. Het wordt berekend door de hashCode-methode van de klasse Object, de ouderlijke klasse van alle Java-objecten. Gewoonlijk overschrijven ontwikkelaars deze methode voor hun eigen klassen, evenals de bijbehorende methodes.
HashMap: hoe het werkt
Dus Class HashMap<K,V> aangezien elke Map-implementatie bestaat uit sleutels en waarden. Het slaat sleutels op met behulp van hash-principes. Binnen de HashMap worden sleutel-waardeparen opgeslagen in "buckets", deze buckets vormen samen een "tabel", een interne reeks gekoppelde lijsten en de oorspronkelijke grootte is 16. HashMap in Java gebruikt de hashcode van de sleutel om een bucket te bepalen waar het sleutel/waarde-paar moet worden toegewezen: het lastige kenmerk van HashMap is dat elke cel (bucket) van de tabel [] niet slechts één paar bevat, maar meerdere. Ze worden niet opgeslagen als een expliciet object (zoals LinkedList), maar als een impliciete keten. De ketting ontstaat doordat elk paar een link naar het volgende paar opslaat. Dat wil zeggen, alle HashMap-paren zijn verspreid over 16 ketens. Wanneer u een nieuw paar in de tafel legt, wordt rekening gehouden met de hash van de sleutel. Deze hash is geen hashcodefunctie die in het sleutelobject is ingebouwd. Het wordt beschouwd als in het bereik van 0-15. Het paar wordt toegevoegd aan de ketting van paren die is opgeslagen in de bucket met de hash-index. Deze aanpak geeft ons zoekversnelling. Bij het zoeken naar een paar op sleutel is het niet nodig om de hele tabel te doorlopen. Er wordt rekening gehouden met de hash van de sleutel en alleen de keten die is opgeslagen in de cel met de hash-index wordt gecontroleerd. Als er te veel paren in de HashMap staan, worden de ketens te lang. Vervolgens neemt de grootte van de array toe, wordt de hash van alle opgeslagen objecten opnieuw berekend en worden ze verspreid over nieuwe ketens.
HashMap-verklaring
Als je naar de klasse HashMap-code gaat, vind je de volgende verklaring:
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable
Waarbij K het type sleutels is dat door deze map wordt onderhouden en V - het type toegewezen waarden. Dit is een voorbeeld van een HashMap-declaratie met Integer-sleutel en String-waarde in uw code:
HashMap<Integer, String> myHashMap = new HashMap<Integer, String>();
HashMap-methoden
Hier is de lijst met HashMap-methoden.
Object get (Objectsleutel) retourneert de waarde voor de opgegeven sleutel;
Object put(Key k, Value v) voegt sleutelwaardetoewijzing in de kaart in;
Object remove(Object key) verwijdert de mapping voor de gespecificeerde key van deze map, indien aanwezig;
void clear() verwijdert alle sleutel-waardeparen uit de HashMap;
Object clone() retourneert een ondiepe kopie van deze HashMap-instantie zonder de sleutels en waarden te klonen;
boolean comesKey (Objectsleutel) retourneert true als de opgegeven sleutel in de kaart wordt gevonden, false als dat niet het geval is;
boolean bevatWaarde(Objectwaarde) retourneert true als de opgegeven sleutel in de kaart wordt gevonden, false als dat niet het geval is;
boolean isEmpty() retourneert true als de kaart leeg is, false als dat niet het geval is;
Set keySet() retourneert de set sleutels die is opgehaald van de kaart;
int size() retourneert de hoeveelheid sleutel-waardetoewijzing;
Verzamelingswaarden() retourneert een verzameling van de waarden van de kaart;
Object remove(Object key) verwijdert het sleutel-waardepaar voor de opgegeven sleutel;
void putAll(Map m) kopieert alle elementen van de kaart naar de andere kaart.
Java HashMap-voorbeeld
Laten we een programma maken met Java HashMap Example om te demonstreren hoe het werkt:
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);
}
}
}
Het resultaat van het uitvoeren van het 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:
{}
TreeMap
TreeMap in Java implementeert ook de Map<Key,Value>-interface, maar is gebaseerd op de rood-zwarte boomstructuur. Een boom bestaat uit "knopen" en lijnen die knopen - takken verbinden". deze knooppunten als "kinderen" van de wortel. Onderliggend knooppunt kan zijn eigen kinderen hebben - lagere knooppunten. Knopen zonder kinderen worden "eindknooppunten" of "bladeren" genoemd. Een binaire boom is een boom, waarbij elk knooppunt nul heeft, één , of twee kinderen De binaire zoekboom is een structuur waarin elk intern knooppunt een sleutel opslaat, en soms een bijbehorende waarde, en heeft twee onderscheiden subbomen ("links" en "rechts"). Een zelfbalancerende binaire zoekboom is een op knooppunten gebaseerde binaire zoekboom die automatisch zijn hoogte (maximaal aantal niveaus onder de hoofdmap) klein houdt bij willekeurige invoegingen en verwijderingen van items. Een rood-zwarte boom is een gebalanceerde binaire boom met de eigenschappen:
Elk knooppunt is rood of zwart
De wortel is altijd zwart
Elk blad is een NIL (soort van leeg, null) knooppunt en het is zwart
Als een knoop rood is, zijn de kinderen zeker zwart.
Elk eenvoudig pad van een knooppunt naar een afstammend blad bevat hetzelfde aantal zwarte knooppunten.
Een TreeMap-functies
Een TreeMap gebruikt een boomstructuur om de sleutels op te slaan als de knooppunten en sorteert de sleutels met behulp van het Red-Black Tree-algoritme. Dus, TreeMap houdt zijn items gesorteerd volgens de natuurlijke volgorde van zijn sleutels. Voor getallen is natuurlijk oplopende volgorde, voor strings - alfabetische volgorde. U kunt een vergelijker gebruiken als u de logica van bestellen wilt wijzigen. Het op een natuurlijke manier sorteren van objecten is een groot voordeel van TreeMap, evenals het vinden van sommige objecten met behulp van verschillende filters en voorwaarden.
TreeMap-methoden
Object get (Objectsleutel) geeft de waarde van de corresponderende sleutel terug;
Object put (Object key, Object value) voegt een afbeelding in een kaart in;
Object remove(Object key) verwijdert de mapping voor deze key van als de TreeMap deze bevat;
boolean bevatSleutel(Objectsleutel) retourneert waar als deze toewijzing een toewijzing voor de opgegeven sleutel bevat;
boolean bevatWaarde(Objectwaarde) retourneert waar als de TreeMap een of meer sleutels toewijst aan de opgegeven waarde;
Object firstKey() retourneert de eerste sleutel die zich momenteel in de gesorteerde kaart bevindt;
Object lastKey() retourneert de laatste sleutel die zich momenteel in de gesorteerde kaart bevindt;
void putAll(Map map) kopieert alle mappings van de gespecificeerde map naar de map;
Set entrySet() retourneert een setweergave van de toewijzingen
int size() retourneert het aantal sleutel-waardetoewijzingen
Verzamelwaarden() retourneert een verzamelingsweergave van de waarden
Object clone() retourneert een ondiepe kopie van de TreeMap
void clear() verwijdert alle toewijzingen uit de TreeMap
SortedMap headMap(Object key_value) retourneert een weergave van het deel van de kaart dat kleiner is dan de parameter key_value
Set keySet() retourneert een Set-weergave van de sleutels in de treemap
SortedMap subMap(K fromKey, K toKey) retourneert een weergave van het gedeelte van deze kaart waarvan de sleutels variëren van fromKey, inclusief, tot toKey, exclusief
Object firstKey() retourneert de eerste sleutel uit de TreeMap.
TreeMap voorbeeld
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);
}
}
Het resultaat van het uitvoeren van het 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 is een gegevensstructuur die gelinkte lijsten en hash-kaarten combineert. LinkedHashMap breidt inderdaad de HashMap-klasse uit en implementeert de kaartinterface, maar hoe zit het met gekoppelde lijsten? De verklaring van LinkedHashMap:
Map <Integer, String> linkedHashMap = new LinkedHashMap <Integer, String>();
Deze nieuwe linkedHashMap erft eigenschappen van HashMap (zoals table, loadFactor, threshold, size, entrySet), krijgt ook twee speciale eigenschappen:
header is de kop van een dubbel gelinkte lijst. Tijdens de initialisatie geeft het zichzelf aan
accessOrder geeft aan hoe toegang tot elementen kan worden verkregen met behulp van iterator. Indien waar, in de volgorde van de laatste toegang. Als dit niet waar is, vindt de toegang plaats in de volgorde waarin de elementen zijn ingevoegd.
Deze gekoppelde lijst definieert de iteratievolgorde. Meestal is het de volgorde van het inbrengen van de sleutels in de kaart.
LinkedHashMap-methoden
Object get (Objectsleutel) retourneert de waarde waaraan de opgegeven sleutel is toegewezen, of null als deze toewijzing geen toewijzing voor de sleutel bevat
void clear() verwijdert alle toewijzingen van de kaart.
boolean comesKey (Objectsleutel) retourneert true als het opgegeven element is toegewezen door een of meer sleutels
boolean removeEldestEntry(Map.Entry elderst) retourneert true als de kaart zijn oudste invoer van de kaart verwijdert
Set<Map.Entry<K,V>> entrySet() retourneert een Set-weergave van de toewijzingen in deze kaart
void forEach (BiConsumer<? super K,? super V> actie) voert de gegeven actie uit voor elk item op deze kaart totdat alle items zijn verwerkt of de actie een uitzondering genereert.
Object getOrDefault(Objectsleutel, V defaultValue) retourneert de waarde waaraan de opgegeven sleutel is toegewezen. Als de toewijzing geen toewijzing voor de sleutel bevat, wordt defaultValue geretourneerd.
Set<K> keySet() retourneert een Set-weergave van de sleutels in de kaart
boolean removeEldestEntry(Map.Entry<K,V> oudste) retourneert waar als deze kaart zijn oudste invoer zou moeten verwijderen
void replaceAll(BiFunction<?super K,?super V,? extends V> function) vervangt elke ingevoerde waarde door het resultaat van het aanroepen van de gegeven functie op die ingang totdat alle ingangen zijn verwerkt of de functie een uitzondering genereert.
Collection<v>values() retourneert een verzamelingsweergave van de waarden in de kaart
LinkedHashMap-voorbeeld
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);
}
}
Hier maken we een nieuwe LinkedHashMap, voegen vijf elementen toe en drukken deze vervolgens af met iterator en op een klassieke manier. Zoals u kunt zien, houdt LinkedHashMap de invoegvolgorde bij. Hierna verwijderen we een element van onze kaart, voegen dan het nieuwe toe en later - nog een element met de sleutel, die al op de kaart staat. Het vervangt de oude waarde die aan deze sleutel is toegewezen. Het resultaat van het lopende programma:
HashMap, TreeMap en LinkedHashMap zijn de implementaties van Map-interfaces. HashMap en LinkedHashMap zijn datastructuren die sleutels hashen. TreeMap gebruikt de natuurlijke volgorde van zijn sleutels om een zoekboom te organiseren. Volgorde:
HashMap handhaaft geen enkele volgorde.
TreeMap sorteert de vermeldingen in oplopende volgorde van sleutels.
LinkedHashMap houdt de invoegvolgorde bij.
Null-sleutels:
HashMap en LinkedHashMap maken het mogelijk om één null-sleutel te hebben.
LinkedHashMap staat geen null-sleutels toe in het geval dat de sleutels natuurlijke volgorde gebruiken of Comparator ondersteunt geen vergelijking op null-leys.
Laten we een Java-kaartvoorbeeld nemen dat alle drie de implementaties bevat die in dit artikel worden besproken:
Zoals we kunnen zien, is de volgorde van elementen in HashMap niet duidelijk, in treeMap hangt het af van sleutels, in LinkedHashMap gaat het om de invoegvolgorde. Als we proberen een null-sleutel in linkedHashMap te plaatsen, krijgen we NullPointerException, maar in linkedHashMap1, waar sleutels String zijn, kunnen we het doen. Een hash-kaart is de beste kaartimplementatie voor algemeen gebruik. Het biedt maximale zoeksnelheid, snelle opslag en ophaalbewerkingen, maar onthoud de chaotische volgorde ervan. Een gekoppelde hashmap erft HashMap-voordelen en krijgt een bestelling voor de sleutels. Het bevat echter linkedList, wat relatief duur is in termen van geheugen. het is langzamer dan HashMap bij het zoeken en een beetje langzamer bij het toevoegen/verwijderen vanwege het onderhouden van de gekoppelde lijst. Een boomkaart slaat sleutels op in oplopende volgorde. Echter, Om te versterken wat je hebt geleerd, raden we je aan een videoles van onze Java-cursus te bekijken
GO TO FULL VERSION