Nädal 11

Kogumid (Collections)

Kogumid

Mitmed andmestruktuurid on Javas kasutusel olnud juba esimestest versioonidest peale. Viimastes versioonides on püütud kogumeid süstemaatiliselt käsitleda ja asjassepuutuv koondada ühte raamistikku - Java Collections Framework. Hea ülevaade on Java veebilehestikus.

Java Collections Framework on ülesehitatud liidestest ja klassidest (ka abstraktsetest). Liidestes määratakse teatud kogumiliigi (nt. list või järjekord) jaoks vajalikud meetodid, mis siis konkreetsetes klassides realiseeritakse. Liidestes Collection ja Map on universaalsemad meetodid, alamliidestes tuuakse juurde spetsiifilisemad. Põhiliideste hierarhia on toodud joonisel. (Tegelikult on liideseid märksa rohkem.)

Massiiv (järjend)

Massiiv on mõnes mõttes kõige olulisem kogumitüüp - paljud teised kogumid on realiseeritud kasutades massiivi. Massiivi kasutamine on mugav juhul, kui elementide arv on massiivi loomisel teada ja see ei muutu. Kuna massiivi elemendid hoitakse arvuti mälus järjest, siis massiivi suurendamiseks on tarvis leida uus ja suurem vaba mälukoht ning vana massiivi elemendid sinna "ümber kolida".

Käesolevas praktikumis me otseselt massiiviga (järjendiga) ei tegele, oleme ju seda varem teinud.

List (ArrayList, LinkedList)

Kuigi listidest oli juba juttu 4. praktikumis, vaatame siin neid põhjalikumalt. Listis on elemendid teatud järjestuses. Põhilise erinevusena massiivist saab listi pikkust programmi töö käigus vabalt muuta, elemente saab erinevatesse kohtadesse lisada ja neid eemaldada. Listile omased operatsioonid on määratud liideses java.util.List.

import java.util.List; 
import java.util.ArrayList; 
import java.util.Arrays; 
... 
List<Integer> list1 = new ArrayList<>(); 
list1.add(42);
List<Integer> list2 = new ArrayList<>(); 
list2.addAll(Arrays.asList(1,2,3)); 
// veel lühem 
List<Integer> list3 = Arrays.asList(1,2,3); 
// eelnevad read juba vihjasid, et järjendi saab konvertida listiks 
Integer[] jarjend = {1, 2, 3};
List<Integer> list4 = Arrays.asList(jarjend); 
// listi konvertimine järjendiks on veidi peenem töö 
Integer[] jarjend2 = list4.toArray(new Integer[0]); 
// listist koopia tegemine
List<Integer> list5 = new ArrayList<>(list4);

Näide: list ja lambda-avaldised

Alates Java 8. versioonist on võimalik kasutada listi elementide puhul ka meetodit forEach koos lambda-avaldistega:

// prindi elemendid ükshaaval välja
list1.forEach(elem -> System.out.println(elem));

Lambda-avaldisi saab kasutada ka listi elementide sorteerimiseks. Nt. sõnede sorteerimiseks sõne pikkuse järgi:

List<String> list6 = Arrays.asList("aa","ccc","b");
// compareTo lambda, mis võtab parameetriks kaks sõne ja tagastab int
Collections.sort(list6, (s1, s2) -> s1.length() - s2.length());

Ilma lambda avaldiseta sorteerimisel meetodiga Collections.sort(list6); sorteeritakse sõned tähestiku järjekorras.

Liidese List realisatsioonid

ArrayList on enamasti kõige efektiivsem viis listide realiseerimiseks - elementide hoidmiseks kasutatakse massiivi.

LinkedList hoiab oma elemente mälus eraldi, kasutades listi kooshoidmiseks viitasid. LinkedList on efektiivne, kui on tarvis tihti lisada andmeid listi etteotsa või keskele (või kui on vaja elemente sealt eemaldada). Samas elemendi võtmine indeksi järgi on aeglasem kui ArrayList-i puhul.

// näide listi keskele elemendi lisamisest 
// NB! töötab ka ArrayList-iga 
List<Integer> list2 = new LinkedList<Integer>(); 
list2.addAll(Arrays.asList(1,2,3)); 
list2.add(2, 54); // '54' saab 3. elemendiks (indeksiga 2)

