Map ehk kujutis

Sissejuhatus

Map ehk kujutis on andmestruktuur, mis salvestab andmeid võti-väärtus paaridena. Võtmed on unikaalsed, igale võtmele vastab üks väärtus. Väärtused omakorda võivad korduda ehk ei ole unikaalsed. Teisiti võib kujutist võtta kui sõnastikulaadset andmestruktuuri.

Kujutist kasutatakse juhul, kui on vaja kiiresti mingi võtme järgi üles leida vastavat väärtust. Lisaks kasutatakse kujutist näiteks:

• arvepidamiseks
• vahemälu (cache) jaoks

Javas on mitmeid erinevaid kujutiste implementatsioone. Erinevalt järjenditest ja hulkadest, kujutised ei realiseeri Collection liidest, vaid neil on enda liides - Map. Enim kasutatavad nendest on sellel liidesel põhinevad implementatsioonid HashMap, LinkedHashMap ja TreeMap.

HashMap

HashMap on kõige enim levinud Map implementatsioon. See salvestab elemente paisktabeli (hash table) abil, mille tõttu on operatsioonid selle kujutise implementatsiooniga toimuvad enamus kordadest konstantse ajaga.

HashMap-i loomine

HashMap-i saab luua järgnevalt:

// Empty map
HashMap<String, Integer> ages = new HashMap<>();

// Map with initial entries
HashMap<String, String> capitals = new HashMap<>();
capitals.put("Estonia", "Tallinn");
capitals.put("Latvia", "Riga");
capitals.put("Lithuania", "Vilnius");

HashMap kirjeldatakse kujul : Map<K, V> map = new HashMap<>(); kus K ja V on andmetüübid.

• K - Key, võtme andmetüüp. Kõik võtmed selles kujutises peavad olema seda andmetüüpi.
• V - Value, väärtuse andmetüüp. Kõik väärtused selles kujutises peavad olema seda andmetüüpi.

HashMap-i töö põhimõte

Sarnaselt HashSet-ile, kasutab ka HashMap sisemiselt paisktabelit. Kui lisada element kujutisse, siis:

1. Arvutatakse võtme räsiväärtus läbi hashCode() meetodi.
2. Sama räsiväärtusega võtmed grupeeritakse kokku (sisuliselt tekib "ämber" võtmetest).
3. Kui võti on sama räsiga ning ka equals() tagastab true (ehk on samad elemendid), siis sellele võtmele vastav väärtus kirjutatakse uue väärtusega üle

warninghoiatus

Pane tähele! Räsiväärtuste kontrolli viiakse läbi ainult võtme peal. Väärtust ei kontrollita. Jätke meelde, et kujutise puhul võti peab olema unikaalne, väärtused võivad korduda

Paisktabel võimaldab väga kiireid operatsioone elementidega. Elementide lisamine, eemaldamine ja olemasolu kontroll toimub enamus kordadest konstantse ajaga ehk O(1) kiirusega, kuna elemendi õige asukoht leitakse räsifunktsiooni abil ilma kõiki elemente läbi vaatamata.
Samas ei taga paisktabel elementide kindlat järjekorda. Elemendid ei esine lisamise järjekorras ega mõnes muus loogilises järjestuses, vaid sõltuvad nende räsiväärtustest ja sisemisest jaotusest tabelis.
Lisaks võib elementide paigutus ajas muutuda. Kui paisktabeli maht täitub ja toimub selle suurendamine, arvutatakse elementide asukohad uuesti ning need võivad sattuda teistesse grupeeringutesse. Seetõttu ei sobi HashMap juhul, kui elementide järjekord peab olema püsiv või etteaimatav. See on tõhus juhtudel, kus on vaja kiiret otsingut ja kontrolli suurte andmehulkade seas.

Levinumad operatsioonid

Elementide lisamine ja uuendamine

put(T key, V value) meetodit kasutatakse nii elementide lisamiseks kui ka uuendamiseks:

HashMap<String, Integer> map = new HashMap<>();
map.put("Alice", 95);
map.put("Bob", 87);
map.put("Alice", 97);    // Updates Alice's score to 97

System.out.println(map.size());  // 2

Olemas on ka replace() meetod:

map.replace("Bob", 90);    // Has the same effect as put, but only replaces if key exists, does not insert new value
map.replace("Bob", 93, 90);  // Replaces value only if current value is 90

Elementide olemasolu kontroll

boolean hasAlice = map.containsKey("Alice");     // true
boolean hasScore95 = map.containsValue(95);      // false

map.size();     // Returns size of map
map.isEmpty();  // Use instead of "if (map.size() == 0)"

Elementidele ligipääs

map.get("Alice");        // Returns 97
map.get("Charlie");     // Returns null because item has not been added to map

