Oppimateriaali perustuu Arto Wiklan vanhaan ohjelmointisivustoon. Materiaalin copyright © Arto Wikla. Materiaalia saa vapaasti käyttää itseopiskeluun. Muu käyttö vaatii luvan.

XII Ohjelmointitekniikkaa: geneeriset kokoelmaluokat ArrayList<E>, HashMap<K,V> ja HashSet<E>

(Muutettu viimeksi 29.10.2010, sivu perustettu 26.10.2010. Arto Wikla)

Luku esittelee lyhyesti kaikkien luokkien yhteisen yliluokan Object ja ns. käännösaikaista tyyppiparametrointia eli geneerisyyttä. Geneerinen kokoelmaluokka ArrayList<E> kerrataan. Uutuuksina tutustutaan HashMap<K,V>- ja HashSet<E>-luokkiin sekä lyhyesti myös rajapintaluokkiin List ja Map.

ArrayList on kuin vaihtelevan mittainen taulukko, jonne voi tallettaa mitä tahansa Javan olioita. HashMap on rakenne, jolla voi luoda ns. assosiaatiolistoja: ensin olioihin liitetään toisia olioita ja sitten assosioidaan, haetaan, olioihin liitettyjä olioita: "avaimella haetaan avaimeen liitetty arvo". HashSet on joukon yksi mahdollinen toteutus.

Luokissa ArrayList<E> ja HashMap<K,V>, HashSet<E>, ..., käytetetään hyväksi ns. geneerisyyttä, käännösaikaista tyyppiparametrointia. Tähän hyödylliseen ja voimakkaaseen tekniikkaan ei peruskursseilla valitettavasti ole mahdollista syvällisesti perehtyä. Esimerkit kuitenkin antavat mallia välineiden käyttölle omissa ohjelmissa.

Kaiken huipulla Object

Luokka Object on ainoa Javan luokka, jolla ei ole yliluokkaa. Kaikki muut luokat ovat sen välillisiä tai välittömiä aliluokkia.

Luokassa Object on joitakin metodeita, jotka siis periytyvät kaikille muille luokille. Vanha tuttu on toString(), joka on tapana aliluokissa syrjäyttää (override) sopivasti. Object-luokan toString() muodostaa oliosta kuin oliosta merkkijonoesityksen, joka kertoo olion luokan ja heksadesimaaliluvun, joka antaa tietoa olion sijainnista tulkin tietorakenteissa tyyliin Kuulaskuri@80cb94a.

Object-tyyppiselle muuttujalle voi sijoittaa minkä tahansa olioarvon, mutta tällöin tuolle oliolle voi soveltaa vain Object-luokan metodeita. Jos näitä on syrjäytetty aliluokissa, polymorfismin ansiosta valitaan – opittuun tapaan! – olion oman luokan metodi.

Kun Object-tyyppisen muuttujan arvona on jonkin aliluokan ilmentymä ja tuolle oliolle halutaan soveltaa metodia, jota Object-luokasta ei löydy, olioarvo on muunnettava explisiittisellä tyyppimuunnoksella olion oman luokkan tyyppiin, esim:

Object otus = new Kuulaskuri();
otus.seuraavaKuu();                  // väärin!
((Kuulaskuri)otus).seuraavaKuu();;   // sallittu

otus = "BÖÖ!";  // BÖÖ on Object-tyyppinen siinä kuin kuulaskurikin!
int i;
i = otus.length();           // väärin!
i = ((String)otus).length(); // sallittu

Huom: Komponenttiin viittaus (".") sitoo tiukemmin kuin eksplisiittinen tyyppimuunnos, siksi nuo sulkeet tyyppimuunnoksen ympärillä ovat välttämättömät.

Ennen ns. geneeristen kokoelmaluokkien tuloa Javaan (versiossa 1.5) yleiskäyttöisten tietorakenteiden alkiotyyppinä käytettiin Objectia, tai jos alkioiden järjestysrelaatio oli tarpeen, tyyppinä käytettiin Comparable-rajapintaluokkaa. Nykyään on syytä käyttää geneerisiä tyyppejä, koska ne ovat turvallisempia ja helppokäyttöisempiä.

