Javan perussäiliöt

Javan luokkakirjasto tarjoaa alkioiden käsittelyyn samantapaisia säiliöluokkia ja lajittelufunktioita kuin esimerkiksi C++:ssa ja Pythonissa on. Käydään seuraavaksi läpi niistä muutamia. Tässä ei ole tarkoituskaan käydä läpi säiliöiden kaikkia ominaisuuksia: kannattaa ehdottomasti lisäksi tutustua säiliöluokkien varsinaiseen dokumentaatioon.

Heti alkuun on hyvä todeta yksi käytännön seikka: Javan säiliöluokat voivat tallettaa vain viitetyyppejä. Jos ehdottomasti haluat tallettaa nimenomaan primitiivityyppisiä arvoja, pitää käyttää esimerkiksi tavallisia taulukoita. Säiliöluokkien yhteydessä käytetään primitiivityyppien sijaan niitä vastaavia kääreluokkia, joskin toki primitiivityyppisiäkin muuttujia voi automaattisten (un)boxing-muunnosten ansiosta käyttää vaivattomasti säiliöluokkienkin yhteydessä.

Geneerinen luokka java.util.ArrayList on samantapainen dynaaminen taulukkotyyppi kuin C++:n vector ja Pythonin list. Geneerisyyteen palataan myöhemmin tarkemmin, mutta termi viittaa siihen, että ArrayList-luokkaa käytettäessä annetaan erillinen tyyppimääre, joka määrittää, millaisia alkioita tallettavasta taulukosta on kyse. Dynaamisuudella viitataan tässä siihen, että taulukon kokoa voi muuttaa esimerkiksi lisäämällä uusia alkioita sen perään.

Lista?

Huomaa, ettei termi “lista” tarkoita pelkästään esimerkiksi linkitettyä listaa tms. vaan yleisesti ottaen alkiojoukkoa, jossa alkioilla on jokin lineaarinen järjestys eli jossa voidaan puhua esimerkiksi ensimmäisestä, viimeisestä tai yleisesti ottaen indeksin i alkiosta. Luokka ArrayList on nimensä mukaisesti lista, joka tallettaa alkionsa taulukkoon. Emme käsittele sitä enempää tässä osiossa, mutta Java tarjoaa myös mm. luokan LinkedList, joka nimensä mukaisesti on lista, joka tallettaa alkionsa linkitettyyn listaan.

Javan geneeristen luokkien yhteydessä käytetään samantapaista syntaksia kuin C++:ssa: tyyppi annetaan hakasulkeissa luokan nimen perässä. Esimerkiksi ArrayList<Integer> on ArrayList-taulukko, johon talletetaan Integer-olioita, ja ArrayList<ArrayList<String>> on ArrayList-taulukko, jonka alkiot itsessään ovat ArrayList-taulukoita, joiden alkiot ovat String-olioita (eli kyseessä olisi kaksiulotteinen String-taulukko). ArrayList-taulukkoon voi toki tallettaa myös tavallisia taulukoita eli esim. myös ArrayList<String[]> olisi kaksiulotteinen String-taulukkotyyppi (joskin vähemmän dynaaminen sellainen). ArrayList-luokka tarjoaa mm. jäsenfunktiot:

• add(item): lisää alkion item taulukon perään (ja taulukon koko kasvaa yhdellä).

• addAll(container): lisää säiliön container sisältämät alkiot taulukon perään (aivan kuin ne lisättäisiin yksitellen add-funktiolla).

• get(i): palauttaa indeksin i alkion.

• set(i, item): asettaa alkion item olemassaolevan indeksin i kohdalle.

Seuraava esimerkkikoodinpätkä luo 10 ensimmäistä Fibonaccin lukua sisältävän ArrayList-taulukon.

// Huomaa, että oikealla puolella new-operaattorin yhteydessä hakasulut ovat tyhjät. Java sallii
// geneerisen luokan tyyppien poisjätön new-operaattorin yhteydessä, jos tyypit osataan päätellä
// sijoituksen kohteen eli tässä muuttujan fibonacci tyyppimäärityksen pohjalta.
// Toki olisi laillista käyttää täyttä muotoa new ArrayList<Integer>().
ArrayList<Integer> fibonacci = new ArrayList<>();

// Lisätään taulukon alkuun 2 ensimmäistä Fibonaccin lukua.
fibonacci.add(0); // Ensimmäinen Fibonaccin luku on 0.
fibonacci.add(1); // Toinen Fibonaccin luku on 1.
for(int i = 1; i < 10; i++) {
  // Lisätään loput Fibonaccin luvut: seuraava on aina kahden edellisen summa.
  fibonacci.add(fibonacci.get(i-1) + fibonacci.get(i));
}

