ARCHIV

Java (11) - Kontejnery II.

Po minulém obecném úvodu do světa kolekcí se podíváme na jednotlivá rozhraní a implementace. Správný výběr je důležitý pro tvorbu rychlých a úsporných programů.

6.4.2005 15:00 | Lukáš Jelínek | Články autora | přečteno 79079×

Kategorie kontejnerových rozhraní

Jak jsem říkal už minule, namísto práce s implementačními objekty je vhodné při práci používat rozhraní. Systém kolekcí je na rozhraní založen, existuje jich zde celá hierarchie a my můžeme pracovat na té úrovni, která nám nejlépe vyhovuje (resp. na té nejvyšší použitelné).

Máme dvě základní množiny kontejnerů, každá z nich vychází z jednoho rozhraní. První z nich jsou běžné (normální) kolekce odvozené od rozhraní Collection, do druhé kategorie patří kolekce asociativní ("mapované", obsahující dvojice klíč-hodnota) implementující rozhraní Map.

Normální kolekce

Typickým znakem "normálních" kolekcí je to, že pracujeme s jednoduchými prvky (prvek je jeden objekt). Vnitřní implementace kontejneru může být jakákoli a liší se podle toho, k čemu je tento kontejner určen.

V rámci CF rozeznáváme dvě skupiny těchto kolekcí - množiny a seznamy (sekvence). Podívejme se na ně blíže:

• Množiny (rozhraní Set) - každý prvek může být v kontejneru pouze jednou. Není zde obdoba kontejneru multiset (s možností vícenásobné přítomnosti téhož prvku) známého z STL v C++. Prvek obecně nemá určenu žádnou polohu v množině, na základě které by k němu bylo možné přistupovat. Zvláštním případem je podrozhraní SortedSet, což je seřazená množina.
• Seznamy (rozhraní List) - prvek může být v kontejneru vícekrát a má určenu jednoznačnou polohu (index).

Asociativní kolekce

Často jsme v situaci, kdy potřebujeme k datům přistupovat ne podle číselného indexu, ale podle nějakého obecného klíče. Asociativní kolekce obsahují prvky jakožto dvojice klíč-hodnota, kdy každý člen této dvojice může být libovolného referenčního typu.

Obdobně jako u množin, ani zde nemáme něco jako multimap z STL. Ke každému klíči může příslušet nejvýše jedna hodnota. Další shodná vlastnost s rozhraním Set je existence seřazené varianty - je to rozhraní SortedMap.

Obecné implementační třídy

Nyní přichází čas na bližší seznámení s různými implementací kolekcí. Každá se hodí pro určitý způsob použití.

HashSet - množina s hešovací tabulkou

Třída HashSet používá pro ukládání dat hešovací tabulku. Práce je velice rychlá (většina operací probíhá v konstatním čase), nezaručuje ale pořadí prvků. Prázdné reference jsou povoleny.

HashSet můžeme použít prakticky vždy, kdy nepotřebujeme pracovat s prvky v konkrétním pořadí (tj. ve většině případů).

Pro optimální výkon je důležité správně zvolit výchozí kapacitu kontejneru - příliš velká způsobuje zbytečnou alokaci paměti a navíc i pomalejší sekvenční přístup (přes iterátor). Proto je dobré před použitím promyslet, kolik prvků se zde bude obvykle vyskytovat a podle toho kontejner nadimenzovat (výchozí kapacita je 101 prvků).

Set s = new HashSet();    // vytvoření nové množiny
s.add(new Integer(15));   // vložíme postupně 3 prvky
s.add(new Integer(-2));
s.add(new Integer(123));
s.add(null);              // vložíme null - je to povoleno
s.add(new Integer(-2));   // -2 už v množině je, podruhé se nevloží

System.out.println(s.size());  // vypíše počet prvků, tedy 4 (včetně hodnoty null)

TreeSet - množina se stromovou strukturou

Pro práci se seřazenými prvky použijeme třídu TreeSet. Protože je to seřazená množina, implementuje rozhraní SortedSet. Většina operací se provádí v logaritmickém čase.

Okruh použití TreeSet je vymezen potřebou seřazené množiny. Pokud vkládané prvky neimplementují rozhraní Comparable, musíme pro ně definovat komparátor (tj. implementovat rozhraní Comparator) a předat ho konstruktoru objektu TreeSet.

SortedSet s = new TreeSet();  // vytvoření množiny
s.add(new Double(12.3));      // vložíme 3 prvky
s.add(new Double(100.456));
s.add(new Double(-0.001));

