Kokoelmat

Kokoelma

Kokoelma(tai säiliö) on olio, joka ryhmittää useampia alkioita yhteen pakettiin. Kokoelmia käytetään tiedon tallennukseen, saantiin ja muuttamiseen. Kokoelmat muodostavat luonnollisen kaltaisia ryhmiä, kuten pokerikäsi (korttien kokoelma), kirjekansio (kirjeiden kokoelma) tai puhelinluettelo (nimi-puhelinnumero kuvausten kokoelma). Mm. Seuraavia etuja saadaan kokoelmien käytöstä (Sunin sivut):

Kokoelmakehys

Kokoelmakehys on kokoelmien esittämiseen ja muuttamiseen tarkoitettu yhtenäinen arkkitehtuuri joka mahdollistaa muokkaamisen riippumatta joukon olioiden toteutuksesta. Kokoelmakehys on määritelty joukkona rajapintoja ja siihen liitettyjä sopimuksia. Kehys tarjoaa myös abstrakteja toteutuksia, joista voi luoda omia tietorakennerajapintoja sekä konkreettisia toteutuksia rajapinnoista.

Kaikki kokoelmakehykset sisältävät seuraavat kolme asiaa:
Rajapinnat: Abstraktit tietotyypit kokoelmien esittämiseen. Rajapinnat luovat edellytyksen muokata kokoelmia riippumatta niiden toteutuksesta. OOP-kielissä, kuten Java, nämä rajapinnat yleisesti muodostavat hierarkian.
Toteutukset: Konkreettiset kokoelmarajapintojen toteutukset. Nämä ovat uudelleenkäytettävät tietorakenteet.
Algoritmit: Metodit jotka suorittavat hyödylliset laskennat, kuten etsinnän tai lajittelun olioille jotka toteuttavat kokoelmarajapinnan. Näitä algoritmeja sanotaan polymorphisiksi, koska samaa metodia voidaan käyttää tarkoituksenmukaisen kokoelmarajapinnan useassa eri toteutuksessa. Algoritmit ovat uudelleenkäytettävää toiminnallisuutta.

Kokoelmakehyksen sisältö (Sunin sivut): Java 5:n uudistukset Collections-kehykseen

Rajapinnat

Rajapintojen perustarkoitus kokoelmakehyksessä on on mahdollistaa kokoelmien muuttaminen riippumatta siitä, mikä on kokoelman alkioiden toteutus. Perusrajapintana toimii Collection. Collection-rajapinnasta periytyvät viisi muuta rajapintaa: Set, List, SortedSet, Queue ja BlockingQueue. Lisäksi on olemassa kolme rajapintaa, jotka eivät periydy Collection rajapinnasta: Map, SortedMap ja ConcurrentMap. Nämä rajapinnat esittävät enemmänkin kuvauksia, kuin todellisia kokoelmia. Niistä löytyy kuitenkin samankaltaisia operaatioita kuin kokoelmien rajapinnoista, joten niitä voidaan muuntaa samalla tavoin.

Rajapintoja hyödyntämällä on erotettu tietorakenteiden toteutus omaksi kokonaisuudekseen ja toisaalta niiden avulla voidaan tarjota ohjelmoijalle yksi rajapinta useisiin eri tietorakenteiden toteutuksiin. Esimerkiksi List-rajapinnan toteuttavat luokat LinkedList ja ArrayList; Map-rajapinnan HashMap, IdentityHashMap ja LinkedHashMap-luokat. Set-rajapinnan taas toteuttavat HashSet ja LinkedHashSet sekä SortedSet-rajapinnan TreeSet.

Kaikki kokoelmien rajapintojen muokkausmetodit on merkitty valinnaisiksi. Jotkut toteutukset eivät voi suorittaa yhtä tai useampaa näistä operaatiosta, heittäen UnsupportedOperationException -poikkeuksen, jos näitä näitä operaatioita yritetään suorittaa. Toteutusten dokumentonnissa onkin mainittava niistä operaatioista joita ne tukevat. Muutamia termejä on esitetty helpottamaan tässä määrittelyssä:

unmodifiable: Kokoelmat jotka eivät tue muuttamisoperaatioita.
modifiable: Kokoelmat joita voi muuttaa.
immutable: Collection-olion muutos ei ole näkyvä.
mutable: Collection-olion muutos on näkyvä.
fixed-size: Listat joiden koko pysyy vakiona huolimatta listan sisällöstä.
variable-size: Listat joiden koko ei pysy vakiona.
random access (lists): Listat joiden alkioiden viittaaminen onnistuu indeksillä.
sequential access (lists): Listat joiden alkioihin ei ole indeksiviittausta.