// Alla tulostuu "[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]".
System.out.println(fibonacci);

Geneeriset luokat HashSet ja TreeSet ovat joukkoluokkia, jotka vastaavat C++:n luokkia unordered_set ja set sekä Pythonin luokkaa set. Ne tallettavat alkiojoukon ilman duplikaatteja eli samanlainen alkio voi sisältyä joukkoon vain kerran. Joukkoluokat toimivat selkeästi taulukkoja tehokkaammin varsinkin tilanteissa, joissa halutaan tutkia, sisältyykö jokin tietynlainen alkio joukkoon. Näiden kahden luokan ero on sama kuin C++:n vastaavilla luokilla: HashSet pohjautuu hajautukseen ja TreeSet tasapainotettuun puurakenteeseen. Käytännön kannalta toisinaan merkittävä toiminnallinen ero on, että HashSet ylläpitää alkiot (hajautuksesta johtuen) satunnaisessa järjestyksessä ja TreeSet kasvavassa suuruusjärjestyksessä.

Sekä HashSet että TreeSet tarjoavat mm. jäsenfunktiot:

• add(item): lisää alkion item joukkoon, ellei joukossa jo ole samanlaista alkiota.

• addAll(container): lisää säiliön container sisältämät alkiot joukkoon (aivan kuin ne lisättäisiin yksitellen add-funktiolla; joukon alkioiden kanssa samanlaisia ei lisätä).

• contains(item): palauttaa totuusarvon joka kertoo, onko joukossa alkiota item.

• remove(item): poistaa alkion item, jos sellainen löytyy joukosta.

TreeSet tarjoaa lisäksi alkioiden järjestykseen liittyen mm. seuraavat jäsenfunktiot:

• first(): palauttaa joukon pienimmän alkion.

• last(): palauttaa joukon suurimman alkion.

• pollFirst(): palauttaa ja poistaa joukon pienimmän alkion.

• pollLast(): palauttaa ja poistaa joukon suurimman alkion.

Seuraava koodinpätkä havainnollistaa joukkoluokkien alkeita. Useimpia edellä mainittuja funktiota ei tässä testata.

import java.util.HashSet;
import java.util.TreeSet;

class Sets {
  public static void main(String[] args) {
    HashSet<String> hashSet = new HashSet<>();
    TreeSet<String> treeSet = new TreeSet<>();
    for(String arg : args) {
      hashSet.add(arg);
      treeSet.add(arg);
    }
    System.out.print("Iterating over hashSet:");
    for(String s : hashSet) {
      System.out.print(" " + s);
    }
    System.out.println();
    System.out.print("Iterating over treeSet:");
    for(String s : treeSet) {
      System.out.print(" " + s);
    }
    System.out.println();
  }
}

Esimerkkikoodin ajo tapaan java Sets one two one three one four five two voisi tuottaa tulostuksen:

Iterating over hashSet: four one two three five
Iterating over treeSet: five four one three two

Tulostuksessa huomataan, kuinka hajautukseen pohjautuvan joukon läpikäynti tulostaa alkiot epämääräisessä järjestyksessä, mutta puuhun pohjautuvan joukon läpikäynti aakkosjärjestyksessä.

Geneeriset luokat HashMap ja TreeMap ovat sanakirjaluokkia, jotka vastaavat C++:n luokkia unordered_map ja map sekä Pythonin luokkaa dict. Ne tallettavat avain-alkio-pareja, ja sanakirjarakenteesta voi tehokkaasti etsiä tiettyä avainta vastaavan alkion. Koska avaimet ja alkiot voivat olla keskenään eri tyyppisiä, annetaan hakasuluissa pilkulla eroteltuina erikseen sekä avaimen että alkion tyypit. Esimerkiksi HashMap<String, Double> käyttäisi String-avaimia ja Double-alkioita, ja TreeMap<Integer, ArrayList<String>> käyttäisi Integer-avaimia ja ArrayList<String>-alkioita. Jälkimmäisessä avaimia vastaava alkiot olisivat siis taulukoita, ja tällainen rakenne voisi olla käyttökelpoinen tilanteessa, jossa saman avaimen alla halutaan säilyttää useita arvoja.

Sanakirjaluokkien ero on sama kuin joukkojen kohdalla: HashMap pohjautuu hajautukseen ja ylläpitää alkiot avainten suhteen satunnaisessa järjestyksessä, ja TreeMap pohjautuu tasapainotettuun puuhun ja ylläpitää alkiot avainten suhteen kasvavassa järjestyksessä. Sekä HashMap että TreeMap tarjoavat mm. jäsenfunktiot:

• put(key, item): lisää avain-alkioparin item-key, eli arvon item avaimelle key, tähän sanakirjaan. Jos avaimella oli aiemmin jo alkio, se korvautuu nyt lisätyllä alkiolla.

• putAll(map): lisää sanakirjan map kaikki avain-alkioparit tähän sanakirjaan (aivan kuin ne lisättäisiin yksitellen funktiolla put).

• containsKey(key): palauttaa totuusarvon joka kertoo, onko avaimella key talletettu alkiota.

• containsValue(item): palauttaa totuusarvon joka kertoo, onko talletettu alkiota item. Huom: tämä voi olla hidas operaatio, koska se perustunee avain-alkio parien läpikäyntiin.

• get(key): palauttaa avaimen key alkion (tai null, jos sanakirja ei sisällä kyseistä avainta).

• remove(key): poistaa avaimen key alkion (ja avaimenkin), jos sellainen löytyy.

• keySet(): palauttaa joukon, joka sisältää kaikkien talletettujen alkioiden avaimet.

• entrySet(): palauttaa joukon, joka sisältää kaikki talletetut avain-alkio-parit.

  • Avain-alkio-pareja tallettava tyyppi on Map.Entry<K, V>, missä K ja V ovat avaimen ja alkion tyypit. Tämä on varsin samankaltainen kuin C++-kielen pair.

  • Avain-alkio-parista saa luettua avaimen ja alkion jäsenfunktioilla getKey() ja getValue().

TreeMap tarjoaa lisäksi alkioiden järjestykseen liittyen mm. seuraavat jäsenfunktiot:

• first(): palauttaa joukon pienimmän alkion.

• last(): palauttaa joukon suurimman alkion.

• pollFirst(): palauttaa ja poistaa joukon pienimmän alkion.

• pollLast(): palauttaa ja poistaa joukon suurimman alkion.

Seuraava esimerkkikoodi havainnollistaa sanakirjoja muodostamalla komentoriviparametreille alkukirjaimeen perustuvan indeksin, jossa kaikki keskenään saman alkukirjaimen omaavat komentoriviparametrit on talletettu alkukirjainta vastaavan avaimen alle. Tässäkään ei testata kuin pientä osaa edellä mainituista funktioista ja käytetään vain puuhun pohjautuvia säiliöitä.

import java.util.TreeMap;
import java.util.TreeSet;

class Index {
  public static void main(String[] args) {
    TreeMap<Character, TreeSet<String>> index = new TreeMap<>();
    for(String arg : args) {
      // Käytetään avaimena ensimmäistä kirjainta, aina isona.
      Character key = Character.toUpperCase(arg.charAt(0));
      // Haetaan indeksistä avainta vastaava sanajoukko. Ellei sellaista
      // vielä ole (eli get antoi null:n), luodaan avaimelle uusi joukko.
      TreeSet<String> keyValues = index.get(key);
      if(keyValues == null) {
        keyValues = new TreeSet<>();
        index.put(key, keyValues);
      }
      // Lisätään nykyinen sana indeksissä nyt varmasti olevaan
      // sanan ensimmäistä kirjainta vastaavaan sanajoukkoon.
      keyValues.add(arg);
    }

    // Iteroidaan indeksin sisältö ensin sisäkkäisellä silmukalla, jonka
    // ulompi silmukka iteroi avaimet ja sisempi avainta vastaavan joukon.
    System.out.println("Iterating over keys and their values:");
    for(Character key : index.keySet()) {
      System.out.print("  " + key + ":");
      for(String s : index.get(key)) {
        System.out.print(" " + s);
      }
      System.out.println();
    }

    // Iteroidaan indeksin avain-alkio-parit läpi. Tässä on houkuttelevaa käyttää
    // var-tyyppimäärettä, koska iteroitavien avain-alkio-pareja tallettavien
    // olioiden tyyppi on ikävän pitkä: Map.Entry<Character, TreeSet<String>>
    System.out.println("Iterating over key-value-pairs:");
    for(var keyValue : index.entrySet()) {
      // Alla poimitaan esimerkin vuoksi parista erikseen avain kutsulla getKey()
      // ja alkio kutsulla getValue(). Lähes samanlainen tulostus olisi saatu
      // tulostamalla keyValue sellaisenaan (Map.Entry:llä on järkevähkö toString-toteutus).
      System.out.print("  " + keyValue.getKey() + ": ");
      System.out.println(keyValue.getValue());
    }
  }
}

Esimerkkikoodin suorittaminen tapaan

java Index The Java programming language is related to C and C++ but is organized rather differently with a number of aspects of C and C++ omitted and a few ideas from other languages included