map.getOrDefault("Alice", 0);     // Returns 97 because "Alice" is in map
map.getOrDefault("Charlie", 0);     // Returns 0 because "Charlie" is not in map

Elementide eemaldamine

map.remove("Alice");           // Removes the entry with key "Alice"
map.remove("Bob", 93);      // Removes entry only if key and value match

map.clear();                // Removes all entries

Puuduva/olemasoleva võtme korral tegutsemine

map.putIfAbsent("baz", 999);                // Adds only if key is not already present

map.computeIfAbsent("newKey", k -> 123);    // Computes and inserts value if absent
map.computeIfPresent("existingKey", (k, v) -> v + 1);   // Updates value if key exists

Võtmete, väärtuste ja paaride itereerimine

// Iterate over keys of map
for (String key : map.keySet()) {
    // ...
}

// Iterate over values of map
for (Integer value : map.values()) {
    // ...
}

warninghoiatus

NB! Võti-väärtus paaride saamiseks tuleks vältida keySet või values kasutamist. Selle asemel tuleks kasutada Map.Entry ja entrySet lähenemist

// Bad example
for (String key : map.keySet()) {
    Integer value = map.get(key);
}

// Good example
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
}

TreeMap

TreeMap salvestab võti-väärtus paare sorteerituna võtme järgi. See sorteerimine toimub automaatselt elemendi kujutisse lisamisel.

TreeMap-i loomine

TreeMap-i saab luua järgnevalt:

TreeMap<String, Integer> ages = new TreeMap<>();
ages.put("Charlie", 28);
ages.put("Alice", 25);
ages.put("Bob", 30);

System.out.println(ages);  // {Alice=25, Bob=30, Charlie=28} - sorted by key!

TreeMap-i töö põhimõte

TreeMap töötab TreeSet-ile sarnaselt ehk sisemiselt kasutatakse red-black tree struktuuri.

1. Elemendi lisamisel lisatakse võti puustruktuuri (väärtus on lihtsalt viide).
2. Võtmeid võrreldakse omavahel et tagada sorteeritust.
3. Puu tasakaalustatakse automaatselt.

TreeMap salvestab võtmeid alati sorteeritud kujul. Vaikimisi kasutatakse selleks elementide loomulikku järjestust, kuid vajadusel saab määrata ka kohandatud võrdlusreegleid Comparator liidese abil. Andmed kujutises on igal ajahetkel korrektselt järjestatud ning neid ei ole vaja eraldi sorteerida.
Võrreldes HashMap-iga on TreeMap aeglasem. Elementide lisamine, eemaldamine ja olemasolu kontrollimine toimub O(log n) ajaga, mis tuleneb sisemisest andmestruktuurist.
TreeMap-i üheks oluliseks eeliseks on alamkujutiste loomine. Kuna elemendid on järjestatud, siis saab efektiivselt võtta näiteks kindlasse vahemikku kuuluvaid elemente. Kui tekib vajadus enda poolt loodud objekte hoida sellises kujutises, siis võtmed peavad olema omavahel võrreldavad. See tähendab, et antud klass peab realiseerima Comparable liidest või TreeMap-i loomise hetkel peab Comparator-i ette andma (saab anda argumendina kaasa loomise hetkel). Ilma võrdlusmehhanismita ei ole võimalik võtmeid puus õigesse kohta paigutada ning TreeMap kaotaks oma mõtte ära seljuhul.

Spetsiifilised TreeMap-i operatsioonid

Lisaks Map liidesest tulevatele meetoditele on TreeMap-il ka mõned omapärased meetodid oleams:

TreeMap<Integer, String> rankings = new TreeMap<>();
rankings.put(1, "Gold");
rankings.put(3, "Bronze");
rankings.put(2, "Silver");
rankings.put(5, "Fifth");
rankings.put(4, "Fourth");

// Get first and last entries
System.out.println(rankings.firstKey());    // 1
System.out.println(rankings.lastKey());     // 5
System.out.println(rankings.firstEntry());  // 1=Gold

// Get keys lower/higher than value
System.out.println(rankings.lowerKey(3));   // 2 (highest key < 3)
System.out.println(rankings.higherKey(3));  // 4 (lowest key > 3)

// Get subMap (range of entries)
Map<Integer, String> top3 = rankings.subMap(1, 4);  // {1=Gold, 2=Silver, 3=Bronze}
Map<Integer, String> topRanks = rankings.headMap(4);  // {1=Gold, 2=Silver, 3=Bronze} (< 4)
Map<Integer, String> lowerRanks = rankings.tailMap(3);  // {3=Bronze, 4=Fourth, 5=Fifth} (>= 3)

Võrdlusmehhanism

Selleks, et TreeMap korrektselt töötaks, peab sinna salvestatav andmetüüp kas realiseerima Comparable liidest või hulgale endale peab võrdlusloogika ette andma.