Nagu ka siin näites, on koodis alati soovitatav panna muutuja või argumendi tüübiks liides List, mitte ArrayList või LinkedList. See tagab, et meetodid, mis seda muutujat kasutavad, teavad, et nad teevad tööd listiga, aga ei tea täpselt, millise realisatsiooniga. Siis on võimalik listi loomisel valida vastavalt olukorrale sobivam realisatsioon (ArrayList või LinkedList) või seda vajadusel muuta, kuid ülejäänud koodi muutma ei pea.

Enesekontroll

Magasin (Stack)

Magasin (stack) on listil põhinev andmestruktuur, mille põhimeetoditeks on pop ja push. Meetod push(x) lisab elemendi x listi lõppu (magasini tippu). Meetod pop() eemaldab magasini tipuelemendi (listi viimase elemendi) ja tagastab selle. Viimasena magasini pandud elemendid pääsevad välja kõige esimesena, seetõttu kasutatakse selle andmestruktuuri kohta ka nimetust LIFO (last-in-first-out).

// sisseehitatud liides Deque (double-ended queue) sisaldab magasini funktsionaalsust
Deque<Integer> magasin = new ArrayDeque<>(); 
magasin.push(1); 
magasin.push(2); 
magasin.push(3); 
System.out.print(magasin.pop()); // 3
System.out.print(magasin.pop()); // 2
System.out.print(magasin.pop()); // 1

Magasini kasutab näiteks Java virtuaalmasin pidamaks arvet parasjagu pooleli olevate meetodi väljakutsete üle. Programmi käivitades lisatakse magasini põhja peameetodi väljakutse info (parameetrite ja lokaalsete muutujate väärtused jms). Kui koodi täitmisel jõutakse mingi abimeetodi väljakutseni, siis lisatakse magasini uus kirje tolle väljakutse info hoidmiseks. Kui abimeetod lõpetab, siis vastav kirje pop-itakse ja magasini tipp viitab jälle eelmisele meetodile. Programmi magasini on näha näiteks püüdmata erindi tekkimisel:

java.lang.NullPointerException
    at MinuProgramm.teisendaArvuks(MinuProgramm.java:27)
    at MinuProgramm.loeFailistNumbreid(MinuProgramm.java:23)
    at MinuProgramm.main(MinuProgramm.java:18)

Järjekord (Queue)

Järjekord (queue) on järjestatud elementide kogum, kus elemente lisatakse (add) alati järjendi lõppu ja neid eemaldatakse (remove) alati järjendi algusest. Sellest tulenevalt kutsutakse seda FIFO (first-in-first-out).

// sisseehitatud liides Queue sisaldab järjekorra funktsionaalsust
Queue<String> linnadMidaKülastada = new LinkedList<>();
linnadMidaKülastada.add("Tartu"); // lisab lõppu
linnadMidaKülastada.add("Paide");
linnadMidaKülastada.add("Tallinn");
while (!linnadMidaKülastada.isEmpty()) {
  System.out.println(linnadMidaKülastada.remove()); // eemaldab algusest
}

Järjekorda kasutatakse paljude algoritmide osana (nt graafide läbimisel), samuti saab sellega organiseerida programmi tööd (nt kasutaja sisestab käsureal käsud ja hiljem hakatakse neid täitma).

Kujutus (Map)

Kujutus (map, pythonis dictionary) sisaldab endas kaheosalisi kirjeid, mille esimest komponenti nimetatakse võtmeks ja teist väärtuseks. Ühes kujutuses saab sama võtmega olla vaid üks kirje. Kujutust kasutatakse siis, kui mingi identifikaatori järgi on vaja kiiresti leida üles sellele vastav info. Kujutuse (liidese Map) realisatsiooniks on parim valik enamasti HashMap.

Järgnevas näites kasutatakse HashMapi telefoniraamatu imiteerimiseks:

Map<String, Integer> telefoniraamat = new HashMap<>(); 
telefoniraamat.put("Peeter Peet", 5562356); 
telefoniraamat.put("Mari Maasikas", 53438956); 
System.out.println("Mari number on " + telefoniraamat.get("Mari Maasikas")); 

Paneme tähele, et kolmnurksulgude vahele on vaja märkida kaks tüübiparameetrit: üks võtme jaoks (String) ja teine väärtuse jaoks (Integer).

Kui get-iga küsitakse mingit elementi, mida kujutuses ei leidu, siis tagastatakse null.

Kujutuse kohta võidakse öelda veel sõnastik (dictionary on Pythoni vastav andmestruktuur) või paisktabel (hashtable).