tulostaa:

Iterating over keys and their values:
  A: a and aspects
  B: but
  C: C C++
  D: differently
  F: few from
  I: ideas included is
  J: Java
  L: language languages
  N: number
  O: of omitted organized other
  P: programming
  R: rather related
  T: The to
  W: with
Iterating over key-value-pairs:
  A: [a, and, aspects]
  B: [but]
  C: [C, C++]
  D: [differently]
  F: [few, from]
  I: [ideas, included, is]
  J: [Java]
  L: [language, languages]
  N: [number]
  O: [of, omitted, organized, other]
  P: [programming]
  R: [rather, related]
  T: [The, to]
  W: [with]

Edellisissä esimerkeissä kaikki säiliöt luotiin tyhjinä, antamatta rakentimelle parametria. Säiliöluokilla on yleensä myös rakennin, joka ottaa parametrina toisen säiliön ja alustaa uuden säiliön parametrin alkioilla (samaan tapaan kuin jos tehtäisiin addAll/putAll-kutsu heti alussa).

Kysymys 1

Toteutat ohjelmaa suklaamassan temperointiprosessin seuraamiseen. Tarvitset siis ohjelmaasi säiliön, johon tallennat lämpötila-arvoja saapumisjärjestyksessä syöttöjärjestyksen säilyttäen. Säiliövalintasi on:

HashSet<Double>

ArrayList<Integer>

ArrayList<Double>

Kysymys 2

Tarvitset hakusanaindeksin, johon talletetaan hakusanoja ja niiden esiintymissivut kirjassa. Hakusanat halutaan aakkosjärjestyksessä ja sivut esiintymisjärjestyksessä eli pienimmästä suurimpaan. Javan säiliöistä tiedon koostamiseen sopii:

HashMap<String, Integer>

TreeMap<String, TreeSet<Integer>>

HashMap<String, ArrayList<Integer>>

Kysymys 3

Kurssilla on useita suoritustapoja. Tarvitset kurssille ilmoittautuneiden opiskelijoiden opiskelijanumerot tallennetuiksi niin, että voidaan kätevästi tarkastaa, onko opiskelija jo ilmoittautunut kurssille ja jos ei ole, lisätä tämä mukaan. Sopivin Java säiliö opiskelijanumeroiden käsittelemiseen on:

ArrayList<String>

HashMap<String, String>

HashSet<String>

Säiliö vs. hajautuskoodi / vertailufunktio

Hajautukseen pohjautuvat säiliöt laskevat alkioille (tai sanakirjassa avaimille) hajautusarvot kutsumalla alkioiden jäsenfunktiota hashCode(). Javassa laikilla luokilla on tämä funktio vähintään Object-luokalta (kts. perintä) perityn oletustoteutuksen muodossa, mutta kyseinen oletustoteutus pohjautuu vain olion identiteettiin eikä varsinaiseen arvoon. Javan valmiiksi tarjoamilla luokilla, kuten Integer, String jne., kuitenkin pääsääntöisesti on järkevät hashCode-toteutukset. Jos toteutat oman luokan, jota mahdollisesti käytetään hajautukseen pohjautuvan säiliön yhteydessä, sinun tulisi toteuttaa luokkiisi oma hashCode-funktio. Tällaisen toteuttaminen voi olla jopa varsin suoraviivaista, koska olion hajautusarvon voinee useimmiten muodostaa sen (sopivasti valittujen) jäsenmuuttujien hajautusarvojen yhdisteenä. Jos valituille jäsenmuuttujille osataan yksitellen laskea järkevät hajautusarvot, saa niistä helposti laskettua yhdistetyn hajautusarvon Javan tarjoamalla apufunktiollla java.util.Objects.hash. Funktiolle annetaan parametreina yksi tai useampia olioita, ja se palauttaa kyseisten olioiden yksittäisten hajautusarvojen pohjalta lasketun yhdistetyn hajautusarvon. Tästä annetaan esimerkki hieman myöhemmin luokkien yhteydessä.

Puuhun pohjautuvat säiliöt tallettavat alkiot (tai avaimet) suuruusjärjestykseen, joka edellyttää, että alkioiden tyyppi joko valmiiksi tukee alkioiden välistä vertailua (tästä lisää rajapintojen yhteydessä), tai säiliöluokalle voi vaihtoehtoisesti antaa säiliön luonnin yhteydessä parametrina funktion, jolla säiliön tulisi verrata alkioita (tästä esimerkki kohta, lajittelun yhteydessä). Javan omat perystyypit tukevat valmiiksi tavanomaista kasvavaan suuruusjärjestykseen pohjautuvaa vertailua.

Palautusta lähetetään...