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 automaattisten (un)boxing-muunnosten ansiosta primitiivityyppisiäkin muuttujia voi toki käyttää vaivattomasti säiliöluokkien 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 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 kulmasulkeissa 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ää alkionitem
taulukon perään (ja taulukon koko kasvaa yhdellä).addAll(container)
: lisää säiliöncontainer
sisältämät alkiot taulukon perään (aivan kuin ne lisättäisiin yksitellenadd
-funktiolla).get(i)
: palauttaa indeksini
alkion.set(i, item)
: asettaa alkionitem
olemassaolevan indeksini
kohdalle.
Seuraava esimerkkikoodinpätkä luo 10 ensimmäistä Fibonaccin lukua sisältävän
ArrayList
-taulukon.
// Huomaa, että oikealla puolella new-operaattorin yhteydessä kulmasulut 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ää alkionitem
joukkoon, ellei joukossa jo ole samanlaista alkiota.addAll(container)
: lisää säiliöncontainer
sisältämät alkiot joukkoon (aivan kuin ne lisättäisiin yksitellenadd
-funktiolla; joukon alkioiden kanssa samanlaisia ei lisätä).contains(item)
: palauttaa totuusarvon joka kertoo, onko joukossa alkiotaitem
.remove(item)
: poistaa alkionitem
, 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 funktioita 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 kulmasuluissa pilkulla eroteltuna erikseen
sekä avaimen että alkion tyyppi. 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 vastaavat 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-alkioparinkey
-item
, eli arvonitem
avaimellekey
, tähän sanakirjaan. Jos avaimella oli aiemmin jo alkio, se korvautuu nyt lisätyllä alkiolla.putAll(map)
: lisää sanakirjanmap
kaikki avain-alkioparit tähän sanakirjaan (aivan kuin ne lisättäisiin yksitellen funktiollaput
).containsKey(key)
: palauttaa totuusarvon, joka kertoo, onko avaimellakey
talletettu alkiota.containsValue(item)
: palauttaa totuusarvon, joka kertoo, onko talletettu alkiotaitem
. Huom: tämä voi olla hidas operaatio, koska se perustunee avain-alkio parien läpikäyntiin.get(key)
: palauttaa avaimenkey
alkion (tainull
, jos sanakirja ei sisällä kyseistä avainta).remove(key)
: poistaa avaimenkey
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
jaV
ovat avaimen ja alkion tyypit. Tämä on varsin samankaltainen kuin C++-kielenpair
.Avain-alkio-parista saa luettua avaimen ja alkion jäsenfunktioilla
getKey()
jagetValue()
.
TreeMap
tarjoaa lisäksi alkioiden järjestykseen liittyen mm. seuraavat jäsenfunktiot:
first()
: palauttaa joukon pienimmällä avaimella talletetun alkion.last()
: palauttaa joukon suurimmalla avaimella talletetun alkion.pollFirst()
: palauttaa ja poistaa joukon pienimmällä avaimella talletetun alkion.pollLast()
: palauttaa ja poistaa joukon suurimmalla avaimella talletetun 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).
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 luokallesi 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 apufunktiolla 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 perustyypit tukevat valmiiksi tavanomaista kasvavaan suuruusjärjestykseen pohjautuvaa vertailua.