Interfață de hartă în Java

Ce este Java Map Interface

Interfața Java Map face parte din cadrul Java Collection, dar nu este un subtip al interfeței Collection. Deci se comportă într-un mod diferit în comparație cu, de exemplu, Liste sau alte obiecte de colecție. Fiecare element din Map<Key, Value> reprezintă o pereche cheie-valoare. Atât Cheia, cât și valoarea sunt câteva obiecte. Toate cheile dintr-o anumită hartă sunt unice, în timp ce valorile nu sunt, așa că pot fi duplicate. Vă puteți gândi la Hartă în Java, cum ar fi un fel de dicționar sau catalog de magazin online, unde puteți găsi orice articol folosind indexul său unic. Cheia este un identificator unic al valorii dintr-o hartă. De exemplu, în Map<String, Item> String este un ID al unui articol din magazinul online. Conform documentației, Map are următoarele subinterfețe:

Legături ;

ConcurrentMap<K,V> ;

ConcurrentNavigableMap<K,V> ;

LogicalMessageContext ;

MessageContext ;

NavigableMap<K,V> ;

SOAPMessageContext ;

Sorted Map<K,V> .

Și clasele de implementare:

AbstractHarta
Atribute
AuthProvider
ConcurrentHashMap
ConcurrentSkipListMap
EnumMap
HashMap
Hashtable
IdentityHashMap
LinkedHashMap
PrinterStateReasons
Proprietăți
Furnizor
Sfaturi de randare
Legături simple
TabularDataSupport
Harta copacului
UIDdefaults
WeakHashMap

Java AbstractMap este o clasă abstractă care implementează cea mai mare parte a interfeței Map.
Java HashMap este o structură de date pentru stocarea perechilor cheie-valoare folosind un tabel hash.
Java TreeMap este o structură de date pentru a utiliza un arbore, adică afișare cu chei sortate.
WeakHashMap pentru a utiliza un tabel hash cu chei slabe, afișare cu valori care pot fi șterse de colectorul de gunoi dacă nu mai sunt folosite.
LinkedHashMap este o hartă cu ordinea de adăugare a elementelor, permite iterația în ordinea de inserare.
EnumMap extinde clasa AbstractMap pentru utilizare cu cheile enumerare.

IdentityHashMap folosește verificarea echivalenței referențiale atunci când compară documente, maparea cu cheile comparate folosind operația == în loc de metoda equals()

Aici suntem interesați de cele mai populare implementări ale Map Interface: HashMap, TreeMap și LinkedHashMap. Apropo, ordinea elementelor hărții depinde de implementările specifice. Să spunem, TreeMap și LinkedHashMap au o ordine previzibilă a elementelor, în timp ce HashMap nu.

Metode de hartă

Operațiunile principale ale oricărei hărți sunt inserarea, eliminarea și căutarea elementelor.

public Object put(cheia obiectului, valoarea obiectului) inserează un element în hartă.
public void putAll(Map map) inserează harta specificată în interiorul hărții.
public Object remove(Cheia obiect) șterge o intrare conform cheii specificate.
public Object get(Cheia obiect) returnează valoarea pentru cheia specificată.
public boolean containsKey(Cheia obiectului) caută cheia specificată din această hartă
public Set keySet() returnează o vizualizare Set care conține toate cheile
public Set entrySet() returnează o vizualizare Set cu toate cheile și valorile.

Ce este HashMap

Ce este HashMap? Este cea mai populară implementare a interfeței Map<Key,Value>. Această structură de date se bazează pe principiul hashing.

Principiul principal al funcționării HashMap: hashing

Pentru a înțelege ce este o hartă hash și cum funcționează, să vorbim mai întâi despre funcțiile hash și hash. O funcție hash este doar o funcție în sens matematic. Deci, există o valoare de intrare (un obiect, o bucată de date) și funcția o convertește folosind o regulă adecvată în valoare de ieșire - un hash. Destul de des hash este un număr hexazecimal de lungime adecvată. Regulile proceselor de conversie pot fi diferite, dar sunt supuse următoarelor principii:

O anumită intrare (obiect) are un anumit cod hash.
Dacă două obiecte sunt egale, codurile lor hash sunt de asemenea egale. Reversul nu este adevărat.
Dacă codurile hash sunt diferite, cu siguranță obiectele nu sunt egale.
Uneori, obiecte diferite pot avea același cod hash. Este un eveniment foarte puțin probabil, numit „coliziune” și o funcție hash de bună calitate ar trebui să minimizeze probabilitatea de coliziuni.

În Java, fiecare obiect are un cod hash. Este calculat prin metoda hashCode a clasei Object, clasa parentală a tuturor obiectelor Java. De obicei, dezvoltatorii înlocuiesc această metodă pentru propriile lor clase, precum și pentru metodele egale asociate acesteia.

HashMap: cum funcționează

Deci Class HashMap<K,V>, deoarece fiecare implementare Map constă din chei și valori. Stochează cheile folosind principii de hashing. În interiorul perechilor cheie-valoare HashMap sunt stocate în „găleți”, aceste compartimente construiesc împreună un „tabel”, o matrice internă de liste conectate, iar dimensiunea sa inițială este de 16. HashMap în Java utilizează codul hash al cheii pentru a determina o găleată în care perechea cheie/valoare ar trebui să mapați: Caracteristica dificilă a HashMap este că fiecare celulă (găleată) a tabelului [] păstrează nu numai o pereche, ci mai multe. Ele nu sunt stocate ca un obiect explicit (cum ar fi LinkedList), ci ca un lanț implicit. Lanțul este creat datorită faptului că fiecare pereche stochează o legătură către următoarea pereche. Adică, toate perechile HashMap sunt împrăștiate în 16 lanțuri. Când puneți o nouă pereche în tabel, se ia în considerare hash-ul cheii. Acest hash nu este o funcție hashcode încorporată în obiectul cheie. Este considerat a fi în intervalul 0-15. Perechea este adăugată la lanțul de perechi stocat în găleată cu indicele hash. Această abordare ne oferă o accelerare a căutării. În timp ce căutați o pereche după cheie, nu este nevoie să parcurgeți întregul tabel. Se ia în considerare hash-ul cheii și se verifică numai lanțul care este stocat în celula cu indexul hash. Dacă există prea multe perechi în HashMap, lanțurile devin prea lungi. Apoi dimensiunea matricei crește, hash-ul tuturor obiectelor stocate este recalculat și ele sunt împrăștiate de-a lungul noilor lanțuri.

Declarație HashMap

Dacă accesați codul HashMap de clasă, veți găsi următoarea declarație:

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable

Unde K este tipul de chei menținute de această hartă și V - tipul valorilor mapate. Acesta este un exemplu de declarație HashMap cu cheie întreagă și valoare String în codul dvs.:

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

Metode HashMap

Iată lista metodelor HashMap.

Object get(Object key) returnează valoarea pentru cheia specificată;
Object put(Key k, Value v) inserează maparea valorii cheie în hartă;
Object remove(Object key) elimină maparea pentru cheia specificată din această hartă, dacă este prezentă;
void clear() elimină toate perechile cheie-valoare din HashMap;
Object clone() returnează o copie superficială a acestei instanțe HashMap fără a clona cheile și valorile;
boolean containsKey(Object key) returnează true dacă cheia specificată este găsită în hartă, false dacă nu este;
boolean containsValue(Object Value) returnează true dacă cheia specificată este găsită în hartă, false dacă nu este;
boolean isEmpty() returnează true dacă harta este goală, false dacă nu este;
Set keySet() returnează setul de chei preluate de pe hartă;
int size() returnează cantitatea de mapare cheie-valoare;
Collection values() returnează o colecție de valori ale hărții;
Object remove(Object key) elimină perechea cheie-valoare pentru cheia specificată;
void putAll(Harta m) copiază toate elementele hărții pe cealaltă hartă.

Exemplu Java HashMap

Să creăm un program cu Java HashMap Exemplu pentru a demonstra cum funcționează:

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);
       }

   }
}

Rezultatul rulării programului:

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:
{}

Harta copacului