Geneeristen tyyppien perusidea

Ennen geneeristen tyyppien ja ns. autoboxing-piirteen sisällyttämistä Javaan yleisten tietorakenteiden käyttäminen oli melko vaivalloista, koska alkiot täytyi itse muuntaa sopivan tyyppisiksi sekä rakenteeseen vietäessä, että sieltä otettaessa – siihen tapaan kuin yllä jouduttiin menettelemään Object-tyyppisen muuttujan kohdalla:

Geneerisen tyypin laatimisen idea on kertoa kääntäjälle muodollisin tyyppiparametrein, minkä tyyppisistä komponenteista ja osista jokin luokka rakennetaan.

Laaditaan äärimmäisen yksinkertaisena esimerkkinä "säiliö", jonne voidaan säilöä olio, jonka tyyppi on mikä vain luokka:

public class Sailio<T> {  // T on muodollinen tyyppiparametri
  private T tieto;
  public Sailio() { }
  public T getArvo() {return tieto;}
  public void setArvo(T tieto) {this.tieto = tieto;}
  public String toString() {return tieto.toString();}
}

Luokasta Sailio voi luoda ilmentymiä vain antamalla muodolliselle tyyppiparametrille todellisena parametrina jokin todellinen tyyppi:

public class SailioEsimerkkeja {
  public static void main(String[] args) {

   Sailio<String> merkkkijonosailo = new Sailio<String>();
   merkkkijonosailo.setArvo("Kissantassu");
   System.out.println(merkkkijonosailo);
   merkkkijonosailo.setArvo("Koiranpentu");
   System.out.println(merkkkijonosailo);

   Sailio<Kuulaskuri> kuulaskurisailo = new Sailio<Kuulaskuri>();
   Kuulaskuri kuu = new Kuulaskuri();
   kuulaskurisailo.setArvo(kuu);;
   System.out.println(kuulaskurisailo.getArvo().moneskoKuu());
   kuu.seuraavaKuu();
   System.out.println(kuulaskurisailo.getArvo().moneskoKuu());

   Sailio<Integer> lukusailo = new Sailio<Integer>(); // näin muodollisesti
   lukusailo.setArvo(new Integer(123));               // pitäisi tehdä...
   System.out.println(lukusailo);

   lukusailo.setArvo(321);           // mutta kääntäjä osaa hoitaa homman
   System.out.println(lukusailo);    // ohjelmoijan puolesta: autoboxing!
  }
}

Ohjelma tulostaa:

Kissantassu
Koiranpentu
1
2
123
321

Koska jo kääntäjä tietää todellisen tyyppiparametrin, se osaa generoida itse tarvittavat tyyppimuunnokset! Alkeistyypit (int, double, boolean, ...) eivät kuitenkaan kelpaa todelliseksi tyyppiparametriksi, vaan niiden sijalla on käytettävä vastaavia luokkia, ns. "käärepaperiluokkia" ("wrapper") Integer, Double, Boolean, ...

Näiden "käärepaperiluokkien" käyttäminen on tehty helpoksi ns. "autoboxing"-menettelyn avulla. Koska kääntäjä tietää tietorakenteessa pidettävien alkeistyyppisten arvojen tyypin, se osaa automaattisesti generoida tarvittavat tyyppimuunnokset tietoja rakenteeseen vietäessä ja niitä sieltä otettaessa.

Tällä kurssilla geneerisyydestä esimerkkeinä nähdään vain luokat ArrayList<E>, HashMap<K,V> ja HashSet<E>. Tarjolla on monia monia muita, joihin on hyvä perehtyä, kun alkaa todellisia ohjelmia laatimaan.

Omien geneeristen luokkien ohjelmointi on melko monitahoista ja suoraan sanottuna vaativaa. Perusteellista lisätietoa Javan geneerisyydestä löytyy Angelika Langerin erinomaisilta sivuilta "Java Generics FAQs - Frequently Asked Questions".

