Map-tietorakenne

Olemme ohjelmointi 1:ssä käyttäneet listoja (ArrayList<String>) tai taulukoita (String[]), kun olemme halunneet käsitellä useita saman typpisiä asioita. Javassa on myös lukuisia muita kokoelmia, joihin voimme koota dataa. Kokoelma tarkoittaa yksinkertaisesti oliota, joka kokoaa alkioita yhteen (Oracle.com).

Tällä sivulla:

• Java Collections Framework
• Hajautustaulu eli HashMap
• Materiaalia
• Mapin tyypin määrittely
  • Arvojen lisääminen ja hakeminen
  • Numeroiden käsitteleminen mapissa
  • Uuden arvon asettaminen
  • Arvojen poistaminen (remove) ja tarkastaminen (containsKey)
  • Null-viittaukset
  • Usean arvon tallentaminen samalle avaimelle
  • Map:in koko sisällön läpikäynti
    • Avaimet
    • Arvot
    • Avaimet ja arvot pareina

Java Collections Framework

Java Collections Framework sisältää mm. seuraavat rajapinnat ja luokat:

• List (ArrayList ja LinkedList)
• Map (HashMap ja TreeMap)
• Set (HashSet ja TreeSet)
• Queue, Stack, jne (ei käsitellä tällä kurssilla)

Tällä kurssilla keskitymme Javan Map-tietorakenteeseen ja erityisesti sen HashMap-toteutukseen, eli ns. hajautustauluun.

Opiskelun tueksi erinomainen lisämateriaali hajautustauluista on Helsingin yliopiston MOOC-oppimateriaali https://ohjelmointi-20.mooc.fi/osa-8/2-hajautustaulu, jonka sisältöä on lainattu myös tässä materiaalissa ja materiaaliin liittyvissä videoissa ja tehtävissä.

Hajautustaulu eli HashMap

“Hajautustaulu eli HashMap on ArrayListin lisäksi eniten käytettyjä Javan valmiiksi tarjoamia tietorakenteita. Hajautustaulua käytetään kun tietoa käsitellään avain-arvo -pareina, missä avaimen perusteella voidaan lisätä, hakea ja poistaa arvo.”

Agile Education Research –tutkimusryhmä, mooc.fi

HashMap ja Map voidaan ottaa käyttöön import-komennolla seuraavasti:

import java.util.HashMap;
import java.util.Map;

Toisin kuin listoissa, arvoja ei käsitellä pelkästään numeeristen indeksien avulla, vaan voimme määritellä avaimiksi halutessamme vaikka merkkijonoja:

HashMap<String, String> postinumerot = new HashMap<>(); // tai new HashMap<String, String>();

postinumerot.put("00710", "Helsinki");
postinumerot.put("90014", "Oulu");
postinumerot.put("33720", "Tampere");
postinumerot.put("33014", "Tampere");

System.out.println(postinumerot.get("00710")); // tulostaa "Helsinki"

Yllä esitetty koodi muodostaa kutakuinkin seuraavan laisen tietorakenteen, jossa jokainen avain viittaa sille asetettuun arvoon:

Toinen samankaltainen käyttötapaus avain-arvo-pareille on myöhemmin tällä kurssilla käsiteltävä JSON-tietorakenne, jossa data näyttäisi tältä:

{
    "00710": "Helsinki",
    "90014": "Oulu",
    "33720": "Tampere",
    "33014": "Tampere"
}

Tämä esimerkki on lainattu Helsingin yliopiston Agile Education Research –tutkimusryhmän oppimateriaalista, joka on lisensoitu Creative Commons BY-NC-SA-lisenssillä.

Materiaalia

PowerPoint-kalvot

### Mikä on Javan Map-tietorakenteen tarkoitus?

- [ ] Map on tietorakenne, joka säilyttää alkioita järjestettynä listana.
- [x] Map on tietorakenne, joka yhdistää avain-arvo -pareja.
- [ ] Map on tietorakenne, joka tallentaa alkioita taulukkomuodossa.

Mapin tyypin määrittely

Hajautustaulua luodessa tarvitaan kaksi tyyppiparametria:

• avainmuuttujan tyyppi
• lisättävän arvon tyyppi.

Tyyppiparametrit määritellään kulmasulkeisiin, kuten teimme Ohjelmointi 1:ssä ArrayList:in kanssa. Koska tyyppiparametreja on tällä kertaa kaksi, ne kirjoitetaan pilkulla eroteltuna:

Map<String, String> tietovarasto = new HashMap<>(); // tai new HashMap<String, String>();

Kulmasuluissa ensimmäinen tyyppi on avaimen tyyppi, toinen tallennettavien arvojen tyyppi. Tässä esimerkissä molemmat sattuvat olemaan merkkijonoja, eli String.

Arvojen lisääminen ja hakeminen

Arvot lisätään map-tietorakenteeseen put-metodilla. Put tarvitsee kaksi parametria: avaimen sekä arvon:

Map<String, String> tietovarasto = new HashMap<String, String>();
tietovarasto.put("avain", "arvo");

Mikäli mapissa on jo valmiiksi olemassa sille annettu arvo, vanha arvo korvataan uudella.

Arvojen hakeminen mapista puolestaan tehdään get-metodilla:

String arvo = tietovarasto.get("avain");
System.out.println(arvo);

Get-metodille annetaan parametrina se avain, jonka arvoa haetaan.

Tämä esimerkki on lainattu Agile Education Research –tutkimusryhmän oppimateriaalista, joka on lisensoitu Creative Commons BY-NC-SA-lisenssillä.

### Miten uusi avain-arvo -pari lisätään Map-tietorakenteeseen?
- [ ] Käyttämällä metodia add(key, value)
- [ ] Käyttämällä metodia insert(key, value)
- [x] Käyttämällä metodia put(key, value)

### Kuinka saadaan arvo Map-tietorakenteesta annetun avaimen perusteella?
- [x] Käyttämällä metodia get(key)
- [ ] Käyttämällä metodia retrieve(key)
- [ ] Käyttämällä metodia fetch(key)

Numeroiden käsitteleminen mapissa

Kuten listoille, myös map-tietorakenteeseen voidaan tallentaa ainoastaan viittaustyyppisiä arvoja. Siksi esimerkiksi int-tyypin sijaan käytetään Integer-tyyppiä:

Map<String, Integer> opintopisteet = new HashMap<>();

// Lisätään arvoja tietyille avaimille:
opintopisteet.put("swd1tn001", 5);
opintopisteet.put("swd1tn002", 5);

// Haetaan yksi arvo:
int pisteet = opintopisteet.get("swd1tn002");
System.out.println(pisteet); // 5

// Haetaan kaikki avaimet:
Set<String> avaimet = opintopisteet.keySet();
System.out.println(avaimet); // [swd1tn002, swd1tn001]

PowerPoint-kalvot

Uuden arvon asettaminen

Mapissa on jokaista avainta kohden korkeintaan yksi arvo. Jos siihen lisätään uusi avain-arvo-pari, jossa avain on jo aiemmin liittynyt toiseen hajautustauluun tallennettuun arvoon, vanha arvo katoaa hajautustaulusta.

Map<String, String> numerot = new HashMap<>();
numerot.put("Uno", "Yksi");
numerot.put("Dos", "Zwei");
numerot.put("Uno", "Ein"); // korvaa aikaisemman arvon!

String kaannos = numerot.get("Uno");
System.out.println(kaannos); // Ein

Tämä esimerkki on lainattu Agile Education Research –tutkimusryhmän oppimateriaalista, joka on lisensoitu Creative Commons BY-NC-SA-lisenssillä.

Arvojen poistaminen (remove) ja tarkastaminen (containsKey)

HashMap<String, String> countries = new HashMap<>();
countries.put("Suomi", "Finland");
countries.put("Ruotsi", "Sweden");
countries.put("Norja", "Norway");

countries.containsKey("Ruotsi"); // true

countries.remove("Ruotsi");

countries.containsKey("Ruotsi"); // false

Null-viittaukset

Jos mapista haetaan arvoa avaimella, jota ei löydy, palautuu tuloksena null-arvo, eli tyhjä viittaus.

Mikäli null-arvon sijasta halutaan käyttää jotain toista arvoa oletusarvona, voidaan käyttää mapin getOrDefault-metodia:

Map<String, Integer> pistelaskuri = new HashMap<>();
pistelaskuri.put("Matti", 10);

// Avain "Matti" löytyy, joten paluuarvoksi tulee 10:
int matti = pistelaskuri.getOrDefault("Matti", 0);

// Avainta "Teppo" ei löydy, joten paluuarvoksi tulee 0:
int teppo = pistelaskuri.getOrDefault("Teppo", 0);

