De Java HashMap onder de motorkap
1. Overzicht
In dit artikel gaan we de meest populaire implementatie van Kaart interface van het Java Collections Framework in meer detail, om verder te gaan waar ons intro-artikel was gebleven.
Voordat we aan de slag gaan met de implementatie, is het belangrijk om erop te wijzen dat de primary Lijst en Set collectie-interfaces uitbreiden Verzameling maar Kaart doet niet.
Simpel gezegd, de Hash kaart slaat waarden op per sleutel op en biedt API's voor het toevoegen, ophalen en manipuleren van opgeslagen gegevens op verschillende manieren. De implementatie is gebaseerd op de principes van een hashtabel, wat in eerste instantie een beetje ingewikkeld klinkt, maar eigenlijk heel gemakkelijk te begrijpen is.
Sleutel-waardeparen worden opgeslagen in zogenaamde buckets die samen een tabel vormen, die eigenlijk een interne array is.
Zodra we de sleutel kennen waaronder een object is opgeslagen of moet worden opgeslagen, opslag- en ophaalbewerkingen vinden plaats in constante tijd, O (1) in een goed gedimensioneerde hash-kaart.
Om te begrijpen hoe hash-kaarten onder de motorkap werken, moet men het opslag- en ophaalmechanisme begrijpen dat wordt gebruikt door het Hash kaart. We zullen hier veel aandacht aan besteden.
Tenslotte, Hash kaart gerelateerde vragen komen vrij vaak voor in interviews, dus dit is een solide manier om een interview voor te bereiden of erop voor te bereiden.
2. Het leggen() API
Om een waarde in een hash-map op te slaan, noemen we de leggen API die twee parameters nodig heeft; een sleutel en de bijbehorende waarde:
V put (K-toets, V-waarde);Wanneer een waarde wordt toegevoegd aan de kaart onder een sleutel, wordt de hashCode () De API van het key-object wordt aangeroepen om de zogenaamde initiële hash-waarde op te halen.
Om dit in actie te zien, moeten we een object maken dat als sleutel zal fungeren. We zullen slechts één attribuut maken om als hashcode te gebruiken om de eerste fase van hashing te simuleren:
openbare klasse MyKey {privé int id; @Override public int hashCode () {System.out.println ("Calling hashCode ()"); retourneer id; } // constructor, setters en getters}We kunnen dit object nu gebruiken om een waarde in de hash-map in kaart te brengen:
@Test openbare ongeldig whenHashCodeIsCalledOnPut_thenCorrect () {MyKey-sleutel = nieuwe MyKey (1); Map map = nieuwe HashMap (); map.put (key, "val"); }Er gebeurt niet veel in de bovenstaande code, maar let op de console-uitvoer. Inderdaad de hashCode methode wordt aangeroepen:
HashCode () aanroepenVervolgens de hash () De API van de hash-map wordt intern aangeroepen om de uiteindelijke hash-waarde te berekenen met behulp van de initiële hash-waarde.
Deze laatste hash-waarde komt uiteindelijk neer op een index in de interne array of wat we een bucketlocatie noemen.
De hash functie van Hash kaart het lijkt op dit:
statische laatste int hash (Object sleutel) {int h; return (key == null)? 0: (h = key.hashCode ()) ^ (h >>> 16); }Wat we hier moeten opmerken, is alleen het gebruik van de hash-code van het key-object om een uiteindelijke hash-waarde te berekenen.
Terwijl binnen de leggen functie, wordt de laatste hash-waarde als volgt gebruikt:
openbare V put (K-sleutel, V-waarde) {return putVal (hash (sleutel), sleutel, waarde, onwaar, waar); }Merk op dat een interne putVal functie wordt aangeroepen en krijgt de laatste hash-waarde als de eerste parameter.
Je kunt je afvragen waarom de sleutel opnieuw wordt gebruikt in deze functie, aangezien we deze al hebben gebruikt om de hash-waarde te berekenen.
De reden is dat hash-kaarten slaan zowel de sleutel als de waarde op in de bucketlocatie als een Kaart voorwerp.
Zoals eerder besproken, breiden alle framework-interfaces van Java-collecties zich uit Verzameling interface maar Kaart doet niet. Vergelijk de verklaring van de kaartinterface die we eerder zagen met die van Set koppel:
openbare interface Set breidt collectie uitDe reden is dat kaarten slaan niet precies enkele elementen op zoals andere verzamelingen, maar eerder een verzameling sleutel-waardeparen.
Dus de generieke methoden van Verzameling interface zoals toevoegen, toArray slaat nergens op als het gaat om Kaart.
Het concept dat we in de laatste drie alinea's hebben behandeld, zorgt voor een van de meest populaire interviewvragen over het Java Collections Framework. Het is dus de moeite waard om te begrijpen.
Een speciaal kenmerk van de hash-map is dat deze accepteert nul waarden en null-sleutels:
@Test openbare leegte gegevenNullKeyAndVal_whenAccepts_thenCorrect () {Map map = new HashMap (); map.put (null, null); }Wanneer een null-sleutel wordt aangetroffen tijdens een leggen bewerking, wordt er automatisch een laatste hash-waarde van toegewezen 0, wat betekent dat het het eerste element van de onderliggende array wordt.
Dit betekent ook dat wanneer de sleutel null is, er geen hashing-bewerking is en daarom de hashCode De API van de sleutel wordt niet aangeroepen, waardoor uiteindelijk een null-pointeruitzondering wordt vermeden.
Tijdens een leggen operatie, wanneer we een sleutel gebruiken die al eerder werd gebruikt om een waarde op te slaan, retourneert deze de vorige waarde die aan de sleutel is gekoppeld:
@Test openbare ongeldig gegevenExistingKey_whenPutReturnsPrevValue_thenCorrect () {Map map = new HashMap (); map.put ("key1", "val1"); String rtnVal = map.put ("key1", "val2"); assertEquals ("val1", rtnVal); }anders keert het terug nul:
@Test openbare leegte gegevenNewKey_whenPutReturnsNull_thenCorrect () {Map map = new HashMap (); String rtnVal = map.put ("key1", "val1"); assertNull (rtnVal); }Wanneer leggen retourneert null, het kan ook betekenen dat de vorige waarde die aan de sleutel is gekoppeld, null is, niet noodzakelijk dat het een nieuwe sleutel / waardetoewijzing is:
@Test openbare leegte gegevenNullVal_whenPutReturnsNull_thenCorrect () {Map map = new HashMap (); String rtnVal = map.put ("key1", null); assertNull (rtnVal); }De bevatKey API kan worden gebruikt om onderscheid te maken tussen dergelijke scenario's, zoals we in de volgende paragraaf zullen zien.
3. Het krijgen API
Om een object op te halen dat al in de hash-map is opgeslagen, moeten we de sleutel weten waaronder het is opgeslagen. We noemen de krijgen API en geef het het belangrijkste object door:
@Test openbare ongeldigheid whenGetWorks_thenCorrect () {Map map = new HashMap (); map.put ("key", "val"); String val = map.get ("key"); assertEquals ("val", val); }Intern wordt hetzelfde hashing-principe gebruikt. De hashCode () API van het key-object wordt aangeroepen om de initiële hash-waarde te verkrijgen:
@Test openbare leegte whenHashCodeIsCalledOnGet_thenCorrect () {MyKey-sleutel = nieuwe MyKey (1); Map map = nieuwe HashMap (); map.put (key, "val"); map.get (sleutel); }Deze keer is de hashCode API van Mijn sleutel wordt tweemaal gebeld; een keer voor leggen en een keer voor krijgen:
HashCode () aanroepen HashCode ()Deze waarde wordt vervolgens opnieuw gehasht door het interne te bellen hash () API om de uiteindelijke hash-waarde te verkrijgen.
Zoals we in de vorige sectie hebben gezien, komt deze uiteindelijke hash-waarde uiteindelijk neer op een bucketlocatie of een index van de interne array.
Het waardeobject dat op die locatie is opgeslagen, wordt vervolgens opgehaald en teruggestuurd naar de aanroepende functie.
Als de geretourneerde waarde null is, kan dit betekenen dat het key-object niet is gekoppeld aan een waarde in de hash-map:
@Test openbare leegte gegevenUnmappedKey_whenGetReturnsNull_thenCorrect () {Map map = new HashMap (); String rtnVal = map.get ("key1"); assertNull (rtnVal); }Of het kan gewoon betekenen dat de sleutel expliciet is toegewezen aan een nulinstantie:
@Test openbare leegte gegevenNullVal_whenRetrieves_thenCorrect () {Map map = new HashMap (); map.put ("key", null); String val = map.get ("key"); assertNull (val); }Om onderscheid te maken tussen de twee scenario's, kunnen we de bevatKey API, waaraan we de sleutel doorgeven en deze retourneert true als en alleen als een mapping is gemaakt voor de opgegeven sleutel in de hash-map:
@Test openbare leegte whenContainsDistinguishesNullValues_thenCorrect () {Map map = new HashMap (); String val1 = map.get ("key"); boolean valPresent = map.containsKey ("sleutel"); assertNull (val1); assertFalse (valPresent); map.put ("key", null); String val = map.get ("key"); valPresent = map.containsKey ("sleutel"); assertNull (val); assertTrue (valPresent); }Voor beide gevallen in de bovenstaande test is de retourwaarde van de krijgen API-aanroep is null, maar we kunnen onderscheiden welke welke is.
4. Collectieweergaven in Hash kaart
Hash kaart biedt drie weergaven die ons in staat stellen om de sleutels en waarden ervan als een andere collectie te behandelen. We kunnen er allemaal een krijgen sleutels van de kaart:
@Test openbare ongeldig gegevenHashMap_whenRetrievesKeyset_thenCorrect () {Map map = new HashMap (); map.put ("naam", "baeldung"); map.put ("type", "blog"); Stel sleutels in = map.keySet (); assertEquals (2, keys.size ()); assertTrue (keys.contains ("naam")); assertTrue (keys.contains ("type")); }De set wordt ondersteund door de kaart zelf. Zo elke wijziging die aan de set is aangebracht, wordt weergegeven op de kaart:
@Test openbare leegte gegevenKeySet_whenChangeReflectsInMap_thenCorrect () {Map map = new HashMap (); map.put ("naam", "baeldung"); map.put ("type", "blog"); assertEquals (2, map.size ()); Stel sleutels in = map.keySet (); keys.remove ("naam"); assertEquals (1, map.size ()); }We kunnen ook een collectieoverzicht van de waarden:
@Test openbare ongeldig gegevenHashMap_whenRetrievesValues_thenCorrect () {Map map = new HashMap (); map.put ("naam", "baeldung"); map.put ("type", "blog"); Verzamelingswaarden = map.values (); assertEquals (2, values.size ()); assertTrue (values.contains ("baeldung")); assertTrue (values.contains ("blog")); }Net als de sleutelset, elk wijzigingen die in deze collectie zijn aangebracht, worden weerspiegeld in de onderliggende kaart.
Eindelijk kunnen we een set weergave van alle inzendingen op de kaart:
@Test openbare ongeldig gegevenHashMap_whenRetrievesEntries_thenCorrect () {Map map = new HashMap (); map.put ("naam", "baeldung"); map.put ("type", "blog"); Set inzendingen = map.entrySet (); assertEquals (2, entries.size ()); voor (Entry e: entries)} Onthoud dat een hash-map specifiek ongeordende elementen bevat, daarom nemen we elke volgorde aan bij het testen van de sleutels en waarden van items in de voor elk lus.
Vaak zult u de verzamelingsweergaven in een lus gebruiken, zoals in het laatste voorbeeld, en meer specifiek met hun iterators.
Onthoud gewoon dat de iteratoren voor alle bovenstaande weergaven zijn falen snel.
Als er een structurele wijziging op de kaart wordt aangebracht nadat de iterator is gemaakt, wordt een uitzondering voor gelijktijdige wijziging gegenereerd:
@Test (verwacht = ConcurrentModificationException.class) openbare ongeldige gegevenIterator_whenFailsFastOnModification_thenCorrect () {Map map = new HashMap (); map.put ("naam", "baeldung"); map.put ("type", "blog"); Stel sleutels in = map.keySet (); Iterator it = keys.iterator (); map.remove ("type"); while (it.hasNext ()) {String key = it.next (); }}De enige toegestane structurele wijziging is een verwijderen bewerking uitgevoerd via de iterator zelf:
openbare leegte gegevenIterator_whenRemoveWorks_thenCorrect () {Map map = new HashMap (); map.put ("naam", "baeldung"); map.put ("type", "blog"); Stel sleutels in = map.keySet (); Iterator it = keys.iterator (); while (it.hasNext ()) {it.next (); it.remove (); } assertEquals (0, map.size ()); }Het laatste dat u moet onthouden over deze verzamelingsweergaven is de uitvoering van iteraties. Dit is waar een hash-map behoorlijk slecht presteert in vergelijking met de gekoppelde hash-map en tree-map van zijn tegenhangers.
Iteratie over een hash-kaart gebeurt in het ergste geval Aan) waarbij n de som is van zijn capaciteit en het aantal inzendingen.
5. HashMap-prestaties
De prestaties van een hash-map worden beïnvloed door twee parameters: Initiële capaciteit en Ladingsfactor. De capaciteit is het aantal emmers of de onderliggende array-lengte en de initiële capaciteit is simpelweg de capaciteit tijdens het maken.
De belastingsfactor of LF, kortweg, is een maatstaf van hoe vol de hash-map moet zijn na het toevoegen van enkele waarden voordat het formaat wordt gewijzigd.
De standaard initiële capaciteit is 16 en standaard belastingsfactor is 0.75. We kunnen een hash-map maken met aangepaste waarden voor initiële capaciteit en LF:
Map hashMapWithCapacity = nieuwe HashMap (32); Kaart hashMapWithCapacityAndLF = nieuwe HashMap (32, 0.5f);De standaardwaarden die door het Java-team zijn ingesteld, zijn in de meeste gevallen goed geoptimaliseerd. Als u echter uw eigen waarden moet gebruiken, wat heel goed is, moet u de gevolgen voor de prestaties begrijpen, zodat u weet wat u doet.
Wanneer het aantal hash-mapingangen het product van LF en capaciteit overschrijdt, dan rehashing komt voor, d.w.z. een andere interne array wordt gemaakt met tweemaal de grootte van de oorspronkelijke array en alle items worden verplaatst naar nieuwe bucketlocaties in de nieuwe array.
EEN lage initiële capaciteit vermindert ruimtekosten maar verhoogt de frequentie van rehashing. Opnieuw haspelen is duidelijk een erg duur proces. Als u dus veel inschrijvingen verwacht, moet u in de regel een aanzienlijk hoge aanvangscapaciteit instellen.
Aan de andere kant, als u de initiële capaciteit te hoog instelt, betaalt u de kosten in iteratietijd. Zoals we in de vorige sectie hebben gezien.
Zo een hoge initiële capaciteit is goed voor een groot aantal inzendingen in combinatie met weinig tot geen iteratie.
EEN lage initiële capaciteit is goed voor enkele inzendingen met veel iteratie.
6. Botsingen in de Hash kaart
Een botsing, of meer specifiek, een hashcode-botsing in een Hash kaart, is een situatie waarin twee of meer sleutelobjecten produceren dezelfde uiteindelijke hash-waarde en dus verwijzen naar dezelfde bucketlocatie of array-index.
Dit scenario kan optreden omdat volgens de is gelijk aan en hashCode contract, twee ongelijke objecten in Java kunnen dezelfde hashcode hebben.
Het kan ook gebeuren vanwege de eindige grootte van de onderliggende array, dat wil zeggen voordat het formaat wordt gewijzigd. Hoe kleiner deze array, hoe groter de kans op een botsing.
Dat gezegd hebbende, is het de moeite waard te vermelden dat Java een techniek voor het oplossen van botsingen met hashcodes implementeert, die we aan de hand van een voorbeeld zullen zien.
Houd er rekening mee dat het de hash-waarde van de sleutel is die de bucket bepaalt waarin het object wordt opgeslagen. En dus, als de hashcodes van twee sleutels met elkaar in botsing komen, worden hun invoer nog steeds in dezelfde bucket opgeslagen.
En standaard gebruikt de implementatie een gekoppelde lijst als de bucketimplementatie.
De aanvankelijk constante tijd O (1)leggen en krijgen operaties zullen plaatsvinden in lineaire tijd Aan) bij een aanrijding. Dit komt doordat na het vinden van de bucketlocatie met de uiteindelijke hash-waarde, elk van de sleutels op deze locatie wordt vergeleken met het opgegeven sleutelobject met behulp van de is gelijk aan API.
Om deze techniek voor het oplossen van botsingen te simuleren, passen we ons eerdere hoofdobject een beetje aan:
openbare klasse MyKey {private String-naam; privé int id; openbare MyKey (int id, String naam) {this.id = id; this.name = naam; } // standaard getters en setters @Override public int hashCode () {System.out.println ("Calling hashCode ()"); retourneer id; } // toString overschrijven voor mooie logging @Override public boolean equals (Object obj) {System.out.println ("Calling equals () voor sleutel:" + obj); // gegenereerde implementatie}}Merk op hoe we het ID kaart attribuut als de hashcode - en zo een botsing forceren.
Merk ook op dat we logboekinstructies hebben toegevoegd in ons is gelijk aan en hashCode implementaties - zodat we precies weten wanneer de logica wordt aangeroepen.
Laten we nu doorgaan met het opslaan en ophalen van enkele objecten die op een bepaald punt in botsing komen:
@Test openbare leegte whenCallsEqualsOnCollision_thenCorrect () {HashMap map = nieuwe HashMap (); MyKey k1 = nieuwe MyKey (1, "firstKey"); MyKey k2 = nieuwe MyKey (2, "secondKey"); MyKey k3 = nieuwe MyKey (2, "thirdKey"); System.out.println ("opslagwaarde voor k1"); map.put (k1, "firstValue"); System.out.println ("opslagwaarde voor k2"); map.put (k2, "secondValue"); System.out.println ("opslagwaarde voor k3"); map.put (k3, "thirdValue"); System.out.println ("waarde ophalen voor k1"); String v1 = map.get (k1); System.out.println ("waarde ophalen voor k2"); String v2 = map.get (k2); System.out.println ("waarde ophalen voor k3"); String v3 = map.get (k3); assertEquals ("firstValue", v1); assertEquals ("secondValue", v2); assertEquals ("thirdValue", v3); }In de bovenstaande test hebben we drie verschillende sleutels gemaakt - één heeft een unieke ID kaart en de andere twee hebben hetzelfde ID kaart. Sinds we gebruiken ID kaart als de initiële hash-waarde, er zal zeker een botsing komen tijdens zowel het opslaan als het ophalen van gegevens met deze sleutels.
Bovendien verwachten we, dankzij de collision resolution-techniek die we eerder zagen, dat al onze opgeslagen waarden correct worden opgehaald, vandaar de beweringen in de laatste drie regels.
Wanneer we de test uitvoeren, zou deze moeten slagen, wat aangeeft dat botsingen zijn opgelost en we zullen de geproduceerde logboekregistratie gebruiken om te bevestigen dat de botsingen inderdaad hebben plaatsgevonden:
waarde opslaan voor k1 Aanroepen hashCode () waarde opslaan voor k2 Aanroepen hashCode () waarde opslaan voor k3 Aanroepen hashCode () Aanroepen is gelijk aan () voor sleutel: MyKey [name = secondKey, id = 2] waarde ophalen voor k1 Aanroepen hashCode () ophalen waarde voor k2 Bellen hashCode () waarde ophalen voor k3 Bellen hashCode () Bellen is gelijk aan () voor sleutel: MyKey [naam = secondKey, id = 2]Merk op dat tijdens opslagbewerkingen k1 en k2 zijn met succes toegewezen aan hun waarden met behulp van alleen de hash-code.
Opslag van k3 was niet zo eenvoudig, het systeem ontdekte dat de bucketlocatie al een mapping bevatte voor k2. Daarom is gelijk aan vergelijking werd gebruikt om ze te onderscheiden en er werd een gekoppelde lijst gemaakt om beide toewijzingen te bevatten.
Elke andere volgende mapping waarvan de key-hashes naar dezelfde bucketlocatie gaan, volgt dezelfde route en vervangt uiteindelijk een van de knooppunten in de gekoppelde lijst of wordt toegevoegd aan de kop van de lijst als is gelijk aan vergelijking geeft false voor alle bestaande knooppunten.
Evenzo, tijdens het ophalen, k3 en k2 waren is gelijk aan- vergeleken om de juiste sleutel te identificeren waarvan de waarde moet worden opgehaald.
Tot slot, vanaf Java 8 worden de gekoppelde lijsten dynamisch vervangen door gebalanceerde binaire zoekbomen in botsingsresolutie nadat het aantal botsingen op een bepaalde bucketlocatie een bepaalde drempel overschrijdt.
Deze wijziging biedt een prestatieverbetering, omdat in het geval van een botsing opslag en ophalen plaatsvinden in O (logboek n).
Deze sectie is heel gebruikelijk bij technische interviews, vooral na de basisvragen over opslag en ophalen.
7. Conclusie
In dit artikel hebben we onderzocht Hash kaart implementatie van Java Kaart koppel.
De volledige broncode voor alle voorbeelden die in dit artikel worden gebruikt, is te vinden in het GitHub-project.
