Kolekce

Pole jsou známa od počátku programovacích jazyků. Mezi hlavní výhody patří rychlý přístup k prvkům pole pomocí indexu. Operaci výběru lze provést v konstantním čase. Dále je to typová jednota a v Javě též možnost uchovávat prvky primitivních datových typů.

Nevýhodou klasických polí je hlavně nemožnost změny velikosti a absence podpůrných metod, například pro vyhledávání prvků podle hodnoty.

Rozšíření práce s poli, v balíku java.util - poskytuje následující metody:

public static List asList(); // prevede pole na kolekci typu List, vhodna napr. pro vypisy
public static boolean equals(); // porovnani poli
public static void fill(); // naplneni pole konst. hodnotou
public static void sort(); // setrideni pole
public static binarySearch(); // binarni vyhledavani v setridenem poli metodou sort()

Metody jsou přetíženy pro základní datové typy a pro typ Object (viz dokumentace).

Pro použití metody Arrays.equals() pro strukturované datové typy je nutné zastínit metodu equals(), kterou dědí všechny objekty ze třídy Object. Přitom je nutné dodržet podmínky: reflexivita, symetrie, tranzitivita (jedná se o relaci ekvivalence) a dále konzistenci a nerovnost s null. Též je třeba zastínit metodu hashCode() zděděnou od Object, protože pokud equals() vrací true pro dva objekty, pak by jejich hashCode() měl být stejný. Podrobněji viz přednášky či Herout: Bohatství knihoven, str. 159, 162.

Slouží pro implementaci přirozeného řazení - objekt má jediné kritérium, podle kterého se řadí - metodou Arrays.sort(). Pro všechy základní datové typy je tato metoda přetížena, pro objektové datové typy ji musíme napsat (viz příklad).

  balík:
    java.lang
  metody:
    public int compareTo(Object o)

Očekává se, že metoda compareTo(Object o) bude vracet:

Pozor na nutnost přetypování formálního parametru o na potřebný datový typ!

Slouží k implementaci absolutního řazení nebo řazení v případech, kdy nelze jednoduše implementovat rozhraní Comparable (např. hotová třída, do které nemůžeme zasahovat, nebo jde o objekty, které chceme řadit podle různých kritérií. Např. Studenty budeme jednou řadit podle data narození, jindy podle jména a jindy podle studijního průměru). Opět se využívá přetížených metod třídy Arrays - všechny přijímají jako poslední parametr objekt implementující rozhraní java.util.Comparator.

  balik:
    java.util
  metody:
    int compare(Object o1, Object o2)

Rozhraní poskytující metody pro práci s prvky kolekcí. Je základem rozhraní List a Set. Mezi nejdůležitější metody patří následující.

// VLASTNOSTI
boolean isEmpty() // pravda, kdyz je kolekce prazdna
int size() // pocet prvku v kolekci
 
// VKLADANI, RUSENI PRVKU
boolean add(Object o) // vlozeni prvku do kolekce
boolean add(Collection c) // vlozeni vsech prvku z kolekce c
 
void clear() // kompletni vymazani kolekce
boolean remove(Object o) // odstraneni prvku o (pokud je v kolekci vicekrat, odstrani se nahodne jeden)
boolean remove(Collection c) // odstraneni prvku, ktere jsou zaroven v kolekci c
boolean retainAll(Collection c) // odstraneni prvku, ktere nejsou zaroven v kolekci c
 
// TESTY NA PRVKY
boolean contains(Object o) // pravda, kdyz o je prvkem
boolean contains(Collection c) // pravda, kdyz vsechny prvky c jsou prvkem
 
// ZISKANI ITERATORU
Iterator iterator()
 
// PREVOD KOLEKCE NA POLE
Object[] toArray() // prevod na pole Objectu
Object[] toArray(Object[] a) // prevod na pole konkretniho typu

Přidává metody usnadňující práci se seznamy, hlavně možnost indexace! Seznamy umožňují uložit tentýž prvek (metoda equals()) vícekrát.

void add(int index, Object o) // pridani prvku na index, ostatni prvky budou posunuty
Object get(int index) // vraci prvek ulozeny na index
Object set(int index, Object o) // zmena prvku na index, vraci ulozeny prvek
Object remove(int index) // odstraneni prvku na index, posun indexu, vraci ulozeny prvek
 
int indexOf(Object o) // vraci index prvniho nalezeneho prvku shodneho s o (equals())
int lastIndexOf(Object o) // vraci index posledniho nalezeneho prvku shodneho s o (equals())
List subList(int start, int end) // podseznam od start do end - 1 

Podpora pro implementaci množin. Množiny neumožňují uložit tentýž prvek (metoda equals()) vícekrát. Rozhraní nepřináší žádné podstatné metody navíc k metodám rodičovského rozhraní Collection.

Nejoblíbenější implementace seznamu (= rozhraní List).