[Javan geneerisyys ei ole välttämättä vielä lopullisessa asussaan; Langer toteaa eräässä tiedotteessaan: "My conclusion from looking into the issues is: refrain from overloading, unless you are sure you fully understand overload resolution in Java, which is a mystery even to me". Jos geneerisyyden erikoisasiantuntijallakin on ongelmia ymmärtää metodien kuormittamisen ja geneerisyyden suhdetta, on luultavaa, että jossakin on vielä jotakin mätää...]

Kertausta: ArrayList<E>

Luokka ArrayList<E> määrittelee "vaihtelevanmittaiset" taulukot, joiden komponenttityyppi annetaan ArrayList-oliota luotaessa. Komponentit numeroidaan tavallisen taulukon tapaan indeksein alkaen nollasta. Komponenttien lisääminen ja poistaminen muuttaa lisäys- ja poistokohtaa seuraavien komponenttien indeksejä.

Joitakin ArrayList-luokan välineitä:

Vanha esimerkki: Ohjelma lukee ensin joukon lukuja. Sitten lukuja voi poistaa. Lopuksi ohjelma tulostaa jäljelle jääneiden lukujen summan:

import java.util.*;
public class ArrayListEsim {
  private static Scanner lukija = new Scanner(System.in);
  public static void main(String[] args) {

    ArrayList<Integer> taulu = new ArrayList<Integer>();

    int luku;

    System.out.println("Syötä lukuja, nolla lopettaa.");    
    luku = lukija.nextInt();
    while (luku != 0) {
      taulu.add(luku);
      luku  = lukija.nextInt();
    }

    System.out.println(taulu);

    System.out.println("Syötä poistettavia lukuja, nolla lopettaa.");
    luku = lukija.nextInt();
    while (luku != 0) {
      boolean oli = taulu.remove(new Integer(luku));
      if (oli)         // remove(int index) poistaisi indeksin kohdalta!
        System.out.println(taulu);
      else 
        System.out.println("Ei löydy");
      luku = lukija.nextInt();
    }
 
    System.out.println(taulu);
    System.out.println("Alkioiden summa = " + summa(taulu));
  }

  private static int summa(ArrayList<Integer> tau) {
    int summa = 0; 
    for (int i=0; i < tau.size(); ++i) // for-each olisi tässä toki luontevampi,
        summa += tau.get(i);           // ks. ohjelma linkin takana
    return summa;
  }
}

Ilman edellä jo mainostettua geneerisyyden mahdollistamaa "autoboxingia" esimerkiksi lauseet

     taulu.add(luku);
     ...
     summa += tau.get(i);

joutuisi kirjoittamaan paljon kömpelömmin:

     taulu.add(new Integer(luku));
     ...
     summa += ((Integer)(tau.get(i))).intValue();

HashMap<K,V>

Luokan HashMap ilmentymä on rakenne, jolla K-tyyppisistä arvoista, avaimista ("key"), voi assosioida V-tyyppisiä arvoja ("value"). "Avaimella siis haetaan avaimeen liitettyä arvo".

Tavallaan HashMap-olio on kuin taulukko, jota "indeksoidaan" K-tyyppisillä arvoilla, ei kokonaisluvuilla..

Luokan ArrayList tapaan HashMap on aina "riittävän" suuri. Avaimena käytettävien arvojen luokan K on toteutettava hashCode- ja equals-metodit (tästä ei tässä enempää; mm. String, Integer, Double, ..., kelpaavat tyyppiparametria K vastaavaksi todelliseksi tyypiksi).

Joitakin HashMap-luokan välineitä:

Esimerkki: "Kielenkäännösohjelma". Ohjelma opiskelee ensin sanapareja "sana alkukielelellä" - "sana käännettynä toiselle kielelle". Sitten ohjelma tarjoaa sanojen käännöspalvelun:

import java.util.*;
public class HashMapEsim {
  private static Scanner lukija = new Scanner(System.in);
  public static void main(String[] args) {

    HashMap<String,String> taulu = new HashMap<String,String>();
    String sana1, sana2;

    do {
      System.out.print("Sana alkukielellä? (tyhjä lopettaa) ");
      sana1 = lukija.nextLine();
      if (sana1.equals("")) 
        break;

      if (taulu.containsKey(sana1)) {
        System.out.println("Sana \"" + sana1 + "\" löytyy jo!");
        System.out.println("Vanha käännös " + "\"" +taulu.get(sana1) + 
                           "\" jää voimaan!");
        continue; // uusi alkukielinen sana
      }

      System.out.print("Sana käännettynä?  (tyhjä lopettaa) ");
      sana2 = lukija.nextLine();
      if (sana2.equals("")) 
        break;  // syöttö loppui!

      // nyt molemmat sanat ovat ei-tyhjiä ja ensimmäinen on uusi

      taulu.put(sana1, sana2);

    } while (true); // loppuu jomman kumman sanan ollessa ""

    System.out.println(taulu);

    do {
      System.out.print("Minkä sanan käännöksen haluat tietää? " +
                       "(tyhjä sana lopettaa) "); 
      sana1 = lukija.nextLine();
      if (sana1.equals(""))
        break;  // kysely loppui!
      
      if (!taulu.containsKey(sana1))
        System.out.println("Sanan \"" + sana1 +"\" käännös on tuntematon!");
      else
        System.out.println("Sanan \"" + sana1 + "\" käännös on \"" + 
                           taulu.get(sana1) +"\"");

    } while (true); // loppuu tyhjään sanaan
  }
}

Esimerkki: ArrayList<E>-olioita HashMap<K,V>-rakenteessa

Geneerisiä rakenteita voidaan tietenkin myös yhdistellä ihan samaan tapaan kuin kurssilla aiemmin on tehty vaikkapa olioiden taulukoita ja olioita, joiden sisällä on taulukoita. On siis mahdollista esimerkiksi luoda ArrayList<E>-oliota, joiden komponentit ovat HashMap<K,V>-oliota. Ja päinvastoin.

Esimerkki: HashMap<K,V>-olioon talletetaan avaimiksi henkilöiden nimiä ja assosioitaviksi arvoiksi kunkin henkilön omistamia leluja ArrayList<E>-olioina:

import java.util.*;
public class KunkinKamat {
  public static void main(String[] args) {

    HashMap<String, ArrayList<String> > kenen =
        new HashMap<String,ArrayList<String>>();

    ArrayList<String> maijanKamat = new ArrayList<String>();
    maijanKamat.add("nukke");
    maijanKamat.add("nalle");
    maijanKamat.add("kudin");

    ArrayList<String> pekanKamat  = new ArrayList<String>();
    pekanKamat.add("auto");
    pekanKamat.add("mittari");
    pekanKamat.add("miekka");

    kenen.put("Maija", maijanKamat);
    kenen.put("Pekka", pekanKamat);

    System.out.println(kenen);

    System.out.println(kenen.get("Maija"));
    System.out.println(kenen.get("Pekka"));

    System.out.println(kenen.get("Maija").get(0));
    System.out.println(kenen.get("Pekka").get(2));

    // ...
  }
}

Ohjelman tulostus:

{Maija=[nukke, nalle, kudin], Pekka=[auto, mittari, miekka]}
[nukke, nalle, kudin]
[auto, mittari, miekka]
nukke
miekka

Esimerkki: HashSet<E>-olioita HashMap<K,V>-rakenteessa

Edellisen esimerkin voisi toteuttaa myös sellaisena, että kullakin lapsella on joukko leluja, ei listaa leluista. Ts. esimerkiksi Maijalla voisi olla vain yksi "nukke". Joukon toteuttamiseen tarjolla on mm. geneerinen luokka HashSet<E>, jota käyttäen sama esimerkki voitaisiin toteuttaa luontevasti seuraavaan tapaan:

import java.util.*;
public class KunkinKamatSet {
  public static void main(String[] args) {

    HashMap<String, HashSet<String> > kenen =
        new HashMap<String,HashSet<String>>();

    HashSet<String> maijanKamat = new HashSet<String>();
    maijanKamat.add("nukke");
    maijanKamat.add("nalle");
    maijanKamat.add("kudin");

    HashSet<String> pekanKamat  = new HashSet<String>();
    pekanKamat.add("auto");
    pekanKamat.add("mittari");
    pekanKamat.add("miekka");

    kenen.put("Maija", maijanKamat);
    kenen.put("Pekka", pekanKamat);

    System.out.println(kenen);

    System.out.println(kenen.get("Maija"));
    System.out.println(kenen.get("Pekka"));
/*
    System.out.println(kenen.get("Maija").get(0));
    System.out.println(kenen.get("Pekka").get(2));
*/
    // ...
  }
}

Tulostus:

{Maija=[kudin, nalle, nukke], Pekka=[miekka, mittari, auto]}
[kudin, nalle, nukke]
[miekka, mittari, auto]

Kannattaa perehtyä hyvin käyttökelpoisen HashSet<E>-luokan API-kuvaukseen!

Rajapintaluokkia: List<E>, Map<K,V>,

Tämän luvun esimerkkisovelluksissa käytettiin geneeristen kokoelmien konkreettisia toteutuksia sellaisinaan. Tällöin sitouduttiin yhteen ja vain yhteen toteutukseen tietorakenteesta, vaikka Javan rikkaassa kokoelmavalikoimassa, (Collections Framework) tarjolla on erilaisia vaihtoehtoisia toteutuksia samalle käyttäytymiselle.

Esimerkiksi peräkkäistalletetulle ArrayList-toteutukselle on vaihtoehto LinkedList, joka sisäisesti perustuu ns. linkitetyn listan käyttöön. Samoin HashMap-luokan tarjoamalle palvelulle on vaihtoehtoisia toteutuksia. Tietorakenteiden kurssilla saa sitten oppia, miten erilaisia toteutuksia arvioidaan.

Tuollaisia palvelujoukkoja on koottu yhteen rajapintaluokiksi List<E>, Map<K,V>, jne.

"Oikeassa ohjelmoinnissa" sovelluksissa käytetään muuttujien ja kenttien tyyppeinä näitä rajapintaluokkia, ei yksittäisiä toteutuksia. Näin on helppo vaihtaa kokoelman toteutusta, jos jokin muu kuin ensin valittu osoittautuu paremmaksi, tehokkaammaksi tms.

Edellä nähdyssä ArrayListEsim-esimerkissä kaikki muut ArrayList-ilmaukset korvataan pelkällä rajapintaluokalla ArrayList, paitsi itse olion luonti:

import java.util.*;
public class ArrayListEsim {
  private static Scanner lukija = new Scanner(System.in);
  public static void main(String[] args) {

    List<Integer> taulu = new ArrayList<Integer>();

    ...
  private static int summa(List<Integer> tau) {
    int summa = 0; 
    for (int i=0; i < tau.size(); ++i) // for-each olisi tässä toki luontevampi,
        summa += tau.get(i);           // ks. ohjelma linkin takana
    return summa;
  }
}

Nyt voidaan vaihtaa pelkästään List-olion toteutus (ja juokan nimi):

import java.util.*;
public class LinkedListEsim {
  private static Scanner lukija = new Scanner(System.in);
  public static void main(String[] args) {

    List<Integer> taulu = new LinkedList<Integer>();

    ...
  private static int summa(List<Integer> tau) {
    int summa = 0; 
    for (int i=0; i < tau.size(); ++i) // for-each olisi tässä toki luontevampi,
        summa += tau.get(i);           // ks. ohjelma linkin takana
    return summa;
  }
}

Kuten sanottu, Tietorakenteiden kurssilla sitten opitaan periaatteita, joilla tietorakenteiden eri toteutuksia voidaan vertailla ja arvioida.