Enesekontroll

Malle Kalle
Herbert Jaanus
Kalle Pille
Jaanus Margus
Pille Janne

> java Pidu näidis.txt Janne

Malle

Hulk (Set)

Hulk (set) on andmestruktuur, kus ei saa esineda korduvaid elemente. Hulga elemente ei säilita sisestamise järjekorras. Põhilised hulga meetodid on elemendi lisamine (add), sisalduvuse kontroll (contains) ja hulga läbimine (tsükliga läbi vaatamine).

Set<String> meiliAadressid = new HashSet<>();
meiliAadressid.add("example@example.com");
meiliAadressid.add("java-is-awesome@example.com");
meiliAadressid.add("example@example.com"); // aadressi ei lisata, sest see on juba olemas
for (String aadress : meiliAadressid) {
  System.out.println(aadress);
}

List<String> nimed = Arrays.asList("Märt", "Taavi", "Aivar", "Marina", "Aivar");
// loob hulga, kus on kõik nimed ühekordselt
Set<String> unikaalsedNimed = new HashSet<>(nimed); 
// teeme hulgast uuesti listi
nimed = new ArrayList<>(unikaalsedNimed);

Tavaliselt kasutatakse hulki unikaalsete elementide leidmiseks ja hulga-operatsioonide jaoks: ühisosa, ühend ja vahe.

Andmestruktuuride kombineerimine

Mõnikord on tarvis andmestruktuure kombineerida. Näiteks kui me tahaksime teada mingi teksti kohta, millised sõnad võivad üksteisele järgneda, siis me võiksime analüüsi tulemust esitada kujutusega, kus kirje võtmeks on sõna ja väärtuseks sellele vahetult järgnevate sõnade hulk:

Map<String, Set<String>> järgnevused = new HashMap<>();
järgnevused.put("kala", new HashSet<>());
järgnevused.get("kala").add("ujub");
järgnevused.get("kala").add("praadima");

Enesekontroll

Equals ja hashcode

Vaatame lihtsat näidiskoodi listide kasutamise kohta.

public class Klient {
  private int kliendiNumber;
  public Klient(int kliendinumber) {
    this.kliendiNumber = kliendinumber;
  }
}

public class Test {
  public static void main(String[] args) {
    Klient klient = new Klient(123);
    Klient samaKlient = new Klient(123);
    List<Klient> kliendid = Arrays.asList(klient);
    System.out.println(kliendid.contains(samaKlient)); // false

    Integer kliendiNumber = new Integer(123);
    Integer samaKliendiNumber = new Integer(123);
    List<Integer> kliendiNumbrid = Arrays.asList(kliendiNumber);
    System.out.println(kliendiNumbrid.contains(samaKliendiNumber)); // true
  }
}

Võrdse kliendinumbriga kliendid oleks loogiline samaväärseteks lugeda. Selle järgi peaks esimesena ekraanile ilmuma true, aga ilmub false. Miks see nii on? Miks List<Integer> puhul ilmub analoogse näite korral ekraanile true?

Listi contains meetod läbib terve listi ja võrdleb iga elementi otsitava väärtusega. Võrdlemiseks rakendatakse objektidel nende equals meetodit. Paljud Java sisseehitatud tüübid (nt String ja mähisklassid) on selle meetodi üle katnud, nii et võrreldaks andmete sisu. Klass Klient ei kata seda üle, seetõttu kasutatakse Object klassi varianti, mis võrdleb lihtsalt objektide viitasid. Sama loogikaga töötavad ka HashMap ja HashSet klassid, aga nemad kasutavad lisaks equals meetodile ka hashcode meetodit, et andmestruktuuri tööd optimeerida.

Sellest, kuidas equals ja hashcode meetodid õigesti üle katta, räägitakse lähemalt Algoritmid ja andmestruktuurid aines. Praegu jäta lihtsalt meelde, et andmestruktuurid ei oska sinu objektide sisu uurida ja peavad iga isendit erinevaks.

Geneerilised tüübid

Praktiliselt kõik andmestruktuurid, mida oleme kasutanud, sisaldavad oma tüübis lisaks tavaliselt tüübi nimele ka <T> (näiteks List<String>). Mida tähendab <T>? Kas List<String> ja List<Integer> on sama liides või erinevad liidesed?