Jotkut toteutukset voivat rajata sitä millaisia alkioita voidaan kokoelmaan tallettaa. Esim. ne voivat olla vain tiettyä tyyppiä tai eivät saa olla tyhjiä (null) viittauksia.

Set

Joukko on kokoelma joka ei voi sisältää duplikaatteja alkiosta. Rajapinta mallintaakin matemaattista joukkoa. Sitä käytetään esittämään mm. pokerikättä tai koneen suorittamia prosesseja.

List

Lista on järjestetty kokoelma (joskus kutsutaan myös jonoksi). Toisin kuin joukot, listat voivat sisältää duplikaatteja alkioista. Listan käyttäjällä on yleensä tarkka hallinta siitä, minne kukin alkio on sijoitettu. Käyttäjä voi hakea alkiota indeksin avulla.

SortedSet

Joukko joka ylläpitää alkioitaan nousevassa järjestyksessä. Joitain lisäoperaatioita on lisätty, että saataisiin hyöty järjestyksestä. Rajapintaa käytetään mm. sanalistoihin.

Queue

Jono on erikoistapaus listasta, jossa lisäykset voidaan tehdä vain jonon perään ja poistot (ja haut) jonon päästä.

BlockingQueue

Jono joka tukee operaatioita, jotka alkiota haettaessa odottavat että jono ei ole tyhjä ja alkiota lisättäessä odottavat että lisätilaa vapautuu jonoon.

Map

Olio jossa jokaista arvoa vastaa jokin avain. Jokainen avain voi kuvautua vain täsmälleen yhdelle arvolle.

SortedMap

Kuvaus joka ylläpitää kuvauksia nousevassa järjestyksessä (vrt. Set - SortedSet). Käytetään mm. sanakirjoissa tai puhelinluetteloissa.

Kokoelmien toteutukset

Luokat jotka toteuttavat jonkin kokoelmarajapinnan ovat yleensä muotoa <Toteutuksen tyyli><rajapinta>. Yleiskäyttöiset toteutukset tukevat kaikkia valinnaisia kokoelmarajapinnan operaatioita ja niiden alkioissa ei ole mitään rajoituksia. Nämä luokat ovat synkronoimattomia, mutta Collections-luokka sisältää synchronization wrappers-tehtaita, joita voidaan käyttää lisäämään kokoelmaan synkronointi. Kaikista uusista toteutuksista löytyy fail-fast iteraattorit, jotka havaitsevat luvattoman rinnakkaisen muuntamisen.

AbstractCollection, AbstractSet, AbstractList, AbstractSequentialLista ja AbstractMap -luokat muodostavat perustoteutukset tärkeimmistä kokoelmarajapinnoista.

Rajapinnoista Set, Map, List esitellään seuraavat yleiskäyttöiset toteutukset:

HashSet

Toteuttaa Set rajapinnan, lisänä siinä on hajautustaulu (HashMap instanssi). Ei takaa joukon järjestystä iteroidessa tai yleisesti. Perusoperaatiot (add, remove, contains ja size) ovat vakioaikaisia sillä oletuksella, että hajautusfunktio toimii oikein. Iterointi yli joukon vaatii ajan joka on suoraan verrannollinen HashSetin alkioiden määrään + hajautuksen sankkojen määrä.

HashMap

Hajautustaulun toteutus joka perustuu Map-rajapintaan. Toteuttaa kaikki valinnaiset map operaatiot ja sallii null-arvot ja null-avaimet. Ei anna takuita järjestyksestä. Perusoperaatiot (put ja get) toimivat vakioaikaisesti jos hajautusfunktio toimii oikein. Iterointi yli hajautustaulun vie ajan joka on verrannollinen alkioiden + sankkojen määrään. HashMap instanssilla on kaksi parametria, jotka vaikuttavat sen tehokkuuteen: kapasiteetti (initial capasity) ja kuormituskerroin (load factor). Kapasiteetti kertoo sankkojen määrän alussa ja kuormituskerroin sen miten täyteen taulu saa täyttyä, ennenkuin sen kokoa aletaan kasvattamaan. Taulun saavuttaessa kuormituskertoimen ja alkioiden tulon, taulun koko kasvaa suunnilleen kaksinkertaiseksi.

ArrayList