TreeMap în Java implementează și interfața Map<Key,Value>, dar se bazează pe structura de date arbore roșu-negru. Un Arbore este format din „noduri” și linii care leagă noduri - ramuri". Nodul „rădăcină" este în vârful arborelui. De la rădăcină, pot exista ramuri și noduri. Este o structură ierarhică, vă puteți gândi la aceste noduri ca „copii” ai rădăcinii. Nodul copil poate avea propriile copii – noduri inferioare. Nodurile fără copii sunt numite „noduri de capăt” sau „frunze”. Un arbore binar este un arbore, unde fiecare nod are zero, unu , sau doi copii. Arborele binar de căutare este o structură, în care fiecare nod intern stochează o cheie și uneori o valoare asociată și are doi sub-arbori distinși ("stânga" și "dreapta"). Un arbore de căutare binar cu auto-echilibrare este un arbore de căutare binar bazat pe noduri care își menține automat înălțimea (numărul maxim de niveluri sub rădăcină) mică în fața inserărilor și ștergerii arbitrare de elemente. Un arbore roșu-negru este un arbore binar echilibrat cu proprietățile:

Fiecare nod este fie roșu, fie negru
Rădăcina este întotdeauna neagră
Fiecare frunză este un nod NIL (un fel de gol, nul) și este neagră
Dacă un nod este roșu, copiii lui sunt cu siguranță negri.
Fiecare cale simplă de la un nod la o frunză descendentă conține același număr de noduri negre.

Caracteristicile unui TreeMap

Un TreeMap folosește o structură de date arborescentă pentru a stoca cheile ca noduri și sortează cheile utilizând algoritmul Red-Black Tree. Deci, TreeMap își păstrează intrările sortate în funcție de ordinea naturală a cheilor sale. Pentru numere, natural este ordine crescătoare, pentru șiruri de caractere — ordine alfabetică. Puteți folosi un comparator dacă trebuie să schimbați logica comenzii. Sortarea obiectelor într-un mod natural este un mare avantaj al TreeMap, precum și găsirea unor obiecte folosind diferite filtre și condiții.

Metode TreeMap

Object get(Object key) returnează valoarea cheii corespunzătoare;
Object put(Cheie obiect, valoare obiect) inserează o mapare într-o hartă;
Object remove(Object key) elimină maparea pentru această cheie dacă TreeMap o conține;
boolean containsKey(Object key) returnează true dacă această hartă conține o mapare pentru cheia specificată;
boolean containsValue(Valoare obiect) returnează true dacă TreeMap mapează una sau mai multe chei la valoarea specificată;
Object firstKey() returnează prima cheie în prezent din harta sortată;
Object lastKey() returnează ultima cheie în prezent din harta sortată;
void putAll(Map map) copiază toate mapările de pe harta specificată pe hartă;
Set entrySet() returnează o vedere setată a mapărilor
int size() returnează cantitatea de mapări cheie-valoare
Collection values() returnează o vizualizare a colecției a valorilor
Object clone() returnează o copie superficială a TreeMap
void clear() elimină toate mapările din TreeMap
SortedMap headMap(Object key_value) returnează o vedere a porțiunii de hartă mai mică decât parametrul key_value
Set keySet() returnează o vizualizare Set a cheilor conținute în harta arborescentă
SortedMap subMap(K dinKey, K toKey) returnează o vizualizare a porțiunii acestei hărți ale cărei chei variază de la fromKey, inclusiv, la toKey, exclusiv
Object firstKey() returnează prima cheie din TreeMap.

Exemplu 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);
   }
}

Rezultatul rulării programului:

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 este o structură de date care combină liste legate și hărți hash. Într-adevăr, LinkedHashMap extinde clasa HashMap și implementează interfața Map, dar despre ce este vorba despre listele legate? Declarația LinkedHashMap:

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

Acest nou linkedHashMap moștenește proprietăți din HashMap (cum ar fi table, loadFactor, threshold, size, entrySet), de asemenea, primește două proprietăți speciale:

antetul este capul unei liste dublu legate. În timpul inițializării, se indică
accessOrder indică cum să obțineți acces la elemente folosind iteratorul. Dacă este adevărat, în ordinea ultimului acces. Dacă este fals, accesul va fi în ordinea în care au fost introduse elementele.

Această listă legată definește ordinea iterațiilor. De obicei, este ordinea introducerii cheilor în hartă.