System.out.println("První prvek je: " + s.first()); // vypíše první prvek

Iterator it = s.iterator();       // iterujeme přes všechny prvky
while (it.hasNext()) {            // budou se vypisovat ve vzestupném pořadí
  System.out.println(it.next());
}

ArrayList - pole proměnné velikosti

Podobně jako minule zmíněná třída Vector (o ní ještě bude řeč) poskytuje i tato třída implementaci pole o proměnné délce. Přístup přes index je v konstatním čase, přidávání na začátek nebo modifikace uvnitř posloupnosti v čase lineárním.

ArrayList použijeme ve všech případech, kde bychom jinak použili běžné pole a potřebujeme měnit délku. Výjimkou jsou případy, kdy velmi často dochází k přidávání prvků na začátek nebo provádět změny uvnitř seznamu - tam se ArrayList nehodí.

Následující příklad ukazuje podobnost práce s polem a s kontejnerem typu ArrayList, a samozřejmě výhodu použití kontejneru:

String sa[] = new String[3];  // vytvoření pole pro 3 položky
sa[0] = "";                   // vložíme do něj prvky
sa[1] = "abcd";
sa[2] = "123w";
// tady končíme - pole nejde zvětsit

List l = new ArrayList(3);     // vytvoření seznamu pro 3 položky
l.add(0, "");                  // vložení prvků
l.add(1, "abcd");
l.add(2, "123w");

// přidání dalších prvků - 1. varianta (vhodná pro přidání více prvků)
l.ensureCapacity(5);      // zvětšíme kapacitu seznamu (zde na 5)
l.add(3, "tohle JDE");    // přidáme prvek
l.add(4, "pokračujeme");  // přidáme prvek...

// přidání dalších prvků - 2. varianta (vhodná pro jednotlivé prvky)
l.add("tohle také JDE");  // přidáme prvek
l.add("pokračujeme");     // přidáme prvek...

LinkedList - spojový seznam

Třída LinkedList představuje dobře známý spojový seznam prvků. Co to znamená, lze snadno domyslet. Přístup podle indexové pozice je v lineárním čase, zatímco přidávání a mazání probíhá konstantní rychlostí.

Doména použití třídy LinkedList je omezena na případy s častými modifikacemi na jiných místech, než je konec seznamu.

Opět připomínám, i přes snadný přístup přes index prvků je při sekvenčním přístupu obecně mnohem efektivnější používat iterátory (pro tuto třídu to platí dvojnásob).

HashMap - asocitativní kontejner s hešovací tabulkou

Obdoba HashSet pro asociativní přístup k hodnotám. Pro rychlost i paměťovou náročnost platí to, co bylo řečeno u třídy HashSet. Prázdné (null) klíče a hodnoty jsou povoleny.

Použijeme prakticky ve všech případech, kdy nepotřebujeme seřazené klíče. Viz následující příklad s příponami a MIME typy dat:

Map m = new HashMap();        // vytvoří se asociativní kontejner
m.put("txt",  "text/plain");  // vložení dvojic klíč-hodnota
m.put("html", "text/html");
m.put("jpg",  "image/jpeg");
m.put("mpg",  "video/mpeg");

// nyní pomocí klíče přistupujeme k hodnotám
System.out.println("Přípona .jpg má typ: " + m.get("jpg"));  // vypíše "image/jpeg"
System.out.println("Přípona .gif má typ: " + m.get("gif"));  // vypíše "null" (nebylo nalezeno)

TreeMap - asocitativní kontejner se stromovou strukturou

Opět obdoba - tentokrát TreeSet. Oproti HashMap přináší seřazení klíčů.

Používá se při nutnosti mít seřazené klíče. Samozřejmostí je splnění podmínek pro porovnatelnost klíčů (viz HashSet).

Speciální implementační třídy

Jsou určité případy, kdy nám žádná z výše uvedených implementací nevyhoví. Proto máme k dispozici ještě další implementace, s jejichž pomocí můžeme dosáhnout požadovaných cílů. Podívejme se na některé z nich:

LinkedHashSet - zřetězená množina s hešovací tabulkou

Kompromis mezi HashSet a TreeSet, má zaručené pořadí prvků při rychlosti řádově stejné jako HashSet. Prvky jsou uloženy v pořadí, v jakém se vkládají, pokud ovšem nedojde k vícenásobnému vložení téhož prvku (prvek se znovu nevkládá, zůstane na původní pozici). Je třeba si uvědomit, že i když je zaručeno pořadí, nejedná se o seřazenou množinu a třída tedy neimplementuje rozhraní SortedSet.

