5.3 Yleiskäyttöisiä tietorakenteita, geneerisyyttä, ArrayList<E> ja HashMap<K,V>

Luku esittelee lyhyesti kaikkien luokkien yhteisen yliluokan Object, käännösaikaista tyyppiparametrointia eli geneerisyyttä sekä ns. kokoelmaluokat, ArrayList<E> ja HashMap<K,V>.

ArrayList on vaihtelevan kokoinen taulukko, jonne voi tallettaa mitä tahansa Javan olioita. HashMap on rakenne, jolla voi luoda ns. assosiaatiolistoja: olioon voidaan liittää jokin toinen olio ja ensimmäisellä assosioda toinen, esimerkiksi "avaimella voidaan hakea arvoa".

Luokissa ArrayList<E> ja HashMap<K,V> käytetetään hyväksi ns. geneerisyyttä, käännösaikaista tyyppiparametrointia. Tähän hyödylliseen ja voimakkaaseen tekniikkaan ei peruskursseilla ole kovin paljon aikaa käytettävissä. Esimerkit kuitenkin antavat mallin välineiden käyttöön omissa ohjelmissa.

• Luokka Object
• Vähän geneerisyydestä, hyvin vähän...
• ArrayList<E>
• HashMap<K,V>
• Esimerkki ArrayList<E>-olioista HashMap<K,V>-rakenteessa

Luokka Object

Luokassa Object on joitakin metodeita, jotka siis periytyvät kaikille muille luokille. Vanha tuttu on toString(), joka on tapana aliluokissa korvata (override) sopivasti. Object-luokan toString() muodostaa oliosta kuin oliosta merkkijonoesityksen, joka kertoo olion luokan ja heksadesimaaliluvun, joka antaa tietoa olion sijainnista tulkin tietorakenteissa, esim. Pikkuvarasto@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 polymorfisesti korvattu aliluokissa (ks. luku 4.5), valitaan kuitenkin 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 Pikkuvarasto();
    // ...
    otus.vieVarastoon(3.14);                  // väärin!
    ((Pikkuvarasto)otus).vieVarastoon(3.14);  // sallittu
    //...
    
    otus = "BÖÖ!";
    int i;
    i = otus.length();           // väärin!
    i = ((String)otus).length(); // sallittu

Olion luokkaa voi kysellä instanceof-operaatiolla:

    Object otus = new Pikkuvarasto(); 
    // ...
    if (otus  instanceof  Pikkuvarasto)
      ((Pikkuvarasto)otus).vieVarastoon(3.14);
    else if (otus  instanceof String)
      i = ((String)otus).length();

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ä kokoelmia, koska ne ovat tyyppiturvallisempia.

Huom: Kun käytetään geneerisiä luokkia, instanceof-operaatio on yleensä huonoa ohjelmointia ja usein myös tarpeetonta.

Vähän geneerisyydestä, hyvin vähän...

    Object otus = new Pikkuvarasto();
    // ...
    ((Pikkuvarasto)otus).vieVarastoon(3.14);
    double määrä = ((Pikkuvarasto)otus).otaVarastosta(30);

Uudessa Javassa tyyppiin voidaan liittää käännösaikaisia tyyppiparametretreja:

public class GenTyyppi<T> {

  private T kenttä;
    
  public GenTyyppi() { }

  public GenTyyppi(T kenttä) {       
    this.kenttä = kenttä;
  }
     
  public void printtaa() {
    System.out.println(kenttä);
  }
}

public class GenEsim {

  public static void main(String[] args) {

    GenTyyppi<String> x  = new GenTyyppi<String>();
    GenTyyppi<String> xx = new GenTyyppi<String>("BÖÖ");

    x.printtaa();
    xx.printtaa();

    GenTyyppi<Pikkuvarasto> y  = new GenTyyppi<Pikkuvarasto>();
    GenTyyppi<Pikkuvarasto> yy = new GenTyyppi<Pikkuvarasto>(
                                    new Pikkuvarasto(10, "Mehu"));
    y.printtaa();
    yy.printtaa();
  }
}

null
BÖÖ
null
(Mehu: 10.0)