getOrDefault on erityisen hyödyllinen tilanteissa, joissa null-arvo aiheuttaisi poikkeuksen. Esimerkiksi int-tyyppisten arvojen yhteydessä null-arvoa ei voida asettaa int-tyyppiseen muuttujaan, joten tämä rivi aiheuttaisi poikkeuksen:

int teppo = pistelaskuri.get("Teppo"); // null-arvoa ei voida asettaa int-muuttujaan! 💥

Usean arvon tallentaminen samalle avaimelle

Map:issa voidaan säilyttää vain yhtä arvoa kutakin avainta kohden. Säilytettävät arvot voivat kuitenkin olla muita kokoelmia. Map:issa voidaan siis säilyttää samalla avaimella useita arvoja, kun käsittelemmä Mapin sisällä listoja tai muita kokoelmia.

Tässä esimerkissä säilytämme map-tietorakenteessa listoja, joista kukin sisältää tiettyyn maahan kuuluvien kaupunkien nimiä:

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

List<String> fi = new ArrayList<String>();
fi.add("Helsinki");
fi.add("Espoo");
fi.add("Vantaa");

List<String> sv = new ArrayList<String>();
sv.add("Tukholma");
sv.add("Visby");

maat.put("Suomi", fi);
maat.put("Ruotsi", sv);

System.out.println(maat);

Tämä esimerkki tulostaa maiden nimet, joihin liittyy listat kaupungeista:

{Suomi=[Helsinki, Espoo, Vantaa], Ruotsi=[Tukholma, Visby]}

PowerPoint-kalvot

Map:in koko sisällön läpikäynti

Mapin sisältö voidaan käydä helposti läpi joko avainten, arvojen tai avain-arvo –parien osalta:

• keySet() palauttaa kaikki mapin avaimet
• values() palauttaa kaikki mapin arvot
• entrySet() palauttaa avaimet ja arvot pareina

Avaimet

Jos haluamme käsitellä mapin arvoja, ne voidaan pyytää mapin keySet-metodilla:

Set<String> avaimet = data.keySet();

// Käydään läpi kaikki avaimet:
for (String avain : avaimet) {
    System.out.println(avain);
}

Kuten yllä olevasta koodista huomaamme, keySet palauttaa paluuarvona setin eli joukon. Setit eivät ole keskeinen osa tätä kurssia, mutta voit ajatella settiä listana, jonka alkioilla ei ole taattua järjestystä, ja joka ei salli arvojen duplikaatteja. Setin käyttämiseksi yllä olevaan esimerkkiin tarvitaan lisäksi seuraava import-rivi:

import java.util.Set;

Arvot

Mapin kaikki arvot voidaan pyytää hieman vastaavasti values-metodilla:

Collection<Integer> arvot = data.values();

// Käydään läpi kaikki arvot:
for (Integer arvo : arvot) {
    System.out.println(arvo);
}

values-metodin palauttama Collection-tyyppi on kaikkia Javan kokoelmia yhdistävä rajapintaluokka:

“The root interface in the collection hierarchy. A collection represents a group of objects, known as its elements. Some collections allow duplicate elements and others do not. Some are ordered and others unordered.”

Oracle. Collection. https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html

Collection-tyyppisen kokoelman käyttämiseksi tarvitset luokkaasi seuraavan import-rivin:

import java.util.Collection;

Avaimet ja arvot pareina

Toisinaan avaimia ja arvoja halutaan käsitellä pareittain. Tällöin voimme hyödyntää entrySet-metodia, joka palauttaa monimutkaiselta näyttävän tietorakenteen:

Set<Entry<AvaimenTyyppi, ArvonTyyppi>>

Tämä kokoelma voidaan kuitenkin käydä läpi esimerkiksi for-toistorakenteella kuten aikaisemmat:

Set<Entry<String, Integer>> parit = data.entrySet();

// Käydään läpi kaikki avain-arvo -parit:
for (Entry<String, Integer> pari : parit) {
    System.out.println("Avain: " + pari.getKey());
    System.out.println("Arvo: " + pari.getValue());
}

Jokaisella Entry-oliolla on siis sisässään yksi avain ja yksi arvo, jotka saadaan yllä olevan esimerkin mukaisesti pyydettyä getKey()- ja ketValue()-metodeilla.

Entry-olioiden käyttäminen muuttujissa edellyttää luokan alkuun seuraavan import-rivin:

import java.util.Map.Entry;