LinkedHashMap - zřetězený asociativní kontejner s hešovací tabulkou

Obdoba LinkedHashSet pro asociativní kontejner. Platí to, co bylo řečeno u LinkedHashSet. Tato třída se hodí pro tvrobu různých pamětí s omezenou asociativitou (LRU apod.).

K další příkladům speciálních implementací se dostaneme při seznámení se změnami CF v Javě 5.0.

Zastaralé implementace

Již před vznikem CF existovaly v Javě určité implementace kontejnerů. Protože zde přetrvávají i nadále, není od věci je také trochu prozkoumat.

Vector - pole proměnné velikosti

Chování třídy Vector je prakticky shodné s třídou ArrayList s drobnými rozdíly. Vector má některé metody navíc (např. hledání od určitého indexu), lze mu stanovit přírůstek kapacity a je synchronizovaný (viz dále). V běžných případech dnes nemáme důvod používat Vector namísto třídy ArrayList.

Hashtable - hešovací tabulka

Chování obdobné jako u třídy HashMap, nepovoluje však prázdné klíče ani hodnoty a má synchronizaci.

Wrappery pro práci s kolekcemi

Existuje více způsobů, jak měnit vlastnosti instancí nějakých objektových tříd - lze to udělat např. parametry v konstruktoru nebo použitím tzv. wrapperů, což jsou objekty, které se "předřadí" před původní objekty, převezmou navenek jejich chování a přidají, odeberou či změní právě to, co je třeba. Pro změnu chování kontejnerů tu takové wrappery máme.

Synchronizační wrappery

Všechny standardní implementace kolekcí jsou bez synchronizace vícenásobného přístupu k objektu, takže se ve vícevláknovém prostředí může stát, že k témuž objektu přistupuje více vláken současně a dojde k přečtení nekonzistentních dat nebo k poškození objektu.

Máme-li záruku, že ke kolizi nemůže dojít (program je pouze jednovláknový), není třeba zajišťovat synchronizaci. Na tento předpoklad ale nemůžeme prakticky nikdy spoléhat (zejména pokud píšeme opakovaně použitelný kód) a musíme synchronizaci zajistit buď explicitně (což je pracnější, přestože výkonnostně efektivnější) nebo použít synchronizační wrapper. Netýká se to "starých" kontejnerů Vector a Hashtable, ty mají synchronizaci již v sobě.

Wrapper funguje prostě tak, že příslušné statické metodě z třídy Collections (pozor, neplést s rozhraním Collection!) předáme původní objekt a metoda nám vrátí wrapper k tomuto objektu, který už pak používáme stejně jako původní objekt (zde je jasně vidět, jak se hodí pracovat s rozhraním namísto konkrétní implementace). Více ukáže příklad:

// typický příklad - nepotřebujeme nesynchronizovanou instanci
List l = Collections.synchronizedList(new LinkedList());

// pro speciální použití - zachovává přístup k původní instanci
SortedSet s1 = new TreeSet();
SortedSet s2 = Collections.synchronizedSortedSet(s1);

Wrappery pro zákaz modifikací

Někdy je třeba zakázat jakékoliv změny v kontejneru. Nejčastěji tehdy, když z nějakého uceleného systému (který se stará o přípravu dat) předáváme někam ven referenci na kontejner a nechceme, aby ho někdo zvenku měnil.

Způsob vytvoření wrapperu je obdobný jako v případě synchonizačního wrapperu, opět je to zřejmé z příkladu. Pokus o modifikaci wrapperového kontejneru způsobí výjimku UnsupportedOperationException. Původní kontejner samozřejmě lze (přes referenci na něj) i nadále měnit.

// vytvoření seznamu
List lst = new ArrayList();

// příprava dat apod.

// nyní se vytvoří neměnná kolekce
Collection c = Collections.unmodifiableCollection(lst);

// pokus o změnu - vyvolá výjimku UnsupportedOperationException
c.add(new Object());

Praktická ukázka

Kdo by měl zájem, může si prohlédnout a vyzkoušet praktickou ukázku použití kontejnerů. V souboru PhoneBook.java najdete velice jednoduchý program, který ukazuje práci s kolekcemi na primitivním telefonním seznamu.

V Javě 5.0 došlo u kontejnerů k poměrně významným změnám - přibyla typová bezpečnost, nová rozhraní a implementace atd. K tomu se dostaneme příště, podobně jako k algoritmům, které mohou nad kolekcemi pracovat.

Verze pro tisk