Koska jo kääntäjä tietää todellisen tyyppiparametrin, se osaa generoida itse tarvittavat tyyppimuunnokset! Alkeistyypit (esim. 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äärepaperiluokkin" käyttäminen on tehty helpoksi ns. "autoboxing"-menettelyn avulla. Koska kääntäjä tietää tietorakenteeseen vietyjen alkeistyyppisten arvojen tyypin, se osaa automaattisesti generoida tarvittavat tyyppimuunnokset tietoja rakenteeseen vietäessä ja niitä sieltä otettaessa. Esimerkki nähdään ArrayList-luokan esittelyn lopussa.

Tällä peruskurssilla geneerisyydestä opetellaan vain geneeristen luokkien ArrayList<E> ja HashMap<K,V> käyttöä. Omien geneeristen luokkien ohjelmointi on melko monitahoista ja vaatii tietoa enemmän kuin kurssille mahtuu. Pieni esimerkki erääseen harjoitustehtävään liittyen saattaa silti olla mielenkiintoista luettavaa: KokeileGenVertTaulukkoa.java.

[Lisätietoa Javan geneerisyydestä löytyy tietenkin Sunin sivuilta sekä erityisesti 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ä vikaa...]

ArrayList<E>

Joitakin ArrayList-luokan välineitä:

• public ArrayList<E>() luo tyhjän ArrayList-olion, jonka alkioiksi kelpaavat E-tyyppiset arvot
• public void add(E o) lisää E-tyyppisen arvon listan viimeiseksi komponentiksi eli listan loppuun
• public void add(int index, E element) lisää E-tyyppisen arvon element listan alkioiksi, jonka indeksi on index; jos (index < 0 || index > size()), heitetään IndexOutOfBoundsException
• public boolean contains(Object elem) true, jos lista sisältää arvon elem, muuten false
• public E get(int index) palauttaa arvonaan listan alkion annetulla indeksillä; jos (index < 0 || index > size()), heitetään IndexOutOfBoundsException
• public int indexOf(Object elem) ja int indexOf(Object elem, int index) etsivät elem-oliota vektorista; palauttavat -1, jos ei löydy (equals-vertailu!)
• public E remove(int index) poistaa listasta alkion kohdasta index; jos (index < 0 || index > size()), heitetään IndexOutOfBoundsException
  Huom: Koska int-parametrinen remove-operaatio poistaa indeksin perusteella, int-alkioisesta ArrayList-oliosta, poisto sisältöön perustuen on ohjelmoitava: remove(new Integer(poistettava)), joka siis käyttää seuraavaa kuormitettua versiota remove-operaatiosta:
• public boolean remove(Object obj) poistaa listasta löytyvän ensimmäisen olion obj ja palauttaa false, jos poistettavaa ei löytynyt (equals-vertailu!)
• public E set(int index, E element) korvaa kohdassa index olevan arvon uudella; jos (index < 0 || index > size()), heitetään IndexOutOfBoundsException
• public int size() komponenttien lukumäärä
• public String toString() tuottaa merkkiesityksen ArrayList-oliosta; komponentit muokataan niiden omilla toString()-metodeilla

• ...

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

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

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

HashMap<K,V>

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ä:

• public HashMap<K,V>() luo tyhjän HashMap-olion, jonka avaimiksi kelpaavat K-tyyppiset oliot, arvoiksi kelpaavat V-tyyppiset oliot (tarvittaessa alkeistyypin arvot "autoboxataan" vastaaviksi olioiksi)

• public V put(K key, V value) liitää HashMap-olioon assosiaation key-->value; jos avaimeen jo liittyi assosiaatio, metodi korvaa sen uudella ja palauttaa arvonaan vanhan merkityksen; jos avainta ei löytynyt, metodi palauttaa arvon null
• public V get(Object key) palauttaa arvonaan key-avaimeen liitetyn arvon; jos avainta ei löydy, metodi palauttaa arvon null (metodi palauttaa null-arvon myös, jos avaimen assosiaationa oli null; nämä kaksi tapausta voi erottaa toisistaan containsKey-metodin avulla)
• public boolean containsKey(Object key) true jos avainten joukossa on key, muuten false
• public boolean containsValue(Object value) true jos yhteen tai useampaan avaimeen liittyy arvo value, muuten false
• public V remove(Object key) poistaa avaimen key ja siihen liittyneen arvon, ts. assosiaatio key-->value poistetaan; palauttaa arvonaan poistetun arvon value; jos avainta ei löydy, palautetaan null (metodi palauttaa null-arvon myös, jos avaimen assosiaationa oli null; nämä kaksi tapausta voi erottaa toisistaan containsKey-metodin avulla)
• public String toString() tuottaa merkkiesityksen HashMap-oliosta, komponentit muokataan niiden omilla toString()-metodeilla

• ...

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>-olioista HashMap<K,V>-rakenteessa

Tässä pikku esimerkissä HashMap<K,V>-olioon talletetaan avaimiksi sanoja ja assosioitaviksi arvoiksi sanojen luetteloita ArrayList<E>-olioina:

import java.util.*;

public class HAEsimerkki {

  public static void main(String[] args) {

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

    ArrayList<String> sanoja = new ArrayList<String>();

    sanoja.add("kissa");
    sanoja.add("hiiri");
    sanoja.add("hevonen");

    seuraajat.put("eläimiä", sanoja);

    ArrayList<String> lukuja = new ArrayList<String>();
    lukuja.add("134");
    lukuja.add("-23");
    lukuja.add("9871");

    seuraajat.put("lukuja", lukuja);

    System.out.println(seuraajat);
  }
}

Takaisin luvun 5 sisällysluetteloon.