Toteutus List-rajapinnasta, jossa koko taulukon kokoa voidaan vaihtaa. Toteuttaa kaikki valinnaiset listaoperaatiot ja sallii kaikki alkiot, mukaanlukien null. Vastaa periaatteessa Vector-luokkaa, mutta on synkronoimaton. size, isEmpty, get, set, iterator ja listIterator -operaatiot ovat vakioaikaisia. add toimii ajassa O(n). Jokaisella ArrayList-instanssilla on kapasiteetti, joka määräytyy listan koon mukaan.

TreeSet

Toteuttaa Set rajapinnan ja sisältää TreeMap-instanssin. Takaa, että järjestetyn joukon alkiot ovat nousevassa järjestyksessä. Perusoperaatiot (add, remove ja contains) ovat aikavaativuusluokkaa log(n).

TreeMap

Punamusta-puihin perustuva toteutus SortedMap-rajapinnasta. Takaa, että kuvaus on nousevassa järjestyksessä. Perusoperaatiot (containsKey, get, put ja remove) ovat aikavaativuusluokkaa log(n).

LinkedList

Linkitetyn listan toteutus List-rajapinnasta. Toteuttaa kaikki valinnaiset listaoperaatiot ja sallii kaikki alkiot, mukaanlukien null. Luokka sisältää get, remove ja insert operaatiot alkioille listan alkuun ja loppuun, minkä avulla voidaan linkitetystä listasta toteuttaa jono ja pino. LinkedList toteuttaakin Queue-rajapinnan. Listan operaatiot toteuttavat aikavaativuuden, jota voidaan odottaa kahteen suuntaan linkitetyltä listalta.

LinkedHashSet

Hajautustaulun ja linkitetyn listan toteutus Set-rajapinnasta, odotuksenmukaisella iterointijärjestyksellä. Eroaa HashSet-luokan toteutuksesta siinä, että linkitetty lista määrää iterointijärjestyksen - järjestyksessä joka on sen mukaan kun alkioita on lisätty joukkoon. Sisältää valinnaiset operaatiot ja hyväksyy myäs null-alkiot. Linkitetyllä hajautusjoukolla on kaksi sen suoritustehoon vaikuttavaa parametria: kapasiteetti ja kuormituskerroin, jotka on määritelty kuten HashSet-luokassa.

LinkedHashMap

Hajautustaulun ja linkitetyn listan toteutus Map-rajapinnasta. Iterointi samalla tavoin kuin LinkedHashSet-luokassa.

Esimerkkejä kokoelmien käytöstä

Esimerkki TreeSet- ja HashSet-luokkien käytöstä. Luodaan kaksi TreeSet-tyyppistä joukkoa nimistä ja muodostetaan niiden yhdiste, leikkaus ja erotus HashSet-luokan avulla. 

import java.util.*;

public class Union {

	private static String[] nimet1 = {"Tero", "Miina", "Erkki", "Pentti", "Anni", "Sanna", "Laura", "Eero", "Sami", "Kalle"};
	private static String[] nimet2 = {"Tero", "Miina", "Ville", "Vesa", "Anni", "Risto", "Laura", "Eero", "Sami", "Jari"};

	public static void main(String[] args) {

		Set s1 = new TreeSet();
		Set s2 = new TreeSet();

		for (int i = 0; i < 10; i++) {
			s1.add(nimet1[i]);
			s2.add(nimet2[i]);
		}
		System.out.println();
		System.out.println("Molempien Set:ien sisällöt:");
		System.out.println(s1);
		System.out.println(s2);

		Set union = new HashSet(s1);
		union.addAll(s2);

		System.out.println();
		System.out.println("s1 ja s2 union:");
		System.out.println(union);

		Set intersection = new HashSet(s1);
		intersection.retainAll(s2);

		System.out.println();
		System.out.println("s1 ja s2 intersection:");
		System.out.println(intersection);

		Set difference = new HashSet(s1);
		difference.removeAll(s2);

		System.out.println();
		System.out.println("s1 ja s2 difference:");
		System.out.println(difference);
	}


}

Esimerkki algoritmien käytöstä. Luodaan luokka Apple, joka toteuttaa Comparable-rajapinnan. Omenoiden keskenäinen vertailu tapahtuu niiden painojen mukaan. 

public class Apple implements Comparable {
  int weight = 0;
  String countryOfOrigin = null;

  public Apple(String countryOfOrigin,int weight) {
    this.weight = weight;
    this.countryOfOrigin = countryOfOrigin;
  }

  public int compareTo(Object a) {
    Apple anotherApple = (Apple)a;
    if (anotherApple.weight > this.weight)
      return -1;
    else if (anotherApple.weight == this.weight)
      return 0;
    else
      return 1;
  }