Rozdíl kapacita x velikost (int size()). Zajištění kapacity - konstruktorem ArrayList(int vychoziKapacita), kde parametrem je výchozí kapacita nebo metodou boolean ensureCapacity(int capacity). Předpokládejme, že máme ArrayList plný, tedy velikost je rovna kapacitě. Pokud přidáme další prvek dojde k vytvoření nového vnitřního pole o velikosti 1,5 násobku původní velikosti a překopírování hodnot do nového pole. Toto zaručí, že vložení jednoho prvku je v průměrném případě lineární.

V Javě 1.5 a výše se využívá tzv. generics (šablony), kolekce mezi ně patří - datový typ, který se bude ukládat do kolekce musí být znám při překladu, jinak bude zobrazeno varování. Pokud typem bude Object nebo použijeme zástupný symbol ?, lze samozřejmě do kolekce uložit cokoliv. Více na http://java.sun.com/developer/technicalArticles/J2SE/generics/.

Tato třída implementuje rozhraní List pomocí obousměrně zřetězeného seznamu. Vhodná, pokud

• provádíme časté změny v seznamu,
• potřebujeme pracovat se začátkem a koncem seznamu.

Naopak nevhodná je tato třída pro přímý (indexovaný) přístup k prvkům seznamu, protože indexovaný přístup je lineární vzhledem k velikosti indexu nikoli konstantní jako je tomu u ArrayListu.

Implementuje rozhraní Collection a List a dále nabízí metody pro práci s prvním a posledním prvkem seznamu.

  // vlozeni prvku na zacatek/konec seznamu
  void addFirst(Object prvek)
  void addLast(Object prvek)
 
  // odebrani prvku ze zacatku/konce seznamu - vraci odebirany objekt
  Object removeFirst()
  Object removeLast()
 
  // vraceni prvku ze zacatku/konce seznamu
  Object getFirst()
  Object getLast()

Obdoba třídy Arrays. Poskytuje tytéž metody pro kolekce a další (min, max atp.) navíc. Je z balíku java.util. Metody jsou statické, veřejně přístupné. Existují vždy ve variantě bez objektu /s objektem Comparator pro přirozené / absolutní řazení. Běžně používané metody následují.

// naplneni kolekce hodnotou
void fill(Collection c, Object o) // naplneni kolekce stejnou hodnotou
 
// setrideni kolekce
void sort(Collection c) 
void sort(Collection c, Comparator cmp) 
 
// binarni vyhledavani v setridene kolekci metodou sort()
binarySearch(List list, Object key) 
binarySearch(List list, Object key, Comparator cmp) 
 
// nejvetsi / nejmensi prvek
Object max(Collection c)
Object max(Collection c, Comparator cmp)
Object min(Collection c)
Object min(Collection c, Comparator cmp)
 
// zamichani kolekce
void suffle(Collection c)
void suffle(Collection c, Random rnd)
 
// hledani podseznamu, -1 znamena nenalezeno
int indexOfSubList(List list, List subList)
int lastIndexOfSubList(List list, List subList)

Iterátor zajišťuje přístup k prvkům ve všech kolekcích (vč. Map). Jedná se o postupný průchod kolekcí. Iterátory jsou vždy na jedno použití! Nový iterátor vždy ukazuje před první prvek!

  // deklarace kolekce a naplneni
  Collection c = new ArrayList<Integer>(10);
  Collections.fill(c, new Integer(1));
 
  // ziskani iteraoru a pruchod koleci s odstranovanim prvku
  for (Iterator it = c.iterator(); it.hasNext(); ) {
    it.next();
    it.remove()
  }

Pozor na metodu remove():

• nesmí být volána dříve než metoda next(), jinak je vyhozena výjimka IllegalStateException - metoda remove() maže právě vrácený prvek,
• nevrací referenci na mazaný objekt, jako metoda remove() z rozhraní Collection.

Stejně tak je třeba testovat, zda v kolekci existuje ještě další prvek metodou hasNext(), pokud by neexistoval a přesto jsme zavolali next(), bude vyhozena výjimka NoSuchElementException.

Pro kolekce implementující List existuje ListIterator, který umožňuje obousměrný průchod kolekcí.

Implementují rozhraní Set. Prvek se v množině může vyskytovat pouze jednou, při opětovném pokusu o přidání vrátí metoda boolean add(Object prvek) false. Narozdíl od seznamů nelze s množinami pracovat pomocí indexů. Pro průchody je třeba využívat iterátory.

Implementuje rozhraní Set, které nepřidává žádné podstatné metody oproti Collection.

Toto rozhraní a tato třída udržuje prvky v kolekci seřazeny (TreeSet - ve stromové struktuře). Pro řazení se využívá buď přirozeného řazení metodou compareTo, tj. prvky musí implementovat rozhraní Comparable nebo je třeba vytvořit objekto komparátoru, který se předá kolekci jako poslední parametr konstruktoru.

Rozhraní SortedSet navíc přidává následující metody.

// prvni, posledni prvek
Object first()
Object last()
 
// podmnoziny (dolniHranice je vzdy zahrnuta, horniHranice neni nikdy zahrnuta!)
SortedSet headSet(Object horniHranice)
SortedSet tailSet(Object dolniHranice)
SortedSet subSet(Object dolniHranice, Object horniHranice)