Metode LinkedHashMap

Object get(Object key) returnează valoarea la care este mapată cheia specificată sau null dacă această hartă nu conține nicio mapare pentru cheie
void clear() elimină toate mapările de pe hartă.
boolean containsKey(Object key) returnează adevărat dacă elementul specificat este mapat de una sau mai multe chei
boolean removeEldestEntry(Map.Entry eldest) returnează adevărat dacă harta elimină cea mai veche intrare de pe hartă
Set<Map.Entry<K,V>> entrySet() returnează o vizualizare Set a mapărilor conținute în această hartă
void forEach(acțiunea BiConsumer<? super K,? super V>) execută acțiunea dată pentru fiecare intrare din această hartă până când toate intrările au fost procesate sau acțiunea aruncă o excepție.
Object getOrDefault(Object key, V defaultValue) returnează valoarea la care este mapată cheia specificată. Dacă harta nu conține o mapare pentru cheie, returnează defaultValue.
Set<K> keySet() returnează o vizualizare Set a cheilor conținute în hartă
boolean removeEldestEntry(Map.Entry<K,V> cel mai vechi) returnează adevărat dacă această hartă ar trebui să elimine cea mai veche intrare
void replaceAll(BiFunction<? super K,? super V,? extins V> function) înlocuiește fiecare valoare de intrare cu rezultatul invocării funcției date pe acea intrare până când toate intrările au fost procesate sau funcția aruncă o excepție.
Collection<v>values() returnează o vizualizare de colecție a valorilor conținute în hartă

Exemplu 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);
       }
   }

Aici creăm un nou LinkedHashMap, adăugând cinci elemente, apoi îl imprimăm folosind iteratorul și într-un mod clasic. După cum puteți vedea, LinkedHashMap menține ordinea de inserare. După aceasta, ștergem un element de pe harta noastră, apoi îl adăugăm pe cel nou și mai târziu - încă un element cu cheia, care este deja pe hartă. Acesta înlocuiește vechea valoare mapată la această cheie. Rezultatul rulării programului:

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}

Comparație HashMap, TreeMap, LinkedHashMap

HashMap, TreeMap și LinkedHashMap sunt implementări ale interfețelor Map. HashMap și LinkedHashMap sunt structuri de date care codifică cheile. TreeMap folosește ordinea naturală a cheilor sale pentru a organiza un arbore de căutare. Ordin:

HashMap nu menține nicio ordine.
TreeMap sortează intrările în ordine crescătoare a cheilor.
LinkedHashMap menține ordinea de inserare.

Chei nule:

HashMap și LinkedHashMap vă permit să aveți o cheie nulă.
LinkedHashMap nu permite cheile nule în cazul în care cheile folosesc ordinea naturală sau Comparator nu acceptă compararea pe legile nule.

Să avem un exemplu de hartă Java care include toate cele trei implementări analizate în acest articol:

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);
    }
}

Iată rezultatul rulării acestui program:

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}

După cum putem vedea, ordinea elementelor în HashMap nu este evidentă, în treeMap depinde de chei, în LinkedHashMap este vorba despre ordinea de inserare. Dacă încercăm să punem cheia nulă în linkedHashMap, vom obține NullPointerException, dar în linkedHashMap1, unde cheile sunt String, o putem face. O hartă hash este cea mai bună implementare a hărții de uz general. Oferă viteză maximă de căutare, stocare rapidă și operațiuni de recuperare, dar ar trebui să vă amintiți despre ordinea sa haotică. O hartă hash legată moștenește avantajele HashMap și primește o comandă pentru chei. Cu toate acestea, conține linkedList, care este relativ costisitoare din punct de vedere al memoriei. este mai lent decât HashMap în căutare și puțin mai lent pentru adăugare/eliminare din cauza menținerii listei legate. O hartă arborescentă stochează cheile sortate în ordine crescătoare. In orice caz, Pentru a consolida ceea ce ați învățat, vă sugerăm să urmăriți o lecție video de la Cursul nostru Java

Mai multe lecturi:
Cum să actualizați valoarea unei chei existente în HashMap Metoda HashMap getOrDefault în Java Metoda KeySet în java.util.Map