// Works - String implements Comparable
TreeMap<String, Integer> map = new TreeMap<>();
map.put("banana", 1);
map.put("apple", 2);  // OK - sorted alphabetically

// Works - Integer implements Comparable
TreeMap<Integer, String> numbers = new TreeMap<>();
numbers.put(5, "five");
numbers.put(2, "two");  // OK - sorted numerically

Kui nüüd proovida lisada objekti, mille klass ei realiseeri Comparable liidest, tõstatakse erind:

class Person {
    String name;
    int age;
}

TreeMap<Person, String> people = new TreeMap<>();
people.put(new Person(), "data");  // ClassCastException - Person cannot be cast to Comparable

Seda saab lahendada kahel viisil, kas klass ise realiseerib Comprarable liidest või see antakse hulga loomise hetkel kaasa:

// Sort people based on name
TreeMap<Person, String> people = new TreeMap<>((p1, p2) -> p1.name.compareTo(p2.name));

LinkedHashMap

LinkedHashMap on sarnane LinkedList-iga ja LinkedHashSet-iga, kuna see peab meeles elementide lisamise järjekorda.

LinkedHashMap-i loomine

LinkedHashMap-i saab luua järgnevalt:

LinkedHashMap<String, Integer> ages = new LinkedHashMap<>();
ages.put("Charlie", 28);
ages.put("Alice", 25);
ages.put("Bob", 30);

System.out.println(ages);  // {Charlie=28, Alice=25, Bob=30} - insertion order maintained

LinkedHashMap-i töö põhimõte

LinkedHashMap töötab LinkedList-ile sarnaselt ehk ta hoiab endas sõlmede ahelat, kus iga sõlm koosneb võtmest, viitest väärtusele ning viitest eelmisele ja järgmisele sõlmele. Erinevuseks on, et LinkedHashMap kasutab otsingute läbi viimiseks paisktabelit ja räsiväärtusi. Selline lähenemine kasutab küll rohkem mälu, kuid eeliseks on kiired operatsioonid hulkadega (võrreldav HashMap-iga).

Lisaks võimaldab LinkedHashMap ka järge hoida elementide kasutust. See tuleb kasuks näiteks vahemälu hoidmise puhul. Kui elementide kasutuse jälgimine sisse lülitada, siis elemendi pärimisel get() meetodi kaudu liigutatakse see element kujutise lõppu. Algusesse jääb see element, mida pole hiljuti kasutatud.
Näiteks:

// Create with access-order mode
LinkedHashMap<String, Integer> cache = new
LinkedHashMap<>(16, 0.75f, true);   // size of map, load factor, should access-order be tracked
cache.put("A", 1);
cache.put("B", 2);
cache.put("C", 3);

cache.get("A");  // Access "A" - moves it to end

System.out.println(cache);  // {B=2, C=3, A=1} - A moved to end after access

Millal millist eelistada?

Enamus juhtudest eelista HashMap-i kuna see on enim levinud implementatsioon. TreeMap ja LinkedHashMap tuleks kaaluda, kui sul on vaja nende spetsiifilisi omadusi, näiteks elementide automaatne sorteerimine, alamkujutiste tekitamine, sisestamise järjekorra/kasutuse olemasolu jne.

Mitme väärtuse hoidmine ühe võtme all

Kui tavapäraselt saab kujutises ühe võtme all hoida ühte väärtust, siis kasutades täiendavat andmestruktuuri, saab ühe võtme alla lisada ka mitu väärtust. Kõige lihtsam viis seda saavutada on määrates väärtuse andmetüübiks näiteks List:

Map<String, List<String>> map = new HashMap<>();

Nüüd ühele võtmele võib vastata mitu "väärtust". Väärtuste lisamine toimuks järgnevalt:

// Ensure the list exists for the given key
map.putIfAbsent("key", new ArrayList<>());

// Add a new value to the list only if the key is already present
map.computeIfPresent("key", (k, v) -> {
    v.add("valueToAdd");
    return v;
});

// Add other elements to the list
map.computeIfPresent("key", (k, v) -> {
    v.add("valueToAdd2");
    return v;
});
map.computeIfPresent("key", (k, v) -> {
    v.add("valueToAdd3");
    return v;
});

System.out.println(map);    // {key=[valueToAdd, valueToAdd2, valueToAdd3]}

warninghoiatus

Kuigi Map<Key, List<Value>> on asjakohane ja vahest täitsa vajalik muster, võib see kiiresti muutuda keeruliseks ja raskesti hallatavaks.

See muster on näiteks vajalik kui ühe võtme alla on vaja grupeerida mitut väärtust korraga. Näiteks võti tähistab kategooriat ning väärtuseks on järjend elementidest, mis antud kategooria alla kuuluvad.

Samas seda mustrit rakendades küsi endalt:

• Kas ma kasutan mitut kujutist sama andmestiku jaoks? (nt Map<String, Double> + Map<String, Integer>)
• Kas mu võtmed ja väärtused esindavad tegelikult objekti välju?
• Kas ma pean pidevalt mitut kujutist sünkroonis hoidma?

Kui vastus on "jah", siis tõenäoliselt on tegemist halva mustriga (anti-pattern) ning peaksid looma eraldi klassi nende andmete jaoks.

Kujutise halb kasutus

Üks viga mida kujutistega tihtipeale tehakse on see, et seda kasutatakse kompleksete andmete hoiustamiseks. Võtame näiteks, et programmis on vaja hoiustada valimistulemusi:

Map<String, Double> results = new HashMap<>();
results.put("REF", 31.2);
results.put("EKRE", 16.1);
results.put("KE", 15.3);

Esialgselt see lahendus toimiks, kuid probleemid esinevad, kui oleks soovi nendele andmetele midagi juurde lisada (näiteks mandaatide arv) või tulemusi sorteerida. Tuletagem meelde, et kujutised oma loomult ei ole sorteeritud ning alati ei ole mõistlik ka koheselt TreeMap-i selleks kasutama hakata (ning isegi siis, see kujutis oleks sorteeritud võtmete, mitte väärtuste järgi).

Selle probleemi üks levinud musterlahendus oleks luua abiklass, kuhu need andmed salvestada ning siis sellest klassist tehtud objektid omakorda sisestada järjendisse, kus sorteerimine on võimalik.
Näiteks:

class ElectionResult {
    private String party;
    private double votePercent;
    private int mandates;

    public ElectionResult(String party, double votePercent, int mandates) {
        this.party = party;
        this.votePercent = votePercent;
        this.mandates = mandates;
    }
}

// ...

List<ElectionResult> results = new ArrayList<>();
results.add(new ElectionResult("REF", 31.2, 37));
results.add(new ElectionResult("EKRE", 16.1, 19));
results.add(new ElectionResult("KE", 15.3, 18));

Antud lahendus loob rohkem paindlikust võimalike muudatuste suhtes ning teeb koodi üldisemalt arusaadavamaks. Kujutist puhul tuleks meeles pidada, et ta on mõeldud olukordadeks, kus ühele konkreetsele väärtusele on vaja teist konkreetset väärtust vastu saada.

Levinumad vead kujutistega tegelemisel

hashCode() ja equals()

Selleks et kujutised korrektselt saaksid töötada, peavad sisestatavad võtmed realiseerima hashCode() ja equals() meetodeid korrektselt.
Näiteks:

class Person {
    String name;
    int age;

    // Without hashCode/equals override
}

Person p1 = new Person();
p1.name = "Alice";
Person p2 = new Person();
p2.name = "Alice";

Map<Person, String> data = new HashMap<>();
data.put(p1, "data1");
data.put(p2, "data2");

System.out.println(data.size());  // 2 - treats as different keys!
System.out.println(data.get(p1)); // "data1"
System.out.println(data.get(p2)); // "data2"

Nende meetodite kohta tuleb tulevikus erladi artikkel. Sisuliselt hashCode() arvutab objekti räsiväärtuse. Räsiväärtus ei ole unikaalne ning konfliktid (hash collisions) esinevad sageli. Selleks, et lõplikult kindlaks teha kas objektid on samad kasutatakse equals() meetodit ehk kontrollitakse ka objekti sisu. Räsiväärtus võimaldab kiirelt ja efektiivselt esmast samasuskontrolli teha, kuid ainult sellele ei tohiks toetuda.

Võtmete muutmine

Elementide lisamisel kujutisse arvutatakse välja võtme räsiväärtus ning lisatakse see paisktabelisse. Kui seda võtit nüüd muuta (vt. näidet allpool), siis muutub ka selle objekti räsiväärtus. Seda väärtust ei uuendata paisktabelis ning tulemusena elemendi olemasolu kontrollivad meetodid ei leia elementi võtme järgi enam üles. Näiteks:

class MutableKey {
    String value;

    @Override
    public int hashCode() {
        return value.hashCode();
    }
}

MutableKey key = new MutableKey();
key.value = "original";

Map<MutableKey, String> map = new HashMap<>();
map.put(key, "data");

key.value = "modified";  // Changed after adding!
System.out.println(map.get(key));  // null - can't find it anymore!

Reeglina võtmed peaksid muutumatud olema. Väärtusi võib muuta.

Kujutiste võrdlemine

Javas kujutised on objektid, seega == operaatoriga neid võrrelda ei tohiks. Objektide omavaheliseks võrdlemiseks on ette nähtud .equals() meetod. Kujutised implementeerivad .equals() meetodit elementide sisu alusel. Erinevalt järjenditest elementide järjekorda ei arvestata.