Množinu i podmnožiny lze modifikovat bez vyhození výjimky (narozdíl od seznamů, kde modifikace původního seznamu a následná práce s podseznamem vede k vyhození výjimky). U seřazené množiny není možné přidat prvek menší(větší) než nejmenší(největší) prvek v podmnožině - kvůli správnému zařazení do nadmnožiny - vede na výjimku IllegalArgumentException.

Jiným názvem slovníky (dictionary), umožňují ukládat dvojice klíč-hodnota. Implementují rozhraní Map a POZOR neimplementují rozhraní Collection, tj. nejsou s kolekcemi zaměnitelné!

Mapy jsou v Javě 1.5 a výše implementovány stejně jako ostatní kolekce pomocí generics a je třeba na to nezapomenout!

Základní rozhraní, poskytuje nejběžnější metody.

// VLASTNOSTI
boolean isEmpty() // pravda, kdyz je mapa prazdna
int size() // pocet prvku v mape
 
// VKLADANI, RUSENI PRVKU
Object put(Object klic, Object hodnota) // vlozeni prvku do mapy
void putAll(Map m) // vlozeni vsech prvku z mapy m
 
void clear() // kompletni vymazani kolekce
Object remove(Object klic) // odstraneni prvku s danym klicem
 
// TESTY NA PRVKY
boolean containsKey(Object key) // pravda, kdyz klic je klicem
boolean containsValue(Object hodnota) // pravda, kdyz vsechny mapa obsahuje hodnotu
 
// ZISKANI PRVKU
Object get(Object klic) // vrati hodnotu odpovidajici klici
 
// PREVOD MAPY NA KOLEKCI
Set keySet() // mnozina klicu
Set entrySet() // mnozina dvojic klic-hodnota
Collection values() // kolekce hodnot (moznost opakovani!)

Metody převádějící mapu na jinou kolekci vždy vytvářejí pohled - mělkou kopii! Zvláštností při práci s pohledy (kolekcemi vycházejícími z rozhraní Collection) je, že použití metod jako removeAll(), retainAll atp. z rozhraní Collection projeví i v mapě.

U klíčů se očekává se vhodná implementace metod equals() a hashCode(). V případě použití metody containsValue() je tytéž metody nutné implementovat i pro hodnoty.

Nelze získat iterátor pro průchod mapou! Je několik možností jak to obejít - iterátor pro množinu klíčů, hodnot nebo lépe iterátor pro množinu dvojic klíč-hodnota. Dvojice klíč-hodnota je reprezentována instancí rozhraní Map.Entry, které poskytuje následující metody.

Object getKey() // vrati klic
Object getValue() // vrati hodnotu
 
Object setValue(Object novaHodnota) // nastavi novou hodnotu (modifikace mapy) a vrati starou hodnotu

Opět se jedná o práci s pohledem, platí vše co bylo o pohledech řečeno.

Konkrétní implementace rozhraní Map, rychlost mapy záleží na kvalitě metody hashCode() prvku.

Obdoba SortedSet a TreeSet. Seřazená mapa, umožňuje vytvářet pohledy v intervalu klíčů, pracovat s nejnižšším/nejvyšším prvkem.

Porovnávání v třídě TreeMap může být přirozené, pak prvky musí implementovat rozhraní Comparable nebo lze využít komparátoru, který se předá konstruktoru mapy TreeMap(Comparator cmp).

Object firstKey() // vrati hodnotu patrici k prvnimu klici
Object lastKey() // vrati hodnotu patrici k poslednimu klici
 
SortedMap headMap(Object klicHorniHranice) // pohled na mapu od zacatku az do klicHorniHranice, vyjma klicHorniHranice
SortedMap tailMap(Object klicDolniHranice) // pohled na mapu od klicDolniHranice vcetne az do konce mapy
SortedMap tailMap(Object klicDolniHranice, Object klicHorniHranice) // spojeni predchozcich

1. Vhodná implementace metody hashCode(). V Javě se typicky používá zřetězení pro kolekce založené na hashích tak, aby nedocházelo k jevu clusterování (většina prvků spadne do několika málo bucketů, většina je volné, řetězy jsou dlouhé - lineárni časová složitost vzhledem k velikosti kolekce). Teorie hashovacích funkcí a jejich návrh je ale samozřejmě mimo rámec tohoto předmětu. Jako základní doporučení lze využít Herout: Bohatství knihoven str. 166.
2. Implementace metody equals() tak aby se jednalo o ekvivalenci a navíc byla konzistentní a žádná instance se nerovnala null.

Shrnutí: Třída vhodná pro uložení do kolekce by měla mít neměnné instance, změna se realizuje náhradou novou instancí, měla by mít překryté metody equals() a hashCode a také toString(), která bude vracet smysluplné informace o instanci. Též by měla implementovat rozhraní Comparable pro přirozené řazení. Nakonec bychom si měli dát pozor na možnost výskytu výjimek třídy RuntimeException a potomků - na takové výjimky nás neupozorní kompilátor!