  public int getWeight() {
    return weight;
  }

  public String getCountryOfOrigin() {
    return countryOfOrigin;
  }

  public String toString() {
    String s = "Country of origin: " + countryOfOrigin
      + ".   Weigth: " + weight;
    return s;
  }
}
Koska Apple-luokka toteuttaa Comparable-rajapinnan, voidaan omenoiden taulukkoon käyttää Arrays-luokan sort-metodia, joka järjestää taulukon alkiot nousevaan järjestykseen. 
    Apple[] apples = new Apple[5];

    apples[0] = new Apple("Finland",20);
    apples[1] = new Apple("Sweden",1);
    .
    .

    java.util.Arrays.sort(apples);
Esimerkkiohjelman koko lähdekoodi: SortApples.java

Esimerkki iteraattoreiden käytöstä erilaisille kokoelmille. 

import java.util.*;

class IteratorTest {

  public static void main(String[] args) {
    IteratorTest it = new IteratorTest();
    //it.linkedListTest();
    //it.TreeSetTest();
    //it.HashMapTest();
    it.HashSetTest();
  }

  public void linkedListTest() {
    List myList = new LinkedList();
    myList.add("value1");
    myList.add("value2");

    ListIterator myIterator = myList.listIterator();

    while (myIterator.hasNext()) {
      System.out.println(myIterator.next());
    }
  }

  public void TreeSetTest() {
    SortedSet mySet = new TreeSet();
    mySet.add(new MyItem(3));
    mySet.add(new MyItem(1));
    mySet.add(new MyItem(2));
    mySet.add(new MyItem(4));
    mySet.add(new MyItem(5));

    Iterator myIterator = mySet.iterator();

    while (myIterator.hasNext()) {
      System.out.println(myIterator.next());
    }

  }

  public void HashMapTest() {
    Map myHash = new HashMap();
    myHash.put("First",new MyItem(1));

    Set entries = myHash.entrySet();
    Iterator myIterator = entries.iterator();
    while (myIterator.hasNext()) {
      Map.Entry entry = (Map.Entry)myIterator.next();
      String key = (String)entry.getKey();
      MyItem value = (MyItem)entry.getValue();
      System.out.println("key=" + key + ", value=" + value);
    }

  }

  public void HashSetTest() {
    Set set = new HashSet();
    set.add ("eka");
    set.add ("toka");

    Iterator myIterator = set.iterator();

    while (myIterator.hasNext()) {
      System.out.println(myIterator.next());
    }
  }
}

class MyItem implements Comparable {

   public MyItem(int value) {
     this.value=value;
   }

   public String toString() {
      return "value of this item: "+value;
   }

   public boolean equals(Object other) {
      if (getClass() == other.getClass()) {
	MyItem otherItem = (MyItem)other;
	return value == otherItem.value;
      }
      else
	 return false;
   }

   public int compareTo(Object other) {
      MyItem otherItem = (MyItem)other;
      return value - otherItem.value;
   }

   private int value;
}

Esimerkki HashMap-luokan käytöstä. Toteutetaan tietokilpailu sijoittamalla kysymys ja vastaus pareittain HashMap -instanssiin. 

import java.util.*;

public class Kilpailu {

	private Map kysvas = new HashMap();
	private String kysymys;
	private String vastaus;
	private int laskuriOikein = 0;
	private int laskuriVaarin = 0;
	private Scanner sc = new Scanner(System.in).useDelimiter(System.getProperty("line.separator"));

	public Kilpailu(String[] kv) {
		for(int i = 0; i < kv.length; i = i+2) {
			kysvas.put(kv[i], kv[i+1]);
		}
	}

	public void kysele() {

		for (Iterator i = kysvas.entrySet().iterator(); i.hasNext();) {
			Map.Entry e = (Map.Entry) i.next();
			System.out.print(e.getKey() + ": ");
			this.vastaus = null;
			this.vastaus = sc.next();

			if (this.vastaus.equals((String) e.getValue())) {
				System.out.println("Oikein");
				laskuriOikein++;
			}
			else {
				System.out.println("Väärin");
				laskuriVaarin++;
			}
		}
	}
	public void tulokset() {
		System.out.println("Vastasit oikein "+laskuriOikein+" kysymykseen. Vastauksista "+laskuriVaarin+" oli väärin.");
	}
}
Luokkaa käyttävän pääohjelman toteutus: Tietokilpailu.java.