Tuletame kõigepealt meelde, kuidas toimivad meetodite parameetrid ja argumendid. Meetodi defineerimisel on tihti kasulik jätta koodis mingi väärtus lahtiseks ja tähistada seda tundmatut väärtust parameetriga. See võte võimaldab meetodi erinevatel väljakutsetel määrata parameetrile erinevad väärtused (kasutada erinevaid argumente) ja muuta niimoodi kood universaalsemaks.

Geneerilised tüübid (generic types) on liidesed või klassid, mille definitsioonis on jäetud mõned tüübid lahtiseks - konkreetse tüübi asemel on kasutatud tüübiparameetrit. Taolise klassi või liidese kasutamisel peab need parameetrid väärtustama konkreetsete tüüpidega. Näiteks List on geneeriline tüüp, millele saab anda ühe tüübiparameetri, mis määrab Listis sisalduvate elementide tüübi. Tüübiparameetrid märgitakse kolmnurksete sulgude vahel ja need võimaldavad samal klassil töötada erinevat tüüpi andmetega.

Vaatame näidet klassist, mis oskab enda sees hoida suvalist teist tüüpi objekti (välja arvatud primitiivi):

public class Hoidja<T> {

  private T hoitavObjekt;

  public T getHoitavObjekt() {
    return hoitavObjekt;
  }

  public void setHoitavObjekt(T hoitavObjekt) {
    this.hoitavObjekt = hoitavObjekt;
  }
}

public class Test {
  public static void main(String[] args) {
    Hoidja<Integer> intHoidja = new Hoidja<>();
    intHoidja.setHoitavObjekt(99);
    Hoidja<String> strHoidja = new Hoidja<>();
    strHoidja.setHoitavObjekt("hurraa!");
  }
}

Ärge unustage, et tüübiparameeter on parameeter! Klassi deklaratsioonis on deklareeritud tüübiparameeter ja määratud parameetri nimeks T (sobib suvaline nimi, hea tava on kasutada lühikesi suurtest tähtedest koosnevaid nimesid). Objekti loomisel tuleb tüübiparameeter väärtustada. Sellest võib mõelda nii, et objektis asendatakse selle peale igal pool muutuja T etteantud konkreetse tüübiga. Näitekoodis on intHoidja puhul antud tüübiparameetriks Integer ja strHoidja puhul String. Ühel klassil saab olla ka mitu (komaga eraldatud) tüübiparameetrit. Näiteks liideses Map<K, V> määrab üks parameeter võtme tüübi ja teine parameeter väärtuse tüübi.

Geneerilises klassis saab kasutada tüübiparameetri väärtust igal pool, kuhu saaks kirjutada mingi konkreetse tüübi nime - isendiväljade ja parameetrite tüübina, tagastustüübina, kohaliku muutuja tüübina jne.

Piiratud tüübiparameetrid (bounded type parameters)

Lihtne tüübiparameeter <T> laseb parameetriks määrata ükskõik millise Object alamklassi. Kompilaator lubab T tüüpi objektidel seetõttu kutsuda ainult Object klassi meetodeid. Vajadusel on võimalik piirata, mis klasside alamklasse on võimalik tüübiparameetriks määrata:

public class NumbriHoidja<N extends Number> {

  private N hoitavNumber;

  public N getHoitavNumber() {
    return hoitavNumber;
  }

  public void setHoitavNumber(N hoitavNumber) {
    this.hoitavNumber = hoitavNumber;
  }
}

Antud näites on piiratud tüübiparameeter N ainult klassi java.lang.Number alamklassideks. Kompilaator lubab kasutada NumbriHoidja<Integer>, aga mitte NumbriHoidja<String>. Piiride määramine on kasulik selle pärast, et nüüd on võimalik NumbriHoidja klassis N tüüpi muutujate peal kutsuda ka Number klassi meetodeid (kompilaator tagab, et N on alati mingi Number). Parameetri piiriks saab kasutada nii liideseid kui ka klasse, mõlema puhul kasutatakse võtmesõna extends (imelik, aga nii see on).

Geneerilised meetodid

Mõnikord ei ole vaja tervele klassile tüübiparameetreid lisada. Geneeriliseks saab teha ka üksiku meetodi. Selle jaoks tuleb lihtsalt enne tagastustüüpi tüübiparameeter deklareerida:

public static <T> List<T> reverse(List<T> list) {
  List<T> tulemus = new ArrayList<T>();
  for (int i = list.size()-1; i >= 0; i--) {
    tulemus.add(list.get(i));
  }
  return tulemus;
}

Enesekontroll