21. Gyűjtemények

A gyűjtemények (vagy más néven tárolók, konténerek, kollekciók) olyan típuskonstrukciós eszközök, melynek célja egy vagy több típusba tartozó objektumok memóriában történő összefoglaló jellegű tárolása, manipulálása és lekérdezése.

A gyűjtemény keretrendszer

A gyűjtemény keretrendszer (Java Collections Framework, JCF) egy egységes architektúra, ami a gyűjtemények használatára és manipulálására szolgál. A gyűjtemény keretrendszer tartalmazza:

  • interfészek: absztrakt adattípusok reprezentációja. Az interfészek lehetővé teszik a gyűjtemények szolgáltatásainak (publikus interfészének) megvalósítás-független ábrázolását.
  • implementációk: a gyűjtemény interfészek konkrét implementációi. Főként ezek az újrafelhasználható adatstruktúrák.
  • algoritusok: azok a metódusok, amelyek hasznos műveleteket valósítanak meg, mint például a keresés vagy a rendezés egy objektumon, ami implementálható különböző gyűjtemény interfészeken. Ezeket az algoritmusokat többalakúnak hívjuk: azonos metódus használható különböző implementációk esetén is. Elsősorban az algoritmusok újrafelhasználható funkcionalitása.

A JCF-hez hasonló legismertebb megoldás a C++ nyelvű szabványos minta-könyvtár (Standard Template Library, STL).

A Gyűjtemény keretrendszer használatának előnyei

A Java Gyűjtemény keretrendszer az alábbi előnyökkel rendelkezik:

Csökkenti a fejlesztési időt

Mivel kész adatstruktúrák és algoritmusok állnak rendelkezésünkre, a Gyűjtemény keretrendszer lehetővé teszi, hogy a program fontosabb részével foglalkozzunk, ahelyett, hogy alacsonyszintű programozással kelljen foglalkoznunk.

Növeli a programozás sebességét és minőségét

A JCF gyors és jó minőségű algoritmus-, és adatstruktúra-implementációkkal rendelkezik. A különböző implementációk minden egyes interfésznél felcserélhetők, így a programokat könnyen össze lehet hangolni a gyűjtemény implementációkkal. Több időt tud arra fordítani, hogy növelje a programok minőségét és sebességét, mivel megszabadítja attól a rabszolgamunkától, hogy saját adatstruktúrákat kelljen írnia.

Megengedi az együttműködést a nem kapcsolódó API-k között

Ha két különböző függvénykönyvtár nem illeszthető egymáshoz közvetlenül, akkor lehet akár a keretrendszer a közös nevező az illesztés megteremtése érdekében.

Csökkenti az új API-k használatának és tanulásának nehézségét

Régen minden egyes API-nál egy kis segéd API-t készítettek arra, hogy manipulálja az egyes gyűjteményeket. Kevés összefüggés volt az erre a célra készült gyűjtemények segéd API-jai között, így külön-külön meg kell tanulni azokat, így könnyen hibát ejthetünk ezek használatával. Az általános gyűjtemény interfészek megjelenésétől ez a probléma már a múlté.

Megkönnyíti az új API-k tervezését

A tervezőknek és a kivitelezőknek nem kell újra kidolgozni az API-t, valahányszor készítenek egy gyűjteményekre alapozott API-t, hanem az általános gyűjtemény interfészt használhatják.

Elősegíti a szoftver újrafelhasználhatóságát

Az gyűjtemény interfészekkel összhangba hozott új adatstruktúrák természetesen újra felhasználhatók. Hasonlóan, új algoritmus fejlesztésekor könnyen hozzákapcsolható lesz az összes létező eddigi megvalósításhoz.

21.1. Interfészek

A gyűjtemény interfészek különböző típusú gyűjtemények leírását teszik lehetővé, amint az alábbi ábra mutatja. Ezek az interfészek lehetővé teszik a különböző gyűjtemény-reprezentációk egységes kezelését. A gyűjtemény interfészek a Gyűjtemény keretrendszer alapjainak tekinthetők.

Gyűjtemény interfészek

Ahogy az ábrán látható, a gyűjtemény interfészek hierarchiát alkotnak: a Set egy specializált fajtája a Collection-nek, a SortedSet specializált fajtája a Set-nek, és így tovább. A hierarchia két egymástól független fából áll: a Map nem Collection leszármazott.
Vegyük figyelembe, hogy a gyűjtemény interfészek (általános, generikus) típus paraméterekkel dolgoznak. Például a Collection interfész deklarációja:

public interface Collection<E> ...

Az <E> szintaxis azt jelenti, hogy az interfész általános (generikus) típussal működik. Amikor deklarálunk egy Collection-t, meg tudjuk határozni, hogy milyen típusú objektumot tartalmaz a gyűjtemény. A típus paraméter a fordítóprogram számára lehetővé teszi, hogy csak az adott típusú objektumot engedje belerakni a gyűjteménybe, így csökkenti a futásidejű hibák számát.

Mikor megértjük, hogyan használjuk ezeket az interfészeket, akkor megértettük a Gyűjtemény keretrendszer lényegét. Ez a fejezet be fogja mutatni az általános irányelveket, hogy hogyan lehet hatékonyan használni ezeket az interfészeket. Továbbá irányt ad, hogy mikor melyik interfészt használjuk. Minden egyes interfészhez tanulni fogunk programozási trükköket, hogy segítsen megoldani a legtöbb későbbi problémát.

Hogy megőrizze a gyűjtemény interfészek kezelhetőségét, a Java platform nem különíti el az interfészeket a tartalom módosíthatósága szempontjából. (Bizonyos esetekben a gyűjtemények lehetnek állandók, fix méretűek vagy éppen csak bővíthetők.) A módosítási lehetőségek az egyes interfészekben szabadon választhatók: az adott implementáció választhatja azt is, hogy nem támogatja az összes műveletet. Ha egy nem támogatott művelet kerül meghívásra, az adott gyűjtemény implementáció az UnsupportedOperationException kivételt dobja. A Java platform minden általános célú implementációja támogatja az összes opcionális műveletet is.

A gyűjtemény interfészek

Collection

A gyűjtemény hierarchia gyökere. A Collection objektumok csoportját reprezentálja, amiket elemeknek hívjuk. A gyűjtemény interfész a legkisebb közös nevező a gyűjtemény implementációk között, és akkor érdemes ezt választani, ha a lehető legnagyobb rugalmasságra van szükség. A gyűjtemények néhány típusa engedélyezi az elemek duplikálását, a többi pedig nem. A gyűjtemények néhány típusa rendezett, a többi nem rendezett. A Java platform nem biztosít közvetlen implementációt ehhez az interfészhez, ehelyett a sokkal specifikusabb al-interfészeket implementálja.

Set

Ez a gyűjtemény nem tartalmazhat duplikált elemeket. Ezt az interfészt halmazok tárolására szokták használni, mint például a futó processzek halmaza.

List

A List rendezettséget biztosító gyűjtemény, néha szekvenciának is hívják. A listák tartalmazhatnak duplikált elemeket. A lista felhasználója egész index segítségével hozzá tud férni az elemekhez (hasonlóan a tömbök indexeléséhez), valamint lehetőséget kap a lista egyszerű bejárásához.

Queue

Tipikusan ez a gyűjtemény szokta tárolni a feldolgozásra váró elemeket. A Collection alapműveletein felül lehetőséget ad további beszúrási, kivételi, és megtekintési műveletekre.

Legtöbbször, de nem szükségképpen az elemeket FIFO (first-in-first-out) elv szerint rendezi. A kivételek között van a prioritási sor, amelyik rendezi az elemeket valamilyen szempont alapján. Bármilyen rendezést használunk, a sor elején van az az elem, amit legelőször el szeretnénk távolítani a remove vagy a poll metódus meghívásával. A FIFO sor minden új elemet a sor végére illeszt be. Más fajta sorok használhatnak más elhelyezési szabályokat.

Megjegyzés: A Queue gyűjteményekkel terjedelmi okokból a továbbiakban nem foglalkozunk.

Map

A kulcsokat értékekké képezi le. A leképezések nem tartalmazhatnak duplikált kulcsokat. Minden egyes kulcs legfeljebb egy értéket tud leképezni. Másként fogalmazva a Map kulcs-érték párokat tárol.

Az utolsó két gyűjtemény interfész csupán rendezett verziója a Set-nek és a Map-nek:

SortedSet

Az elemek növekvő sorrendben tárolását teszi lehetővé. Számos kiegészítő művelettel biztosítja, hogy kihasználhassuk a rendezettséget. Ezt az interfészt szokták használni olyan rendezett halmazként, mint például egy szólista vagy tagsági lista.

SortedMap

A leképezések kulcs szerinti növekvő sorrendbe tárolását teszi lehetővé. A rendezett leképezést használjuk a rendezett gyűjtemények kulcs/érték párjainál. Ilyen például a szótár vagy a telefonkönyv.

21.1.1 A Collection interfész

A Collection az objektumok (elemek) csoportját tárolja.

public interface Collection<E> extends Iterable<E> {
    // Basic Operations
    int size();
    boolean isEmpty();
    boolean contains(Object element);
    boolean add(E element);         // Optional
    boolean remove(Object element); // Optional
    Iterator iterator();

    // Bulk Operations
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c); // Optional
    boolean removeAll(Collection<?> c);        // Optional
    boolean retainAll(Collection<?> c);        // Optional
    void clear(); // Optional

    // Array Operations
    Object[] toArray();
    <T> T[] toArray(T[] a);
}

Az interfésznek van metódusa, ami megmondja hány elem van a gyűjteményben (size, isEmpty), leellenőrzi, hogy az adott objektum benne van-e a gyűjteményben (contains), hogy hozzáadjon elemet gyűjteményhez vagy elvegye belőle (add, remove), bejárót (más néven iterátort) szolgáltat a bejáráshoz (iterator).

Az add metódus boolean visszatérési értéke azt jelzi, hogy történt-e a gyűjteményben változás. Ugyanis olyan implementáció esetén, ahol az elemek többszörös tárolása nem megengedett, nem történik változás, ha az elemet már eleve tartalmazta a gyűjtemény. Hasonlóan, a remove metódus esetén csak akkor változik a gyűjtemény állapota, ha benne volt az adott elem, és így sikeres volt a kivétel.

A gyűjtemények bejárása

Két módja van hogy bejárjuk a gyűjteményeket. Az egyik a for-each ciklussal, a másik az iterátorok használatával.

For-each ciklus

A for-each ciklus megengedi, hogy bejárjuk a gyűjteményt vagy tömböt a for ciklus használatával. A következő kód a for-each ciklust használja, és minden elemet külön sorban jelenít meg:

for (Object o : collection)
    System.out.println(o);

Iterátorok

Az iterátor egy olyan objektum, ami megengedi, hogy bejárjuk a gyűjteményt és eltávolítsuk az elemeket a gyűjteményből, ha akarjuk.

Az Iterator interfész:

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove(); // Optional
}

A hasNext metódus visszatérési értéke true, ha az iterációnak van még be nem járt eleme. A remove metódus eltávolítja a gyűjteményből az utolsó elemet, amit a next hívására kaptunk. A remove metódus a visszatérési értékével jelzi, hogy sikeres volt-e az eltávolítás.

Az Iterator.remove az egyetlen biztonságos út, hogy módosítsuk a gyűjteményt az iteráció folyamán. A viselkedés meghatározatlan, ha a gyűjtemény más egyéb úton módosítva lett, amíg az iteráció folyamatban volt.

Iterátor használata célszerű a for-each ciklus helyett a következő esetekben:

  • Törölni szeretnénk a bejárás közben.
  • Ki szeretnénk cserélni az elemeket.
  • Egyszerre többféle bejárásra is szükség van.

A következő metódus mutatja, hogyan használjuk az iterátort szűrőnek egy tetszőleges gyűjteményben (ezzel áttekintjük, hogy a gyűjtemény hogyan távolítja el a specifikus elemeket):

static void filter(Collection c) {
    for (Iterator i = c.iterator(); i.hasNext(); )
        if (!cond(i.next()))
            i.remove();
}

Ez az egyszerű kis kódrészlet sokoldalú, ami azt jelenti, hogy működik bármely gyűjteményben, kivétel nélkül minden implementációban. Ez a példa bemutatja, milyen könnyű sokoldalú algoritmust írni a Gyűjtemény keretrendszer segítségével.

A Collection interfész tömeges metódusai

A tömeges metódusok nem egy elemmel, hanem egész gyűjteménnyel hajtanak végre műveleteket. Implementálni lehet ezeket a metódusokat az alap metódusokat használva, bár a legtöbb esetben az ilyen implementációk kevésbé hatékonyak.

A tömeges metódusok

  • containsAll
    true a visszatérési értéke, ha a cél gyűjtemény tartalmaz minden elemet a meghatározott gyűjteményben (részhalmaz)
  • addAll
    Minden elemet hozzáad a meghatározott gyűjteményhez (unió)
  • removeAll
    Eltávolítja a célgyűjteményből az összes olyan elemet, amit a meghatározott gyűjtemény tartalmazott (különbség)
  • retainAll
    Eltávolítja a célgyűjteményből az összes olyan elemet, amit a meghatározott gyűjtemény nem tartalmazott. Azaz, csak azokat tartja meg a célgyűjteményben, amiket a meghatározott gyűjtemény is tartalmazott. (metszet)
  • clear
    Eltávolítja az összes elemet a gyűjteményből.

Az addAll, removeAll, és a retainAll metódus mindig true-val tér vissza, ha a célgyűjtemény módosítva volt a művelet végrehajtása alatt.

Egy egyszerű példa tömeges metódusok erejéről: a következő kifejezés eltávolítja az e elem minden példányát a c gyűjteményből:

c.removeAll(Collections.singleton(e));

Különösen praktikus, ha le akarjuk törölni az összes null elemet a gyűjteményből:

c.removeAll(Collections.singleton(null));

A kifejezés használja a Collections.singleton metódust, amelyik egy statikus gyártó metódus, ami visszaad egy olyan gyűjteményt, amely csak egy meghatározott elemet tartalmaz.

A Collection interfész tömb metódusai

A toArray metódusok olyanok, mint egy híd a gyűjtemények és a régebbi API-k között, amik tömböket várnak a bementen. A tömb metódusok lehetővé teszik, hogy a gyűjtemény tartalmát tömbként is elérhetővé tegyék. A paraméterek nélküli változat készíti el egy új Object tömböt. A bonyolultabb formája lehetővé teszi, hogy a hívó paraméterként egy tömböt adjon, és az eredmény is ilyen típusú tömb lesz.

Például, feltételezzük, hogy c egy gyűjtemény. Ekkor a következő metódus létrehoz egy tömböt, amelynek métere megegyezik a gyűjtemény méretével, elemei pedig a gyűjtemény elemei:

Object[] a = c.toArray();

Tegyük fel, hogy c ismert és csak sztringet tartalmaz (c típusa Collection<String>). Ekkor használható a következő változat is:

String[] a = c.toArray(new String[0]);

21.1.2 A Set interfész

A Set egy speciális Collection, amely nem tartalmaz duplikált elemeket. A Set nem tartalmaz új metódust a Collection-tól örököltekhez képest. A Set a tartalmazott objektumok equals és a hashcode metódusát használja arra, hogy a többszörös tárolást kiszűrje. Két Set objektum akkor egyenlő, ha ugyanazon elemeket tartalmazzák. A Set interfész:

public interface Set<E> extends Collection<E> {
    // Basic Operations
    int size();
    boolean isEmpty();
    boolean contains(Object element);
    boolean add(E element);         // Optional
    boolean remove(Object element); // Optional
    Iterator iterator();
    // Bulk Operations
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c); // Optional
    boolean removeAll(Collection<?> c);        // Optional
    boolean retainAll(Collection<?> c);        // Optional
    void clear();                              // Optional
    // Array Operations
    Object[] toArray();
    <T> T[] toArray(T[] a);
}

A Java platform három általános Set implementációt tartalmaz: a HashSet, TreeSet, és LinkedHashSet. HashSet esetén az elemeket egy hash táblában tárolja, ez a legjobb választás, ha az elemek bejárása nem fontos. A TreeSet az elemeket egy piros-fekete fában tárolja, ami az elemek bejárását hatékonyan meg tudja valósítani, de egy elem elérése, beszúrása lassabb, mint a HashSet esetén. A LinkedHashSet ötvözi a láncolt listákat a hash táblával.

Nézzünk egy egyszerű példát. Feltételezzük, hogy van egy c nevű Collection-ünk, és szeretnénk még egy Collection-t létrehozni, amely ugyanazokat az elemeket tartalmazza, de minden elemet csak egyszeresen.

Collection<Type> noDups = new HashSet<Type>(c);

Létrejön egy Set, amely nem tartalmaz duplikált elemeket, de a c összes eleme benne van. Az alapértelmezett konverziós konstruktort használjuk a tényleges létrehozásra.

A Set interfész alapvető műveletei

A size metódus visszatér az elemek számával. Az add metódus a Set-hez adja a megadott elemet, ha nem tudja, akkor false értékkel tér vissza. A remove metódus eltávolítja a megadott elemet a listából, ha ez sikerült, akkor false értékkel tér vissza. Az iterator metódus visszaad egy Iterator objektumot.

A következő példa a parancssori paraméterként kapott szavakat eltárolja az s objektumban, kiírja a duplikált szavakat, végül az eltérő szavak számát, és a szavakat:

import java.util.*;
public class FindDups {
    public static void main(String args[]) {
        Set<String> s = new HashSet<String>();
        for (String a : args)
            if (!s.add(a))
                System.out.println("Duplicate: " + a);
        System.out.println(s.size()+" distinct words: "+s);
    }
}

Futtassuk a programot:

java FindDups i came i saw i left

A kimenet a következő lesz:

Duplicate: i
Duplicate: i
4 distinct words: [i, left, saw, came]

Megjegyezzük, hogy a referencia típusát szokás interfész típussal (Set) leírni, míg az objektum típusa egy implementációs osztály lesz (HashSet). Ez egy nagyon ajánlott programozási gyakorlat, amivel könnyebb rugalmas kódot készíteni. Ha később esetleg abc sorrendben akarjuk a szavakat kiírni, csupán le kell cserélni HashSet-et TreeSet-re. Ez az egyszerű, egysoros változtatás ilyen eredményt produkál:

Duplicate word: i
Duplicate word: i
4 distinct words: [came, i, left, saw]

A Set interfész tömeges metódusai

A tömeges metódusok különösen jó szolgálatot tesznek a Set esetén, hiszen így egyszerűen megvalósíthatók az algebrából ismert halmazműveletek:

  • s1.containsAll(s2):
    Igaz logikai értékkel tér vissza, ha s2 részhalmaza s1-nek (s2 részhalmaza s1-nek, ha s1 tartalmazza az s2 összes elemét).
  • s1.addAll(s2):
    Az s1-be s1 és s2 uniója kerül.
  • s1.retainAll(s2):
    Az s1-be s1 és s2 metszete kerül.
  • s1.removeAll(s2):
    Az s1-be s1 és s2 különbsége (s1\s2) kerül.

Ha azt szeretnénk, hogy az unió, metszet vagy különbség képzés során egyik halmaz se módosuljon (ahogy az matematikailag is várható), akkor a következő módon kell alkalmazni a metódusokat:

Set<Type> union = new HashSet<Type>(s1);
union.addAll(s2);
Set<Type> intersection = new HashSet<Type>(s1);
intersection.retainAll(s2);
Set<Type> difference = new HashSet<Type>(s1);
difference.removeAll(s2);

Nézzük meg újra a FindDups programot. Azt akarjuk tudni, hogy melyik szavak fordulnak elő egyszer a vitatott listában, és mely szavak fordulnak elő többször, de nem akarunk duplán kiírt szavakat látni. Ezt úgy tudjuk elérni, hogy két halmazt hozunk létre: az egyik minden elemet tartalmaz, a másik csak a duplikáltakat. Nézzük a programot:

import java.util.*;
public class FindDups2 {
    public static void main(String args[]) {
        Set<String> uniques = new HashSet<String>();
        Set<String> dups = new HashSet<String>();
        for (String a : args)
            if (!uniques.add(a))
                dups.add(a);
        // Destructive set-difference
        uniques.removeAll(dups);
        System.out.println("Unique words:    " + uniques);
        System.out.println("Duplicate words: " + dups);
    }
}

Ha lefuttatjuk az előző parancssori paraméterlistával (i came i saw i left), akkor a következő eredményt kapjuk:

Unique words:    [left, saw, came]
Duplicate words: [i]
A halmazelméleti szimmetrikus differencia a következőképpen állítható elő:
Set<Type> symmetricDiff = new HashSet<Type>(s1);
symmetricDiff.addAll(s2);
Set<Type> tmp = new HashSet<Type>(s1);
tmp.retainAll(s2));
symmetricDiff.removeAll(tmp);

A symmetricDiff-ben először a két halmaz unióját állítjuk elő az addAll metódussal, majd a temp-ben előállított metszetet kivonjuk belőle a removeAll metódussal.

A Set interfész tömb metódusai

Ezek a metódusok semmiben nem térnek el a Collection-nál leírtaktól.

21.1.3 A List interfész

A List egy rendezett Collection. A List duplikáltan is tartalmazhat elemeket. A Collection-ból örökölt metódusokon kívül a List interfész a következő lehetőségeket tartalmazza:

  • Pozíció szerinti elérés: Az elemek a listában betöltött helyük alapján is elérhetők.
  • Keresés: A megadott elemet kikeresi a listából, és visszaadja a pozícióját.
  • Bejárás: Az Iterator alapú szolgáltatások bővültek.
  • Részlista: Lehetővé tesz részlista műveleteket.

A List interfész:

public interface List<E> extends Collection<E> {
    // Positional Access
    E get(int index);
    E set(int index, E element);    // Optional
    boolean add(E element);         // Optional
    void add(int index, E element); // Optional
    E remove(int index);            // Optional
    abstract boolean addAll(int index,
        Collection<? extends E> c);  //Optional
    int indexOf(Object o);
    int lastIndexOf(Object o);
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);
    List<E> subList(int from, int to);
}

A Java platform két alapvető List megvalósítást tartalmaz: Arraylist és LinkedList.

Collection metódusok

A metódusok öröklődnek a Collection-ból, és mindent az elvárásainknak megfelelően használhatunk.

A remove metódus mindig az első előforduló elemet törli a listából. Az add és addAll metódusnál az elem a lista végére kerül. Például a list1 végére másolja a list2 elemeit.

list1.addAll(list2);

A következő kód elkészíti a list3 nevű listát, amelynek eredménye ugyanaz, mint az előzőnek, de nem rontja el list1-et:

List<Type> list3 = new ArrayList<Type>(list1);
list3.addAll(list2);

Két List objektum akkor egyenlő, ha ugyanazok az elemek ugyanolyan sorrendben fordulnak elő benne.

A pozíció szerinti elérés és keresés metódusai

A set és remove metódusok egy adott elemhez pozícionálnak és felülírják, vagy eltávolítják azt. A keresési metódusok (indexOf és lastIndexOf) viselkedése tökéletesen megegyezik String osztálynál megismertekkel.

Az addAll metódus az adott Collection elemeit elhelyezi az adott pozíciótól kezdődően. Az elemeket sorrendben helyezi el egy Iterator segítségével.

A következő metódus megcseréli a két értéket a listában:

static <E> void swap(List<E> a, int i, int j) {
    E tmp = a.get(i);
    a.set(i, a.get(j));
    a.set(j, tmp);
}

A következő metódus arra használja a swap-et, hogy véletlenszerűen keverje az elemeket:

static void shuffle(List<?> list, Random rnd) {
    for (int i = list.size(); i > 1; i--)
        swap(list, i - 1, rnd.nextInt(i));
}

Az algoritmus találomra felcseréli az adott list elemeit Ez egy egyszerű módszer a keverésre. Másrészt az összes keverés valószínűsége megegyezik, feltéve, hogy a forrás is véletlenszerű, valamint gyors (csak list.size()-1 csere történt). A következő program bemutat egy példa felhasználást:

import java.util.*;
public class Shuffle {
    public static void main(String args[]) {
        List<String> list = new ArrayList<String>();
        for (String a : args)
            list.add(a);
        Collections.shuffle(list, new Random());
        System.out.println(list);
    }
}

A programot még rövidebbé és gyorsabbá tudjuk tenni. Az Array osztálynak van egy asList nevű statikus metódusa, ami egy tömb elemeit List-ként is elérhetővé teszi. Ez a metódus nem másolja át a tömb elemeit, csupán referenciákkal dolgozik, és ugyanazok az elemek a listából és a tömbből is elérhetők.

A visszaadott List objektum nem tartalmazza az opcionális add és remove metódusokat, hiszen a tömb mérete nem változhat. Nézzük meg a következő kódot:

import java.util.*;
public class Shuffle {
    public static void main(String args[]) {
        List<String> list = Arrays.asList(args);
        Collections.shuffle(list);
        System.out.println(list);
    }
}

Iterátorok

A List interfész esetén természetesen használható az őstől örökölt módszer a bejárásra, de van egy ennél több lehetőséget nyújtó megoldás is: a ListIerator. Ez az interfész megengedi a lista kétirányú bejárását és az ehhez kapcsolódó további műveleteket. A ListIterator interfész:

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous ();
    int nextIndex();
    int previousIndex();
    void remove(); // Optional
    void set(E o); // Optional
    void add(E o); // Optional
}

Három metódusát (hasNext, next és remove) az Iterator-tól örökölte, a hasPrevious és previous a visszafelé történő bejárást támogatja.

A következő példa visszafelé járja be a listát:

for (ListIterator<Type> i = list.listIterator(list.size());
     i.hasPrevious(); ) {
    Type t = i.previous();
    ...
}

A List interfész kétféle paraméterezéssel tud ListIterator-t gyártani. Paraméter nélkül a lista elejére pozícionál, míg az int paramétert váró verzió esetén a paraméter alapján pozícionál ListIterator tér vissza a listIterator metódus.

Az index vagy kurzor pozíció a következő alapján értendő: n hosszúságú lista esetén n+1 érvényes értéke van az indexnek, 0-tól n-ig minden egész. Az index mindig két elem között van a következő ábra szerint:

Index helyzete

Nézzük meg az indexOf működését:

public int indexOf(E o) {
    for (ListIterator<E> i = listIterator(); i.hasNext(); )
        if (o==null ? i.next()==null : o.equals(i.next()))
            return i.previousIndex();
    return -1; // Object not found
}

Ha az indexOf metódus visszatérési értéke i.previosIndex(), akkor megtalálta a keresett objektumot.

Az Iterator interfész szolgáltatása a remove metódus, mely a gyűjteményből eltávolítja az adott elemet. A ListIterator interfész további két metódust nyújt, amely módosítja a listát: set és add. A set metódus felülírja az aktuális elemet. A következő metódus használja set metódust az adott elem összes előfordulásának cserélése során:

public static <E> void replace(List<E> s, E val, E newVal) {
   for (ListIterator<E> i = s.listIterator(); i.hasNext(); )
      if (val==null ? i.next()==null : val.equals(i.next()))
         i.set(newVal);
}

Egy kis trükk van ebben a példában a val és az i.next() egyenlőség vizsgálatában. Ha a val értéke null, akkor a NullPointerException kivétel nem váltódik ki, hiszen ha val értéke null lenne, akkor a feltételes operátor másik ága értékelődik ki.

Az add metódussal új elemeket adhatunk a List-hez az aktuális kurzorpozíció elé. A következő példa bemutatja, hogy hogyan lehet a val minden előfordulását kicserélni a newVals listával:

public static <E> void replace(List<E> s, E val,
                               List<E> newVals) {
  for (ListIterator<E> i = s.listIterator(); i.hasNext(); ){
    if (val==null ? i.next()==null : val.equals(i.next())) {
      i.remove();
      for (E e : newVals)
        i.add(e);
    }
  }
}

Részlista művelet

A subList(int fromIndex, int toIndex) részlista metódus visszaadja a lista egy szeletét, a paraméterként megadott indexek figyelembevételével: fromIndex része, de toIndex nem része a visszaadott szeletnek. (Emlékeztetőül: a String osztály substring metódusa is így működik.) Ezért gyakori példa a következő:

for (int i = fromIndex; i < toIndex; i++) {
    ...
}

A visszaadott lista kapcsolatban marad az eredeti listával. Így bármilyen módosítás történik a részlistán, az hatással lesz az eredetire is, sőt ez fordítva is igaz. Ezért nincs szükség további részlista metódusokra. Nézzünk erre egy olyan példát, amikor a lista egy részét akarjuk törölni:

list.subList(fromIndex, toIndex).clear();

A következő példák csak egy részlistában keresnek:

int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);

Arra érdemes figyelni, hogy itt a visszaadott indexek a talált elemek részlistabeli indexeit jelentik, nem az eredeti list-belieket.

A következő metódus is a subList-et használja, hogy könnyítse a munkát. A feladata az, hogy a lista egy adott méretű végét levágja, és egyben vissza is adja azt. Másként fogalmazva egy index mentén történő szétvágásról van szó:

public static <E> List<E> dealHand(List<E> deck, int n) {
    int deckSize = deck.size();
    List<E> handView = deck.subList(deckSize - n, deckSize);
    List<E> hand = new ArrayList<E>(handView);
    handView.clear();
    return hand;
}

A következő program az előző dealHand metódust használja a Collection.suhffle-val együtt, hogy 52 lapból osszon le. A program 2 parancssori paramétert használ: a kezek számát és az egy kézbe osztandó lapok számát:

import java.util.*;
class Deal {
    public static void main(String[] args) {
        int numHands = Integer.parseInt(args[0]);
        int cardsPerHand = Integer.parseInt(args[1]);
        // Make a normal 52-card deck
        String[] suit = new String[]
            {"spades", "hearts", "diamonds", "clubs"};
        String[] rank = new String[]
            {"ace","2","3","4","5","6","7","8",
             "9","10","jack","queen","king"};
        List<String> deck = new ArrayList<String>();
        for (int i = 0; i <suit.length; i++)
            for (int j = 0; j <rank.length; j++)
                deck.add(rank[j] + " of " + suit[i]);
        Collections.shuffle(deck);
        for (int i=0; i<numHands; i++)
            System.out.println(dealHand(deck, cardsPerHand));
    }
}

A futó program ezeket az adatokat jeleníti meg:

% java Deal 4 5

[8 of hearts, jack of spades, 3 of spades, 4 of spades,
    king of diamonds]
[4 of diamonds, ace of clubs, 6 of clubs, jack of hearts,
    queen of hearts]
[7 of spades, 5 of spades, 2 of diamonds, queen of diamonds,
    9 of clubs]
[8 of spades, 6 of diamonds, ace of spades, 3 of hearts,
    ace of hearts]

List algoritmusok

A Collections osztály nagyon hatékonyan használható algoritmusokat nyújt listák kezelésére. A következő lista csak felsorolja a fontosabbakat:

  • sort: Rendezi a listát.
  • shuffle: Véletlenszerűen felcserél elemeket a listában. (Permutál.)
  • reverse: Megfordítja az elemek sorrendjét a listában.
  • rotate: Megforgatja az elemeket.
  • swap: Felcserél két meghatározott pozícióban levő elemet.
  • replaceAll: Az összes előforduló elemet kicseréli egy másikra.
  • fill: Felülírja az összes elemet egy meghatározott elemre.
  • copy: Átmásolja a forráslistát egy céllistába.
  • binarySearch: Egy elemeket keres a bináris keresési algoritmust használva.
  • indexOfSubList: Visszatér az első olyan indexszel, amelynél kezdődő részlista egyenlő a másik listával.
  • lastIndexOfSubList: Visszatér az utolsó olyan indexszel, amelynél kezdődő részlista egyenlő a másik listával.

21.1.4 Map interfész

A Map olyan tároló, ami kulcs-érték párokat tartalmaz. A Map nem tud tárolni duplikált kulcsokat, egy kulcshoz csak egy érték rendelhető. A Map interfész:

public interface Map {
    V put(K key, V value);
    V get(Object key);
    V remove(Object key);
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    int size();
    boolean isEmpty();
    void putAll(Map<? extends K,? extends V> t);
    void clear();
    public Set<K> keySet();
    public Collection<V> values();
    public Set<Map.Entry<K,V>> entrySet();
    public interface Entry {
        K getKey();
        V getValue();
        V setValue(V value);
    }
}

A Java platform három különböző Map implementációt tartalmaz: HashMap, TreeMap, LinkedHashMap.

A Map interfész főbb metódusai

A metódusok (put, get, containsKey, containsValue, size, és isEmpty) hasonlóképpen működnek, mint a Collection-nál. A következő program kilistázza a szövegben szereplő szavakat és azok gyakoriságát.

import java.util.*;
public class Freq {
    public static void main(String args[]) {
        Map<String, Integer>     m =
            new HashMap<String, Integer>();
        // Initialize frequency table from command line
        for (String a : args) {
            Integer freq = m.get(a);
            m.put(a, (freq == null ? 1 : freq + 1));
        }
        System.out.println(m.size() + " distinct words:");
        System.out.println(m);
    }
}

A program a következőképpen futtatható:

java Freq if it is to be it is up to me to delegate

A program kimenete:

8 distinct words:
{to=3, delegate=1, be=1, it=2, up=1, if=1, me=1, is=2}

Ha betűrendi sorrendbe akarjuk rendezni, akkor a HashMap-et TreeMap-re kell cserélni, és a következőket írja ki a képernyőre:

8 distinct words:
{be=1, delegate=1, if=1, is=2, it=2, me=1, to=3, up=1}

Ha a felbukkanás sorrendjére vagyunk kíváncsiak, akkor ez a LinkedHashMap-el tegyük, és a kimenet a következő lesz:

8 distinct words:
{if=1, it=2, is=2, to=3, be=1, up=1, me=1, delegate=1}

Két Map objektum könnyedén összehasonlítható. Akkor egyenlőek, ha a kulcs-érték párjaik megegyeznek. (A sorrend nem számít.))

A Map konstruktora egy új Map objektumot hoz létre egy már meglévő Map objektum tartalmával.

Map<K, V> copy = new HashMap<K, V>(m);

A Map interfész tömeges műveletei

A clear metódus törli a Map teljes tartalmát. A putAll metódussal átmásolható egy másik objektum tartalma. A következő példában a paraméterként kapott két Map unióját állítjuk elő:

static <K, V> Map<K, V> new AttributeMap(
        Map<K, V>defaults, Map<K, V> overrides) {
    Map<K, V> result = new HashMap<K, V>(defaults);
    result.putAll(overrides);
    return result;
}

Collection nézetek

A Map tartalmát háromféle szempont alapján nézhetjük vissza:

  • keySet: kulcsok halmaza (Set)
  • values: értékek gyűjteménye (Collection)
  • entrySet: kulcs-érték párok halmaza (Set)

A következő példa a kulcsok halmazának kiíratása:

for (KeyType key : m.keySet())
    System.out.println(key);

Ugyanez iterátorral:

for (Iterator<Type> i=m.keySet().iterator(); i.hasNext(); )
    if (i.next().isBogus())
        i.remove();

Kulcs-érték párok kiírása:

for (Map.Entry<KeyType, ValType> e : m.entrySet())
    System.out.println(e.getKey() + ": " + e.getValue());

21.1.5 Objektumok rendezése

Rendezzünk egy tetszőleges tartalmú l listát:

Collections.sort(l);

Ha a lista String-eket tartalmaz, akkor azt (Unicode-beli) abc sorrendbe rendezhetjük. Ha pedig Dátum (Date) tagokat tartalmaz, akkor időrendi sorrendbe. Hogyan történik ez? A String és a Date is megvalósítják a Comparable interfészt. Ez az interfész tartalmazza a legáltalánosabb rendezési eljárásokat, amely megengedi az osztálynak, hogy automatikusan rendezve legyen valamely szempont szerint. A következő táblázat összefoglalja a legfontosabb osztályokat, amelyek az interfészt megvalósítják.

Osztály Alapértelmezett sorrend
Byte előjeles szám
Character előjelnélküli szám
Long előjeles szám
Integer előjeles szám
Short előjeles szám
Double előjeles szám
Float előjeles szám
BigInteger előjeles szám
BigDecimal előjeles szám
Boolean false < true
File rendszerfüggő abc szerinti a teljes név alapján
String abc szerinti
Date időrendi
CollationKey abc szerinti a helyi jellemzők alapján

Ha a listánk olyan objektumokat tartalmaz, amelyek nem valósítják meg a Comparable interfészt, akkor a Collections.sort(list) hívás ClassCastException kivételt fog dobni.

Saját összehasonlítható osztály létrehozása

A Comparable interfész egyetlen metódust tartalmaz:

public interface Comparable<T> {
    public int compareTo(T o);
}

A comprateTo metódus összehasonlítja az objektumot az átvett objektummal, és visszatérési értéke negatív egész, nulla, vagy pozitív egész, ha az átvevő objektum kisebb, egyenlő vagy nagyobb, mint az átvett objektum. Ha a metódus nem tudja összehasonlítani a két objektumot, akkor ClassCastException-t dob.

A következő osztály emberek nevét tartalmazza összehasonlító eszközökkel kiegészítve:

import java.util.*;
public final class Name implements Comparable<Name> {
    private final String firstName, lastName;
    public Name(String firstName, String lastName) {
        if (firstName == null || lastName == null)
            throw new NullPointerException();
        this.firstName = firstName;
        this.lastName = lastName;
    }
    public String firstName() { return firstName; }
    public String lastName()  { return lastName;  }
    public boolean equals(Object o) {
        if (!(o instanceof Name))
            return false;
        Name n = (Name) o;
        return n.firstName.equals(firstName) &&
            n.lastName.equals(lastName);
    }
    public int hashCode() {
        return 31*firstName.hashCode() + lastName.hashCode();
    }
    public String toString() {
        return firstName + " " + lastName;
    }
    public int compareTo(Name n) {
        int lastCmp = lastName.compareTo(n.lastName);
        return (lastCmp != 0 ? lastCmp :
                firstName.compareTo(n.firstName));
    }
}

Ebben a rövid példában az osztály némileg korlátozott: nem támogatja a középső nevet, kötelező megadni a vezeték- és keresztnevet, és nem veszi figyelembe a nyelvi sajátosságokat. Azonban így is illusztrál néhány fontos pontot:

  • A konstruktor ellenőrzi, hogy az paraméterei null értékűek-e. Ez minden létrejövő Name objektum számára biztosítja, hogy jól formázott legyen, így semelyik más metódus nem dob NullPointerException-t.
  • A hashCode metódus újradefiniált. (Azonos objektumoknak azonos hash kódjuknak kell lennie)
  • Az equals metódus false értékkel tér vissza, ha a paraméterként kapott másik objektum null, vagy helytelen típus. Ilyen esetben a compareTo metódus futásidejű kivételt dob.
  • A toString metódus újradefiniálásával a Name olvasható formában jeleníthető meg. Ez mindig jó ötlet, különösen olyan objektumok esetén, amiket gyűjteménybe helyezünk. A különböző típusú gyűjtemények toString metódusai jól olvasható formában jelenítik meg a gyűjtemények tartalmát.
  • A comparateTo metódus összehasonlítja az objektumok legfontosabb részét (lastName). (Mint ahogy itt is, máskor is gyakran tudjuk használni a részek típusa szerinti alapértelmezett rendezést.) A lastName adattag String típusú, így az alapértelmezett rendezés pontosan megfelelő lesz. Ha az összehasonlítási eredmények nullától különbözőek, amely egyenlőséget jelent, kész vagyunk: csak vissza kell adni az eredményt. Ha a legfontosabb részek egyenlők, összehasonlítjuk a következőket (itt firstName). Ha ez alapján sem dönthető el a sorrend, továbblépünk.

A következő példa félépíti a nevek listáját:

import java.util.*;
public static void main(String[] args) {
        Name nameArray[] = {
            new Name("John", "Lennon"),
            new Name("Karl", "Marx"),
            new Name("Groucho", "Marx"),
            new Name("Oscar", "Grouch")
        };
        List<Name> names = Arrays.asList(nameArray);
        Collections.sort(names);
        System.out.println(names);
    }
}

A program futása után a következőt írja ki:

[Oscar Grouch, John Lennon, Groucho Marx, Karl Marx]

A Comparator-ok

Hogyan tudjuk az objektumokat az alapértelmezett rendezéstől eltérő más sorrendbe rendezni? Ilyen esetben jön jól a Comparator interfész, amely egyetlen egyszerű metódust tartalmaz:

public interface Comparator<T> {
    int compare(T o1, T o2);
}

A compare metódus összehasonlítja a két paramétert, visszatérési értéke negatív egész, nulla, vagy pozitív egész, ha az első paraméter kisebb, egyelő vagy nagyobb, mint a második. Ha valamelyik paraméter helytelen típusú a Comparator számára, a compare metódus ClassCastException-t dob.

Tegyük fel, hogy van egy Employee nevű osztályunk:

public class Employee implements Comparable<Employee> {
    public Name name()     { ... }
    public int number()    { ... }
    public Date hireDate() { ... }
        ...
}

Ha az Employee objektumok alapértelmezett rendezése a Name tag szerinti, akkor nem egyszerű a legmagasabb rangú dolgozókat kikeresni a listából. A következő program elkészíti a listát:

import java.util.*;
class EmpSort {
    static final Comparator<Employee> SENIORITY_ORDER =
                                 new Comparator<Employee>() {
        public int compare(Employee e1, Employee e2) {
            return e2.hireDate().compareTo(e1.hireDate());
        }
    };
    // Employee Database
    static final Collection<Employee> employees = ... ;
    public static void main(String[] args) {
        List<Employee>e = new ArrayList<Employee>(employees);
        Collections.sort(e, SENIORITY_ORDER);
        System.out.println(e);
    }
}

21.2. Implementációk

Az implementációk az előző fejezetben leírt interfészeket valósítják meg (implementálják). Az alábbiakban az implementációk fajtáit láthatjuk.

  • Általános célú implementációk: a leggyakrabban használt implementációk, mindennapos használatra tervezték
  • Speciális célú implementációk: arra tervezték, hogy speciális helyzetekben esetében használjuk. Nem szabványos teljesítmény karakterisztikák megjelenítésére, használati és viselkedési korlátozásokra.
  • Konkurens implementációk: erős konkurencia támogatására tervezték, többnyire az egyszálú teljesítmény rovására. Ezek az implementációk a java.util.concurrent csomag részét képzik.
  • Csomagoló implementációk: a többi implementációval összekombinálva használhatók (gyakran az általános célúval), hogy extra funkcionalitást biztosítsanak, vagy bizonyos funkciókat korlátozzanak
  • Kényelmi implementációk: mini implementációk, tipikusan a gyártó metódusokon keresztül érhetők el. Kényelmes és hatékony alternatívát biztosítanak az általános célú implementációk számára speciális esetekben.
  • Absztrakt implementációk: vázlatos implementációk, amik megkönnyítik az egyéni implementációk létrehozását.

Az általános-célú implementációkat az alábbi táblázat foglalja össze:

Hash tábla Átméretezhető tömb Fa Láncolt lista Hasító tábla + Láncolt lista
Set HashSet TreeSet LinkedHashSet
List ArrayList LinkedList
Map HashMap TreeMap LinkedHashMap

A táblázatban látható hogy a Set, a List és a Map interfészek többfajta általános célú implementációja használható. A SortedSet és a SortedMap interfészeknek nincs saját sora a táblázatban, ezeknek az interfészeknek egy implementációja van (TreeSet és TreeMap).

Az általános célú implementációk mind biztosítják az összes opcionális műveletet, amit az interfészek tartalmaznak. Mindegyik megengedi a null elemet mind a kulcsok, mind az értékek esetén. Egyik sem szinkronizált. Mindegyik szerializálható (Seriaizable), és biztosít egy publikus clone metódust.

A korábbival ellentétes elképzelést jelent az a tény, hogy ezek az implementációk nem szinkronizáltak. A régebbi Vector és Hashtable gyűjtemények szinkronizáltak. A jelenlegi megközelítés azért alakult ki, mert a gyűjteményeket sűrűn használják olyan helyeken, ahol a szinkronizálhatóság nem jelent előnyt. Ilyenek például az egyszálú használat, csak olvasási használat, és ha egy olyan nagyobb adat objektum részét képzik, amely megcsinálja a saját szinkronizációját. Általános API tervezési tapasztalat az, hogy ne kötelezzük a felhasználót olyan szolgáltatás használatára, amit nem sokszor használ. Ráadásul a szükségtelen szinkronizáció adott körülmények között akár holtpontot is eredményezhet.

Általános szabály, hogy programíráskor az interfészeken, és nem az implementációkon kell gondolkodni. Ez az oka annak, hogy ebben a fejezetben nincsenek példa programok. Legtöbb esetben az implementáció megválasztása csak a teljesítményt befolyásolja. Ahogy azt a korábbiakban említettük, egy előnyben részesített programozói stílus az, ha válasszunk egy implementációt a Collection létrehozásakor, és rögtön hozzá rendeljük az új Collection-t egy olyan változóhoz, ami adott interfész típusú (vagy egy olyan eljárásnak adjuk át a Collection-t, ami egy adott interfész típusú paramétert vár). Így a program nem függ majd egy adott implementáció esetén az ahhoz hozzáadott új metódusoktól, ezáltal a programozó bármikor szabadon változtathatja az implementációt, mikor jobb teljesítményt szeretne elérni, vagy a működési részleteket módosítani.

21.2.1 Általános célú Set implementációk

Három általános célú Set implementáció létezik: HashSet, TreeSet, és LinkedHashSet. Általában egyszerű eldönteni azt, hogy melyiket kell használni. A HashSet sokkal gyorsabb, mint a TreeSet (konstans végrehajtási idő szemben a logaritmikus idővel a legtöbb művelet esetén), de nem biztosít rendezhetőséget. Ha a SortedSet interfész műveleteire, vagy egy érték szerint rendezett iterációra van szükség, akkor a TreeSet használata javasolt, egyéb esetben a HashSet.

A LinkedHashSet bizonyos értelemben egy átmenetet képez a HashSet és a TreeSet között. Megvalósítását tekintve ez egy olyan hash-tábla, aminek elemei egy láncolt lista segítségével vannak összekötve, így rendezett-beszúrásos iterációt biztosít (a legritkábban használt elemet szúrja be a legsűrűbben használtba), és majdnem olyan gyorsan fut, mint a HashSet. A LinkedHashSet implementációja megkíméli a használóját az olyan nem specifikált, általában kaotikus rendezéstől, mint a HashSet esetében, valamint a TreeSet esetében felmerülő többlet költségektől is.

Figyelemre méltó, hogy HashSet használata esetén az iterációk száma lineárisan arányos a benne tárolt bejegyzések számával, valamint a beszúrások számával (a kapacitással). Emiatt egy túl magas kezdeti kapacitás választása esetén feleslegesen pazaroljuk az időt és a memóriát. Másrészt a túl alacsony kezdeti kapacitás választás esetén szintén időt vesztünk azzal, hogy az adatstruktúrát mindig át kell másolnunk, mikor a kapacitást növeljük. Ha nem specifikálunk kezdeti kapacitást, akkor az alapbeállítás lép érvénybe, ami 16. A kapacitást mindig felfele kerekítik a legközelebbi kettő hatványra. A kezdeti kapacitást a konstruktor int paramétereként adhatjuk meg. A következő kódsor egy olyan HashSet példány létrehozását mutatja be, ahol a kezdeti kapacitás 64.

Set<String> s= new HashSet<String>(64);

A LinkedHashSet-nek hasonló beállítási paraméterei vannak, mint a HashSet-nek, de az iteráció idejét nem befolyásolja a kapacitás. A TreeSet nem rendelkezik beállítási paraméterekkel.

21.2.2 Általános célú List implementációk

Két általános célú List implementáció létezik: ArrayList és LinkedList. Leggyakrabban valószínűleg az ArrayList–et fogjuk használni. Konstans elérési időt biztosít a lista elemeinek pozícionált elérésekor, egyszerű és gyors. Nem szükséges csomópont objektumot foglalni minden lista elemhez, és képes kihasználni a System.arraycopy nyújtotta előnyöket, amikor egyszerre több listaelemet kell mozgatunk.

Abban az esetben, ha gyakran kell elemeket hozzáadni egy lista elejéhez, vagy iterálni a listán, hogy valamelyik belső elemét kitöröljük, akkor érdemes LinkedList-t használni. Ezek a műveletek konstans idő alatt végrehajtódnak egy LinkedList-ben, míg egy ArrayList-ben lineáris idejűek, de ezért cserébe nagy árat kell fizetni a teljesítmény terén. A pozícionált elérés lineáris idejű LinkedList esetén, míg ugyanez konstans ArrayList-nél, továbbá ez a konstans-faktor a LinkedList esetében sokkal rosszabb.

Az ArrayList-nek egy állítható paramétere a kezdeti kapacitása. Ez azt határozza meg, hogy hány eleme legyen az ArryaList-nek, mielőtt növelni kéne az elemek számát. A LinkedList-nek nincs állítható paramétere.

21.2.3 Általános célú Map implementációk

A három általános célú Map Implementáció a HashMap, a TreeMap és a LinkedHashMap. Ha szükség van összegyűjtött információra, a TreeMap-et használjuk, ha a legjobb sebesség kell, és nem szükségesek az iterációk, használhatjuk a HashMap-et, ha az utóbbihoz hasonló sebesség kell és iteráció is, akkor használjunk LinkedHashMap-et. Hasonlóképp, a Set implementáció blokkban minden ugyanúgy működik, mint a Map implementációban.

21.3. Algoritmusok

Ebben a fejezetben a Java platform által kínált újra felhasználható, sokalakú algoritmusok egy részével foglalkozunk. Mindegyikük a Collections osztály statikus metódusa. Az algoritmusok széles skálája a List-eknél működik. De egy pár tetszőleges kollekciók esetében is működik.

Rendezés

A sort algoritmus újrarendezi a listát. A művelet két formája adott. Az egyszerűbb forma veszi a listát, és rendezi azt az elemek természetes (alapértelmezett) sorrendjében.

Itt egy egyszerű program, ami kiírja betűrendben a parancssori paramétereket:

import java.util.*;
public class Sort {
    public static void main(String args[]) {
        List<String> l = Arrays.asList(args);
        Collections.sort(l);
        System.out.println(l);
    }
}

Futtassuk a programot:

java Sort i walk the line

A következő kimenetet kapjuk:

[i, line, the, walk]

A program megmutatta, hogy ezt az algoritmust nagyon könnyű használni.

Tegyük fel, hogy vannak anagrammákat tartalmazó szólistáink. Szeretnénk kiíratni azokat a listák hossza szerinti csökkenő sorrendben, de csak az adott méretnél (pl. 8) nem kevesebb elemű listákat. A következő példa megmutatja, hogy hogyan érhetjük el ezt a sort metódus második formájának segítségével.

Maguk a szólisták egy m objektumban vannak tárolva. Erről leválogatjuk a megfelelő hosszúságúakat. Ezután a kód rendezi a listát, összehasonlítást végez, és végrehajtja a fordított méret szerinti rendezést. Végül a kód ismét végigfut a listán és kiírja az elemeket (a szavak csoportját):

List<List<String>> winners = new ArrayList<List<String>>();
for (List<String> l : m.values())
    if (l.size() >= minGroupSize)
        winners.add(l);
Collections.sort(winners, new Comparator<List<String>>() {
    public int compare(List<String> o1, List<String> o2) {
        return o2.size() - o1.size();
    }
});
// Szócsoportok kiírása
for (List<String> l : winners)
    System.out.println(l.size() + ": " + l);

Futtassuk a programot, a minimum anagramma csoport méretével (8) együtt a következő kimenetet kapjuk:

12: [apers, apres, asper, pares, parse, pears, prase, presa, rapes, reaps, spare, spear]
11: [alerts, alters, artels, estral, laster, ratels, salter, slater, staler, stelar, talers]
10: [least, setal, slate, stale, steal, stela, taels, tales, teals, tesla]
9: [estrin, inerts, insert, inters, niters, nitres, sinter, triens, trines]
9: [capers, crapes, escarp, pacers, parsec, recaps, scrape, secpar, spacer]
9: [palest, palets, pastel, petals, plates, pleats, septal, staple, tepals]
9: [anestri, antsier, nastier, ratines, retains, retinas, retsina, stainer, stearin]
8: [lapse, leaps, pales, peals, pleas, salep, sepal, spale]
8: [aspers, parses, passer, prases, repass, spares, sparse, spears]
8: [enters, nester, renest, rentes, resent, tenser, ternes, treens]
8: [arles, earls, lares, laser, lears, rales, reals, seral]
8: [earings, erasing, gainers, reagins, regains, reginas, searing, seringa]
8: [peris, piers, pries, prise, ripes, speir, spier, spire]
8: [ates, east, eats, etas, sate, seat, seta, teas]
8: [carets, cartes, caster, caters, crates, reacts, recast, traces]

Keverés

A keverés algoritmusa bizonyos értelemben az ellenkezőjét teszi, mint amit a rendezés tesz. Lerombol bármilyen rendezést, ami esetleg található a listában. Ez az jelenti, hogy ez az algoritmus újrarendezi a listát úgy, hogy a véletlenszerűséget használja az összes azonos valószínűséggel bekövetkező permutációhoz, feltételezve a ténylegesesen rendszertelen forrást. Például tudjuk használni a keverést egy pakli kártya megkeveréséhez a kártya objektumainak listájában. Ezenkívül hasznos tesztesetek, helyzetek generálásához is.

Keresés

A bináris keresés algoritmus (binarySearch metódus) elemeket keres a rendezett listában. Ennek az algoritmusnak két formája van. Az első vesz egy listát és egy elemet, amit keres (egy kereső kulcsot). Ez a forma feltételezi, hogy a lista elemei rendezve vannak a természetes rendezés szerint a tárolóban. A második forma nem az alapértelmezett rendezést alkalmazza, hanem még egy Comparator paramétert is vár.

A visszatérési érték azonos mindkét formában. Ha a lista tartalmazza keresett elemet, visszatér az indexével. Ha nem, a visszatérési érték negatív, és egyben utal arra is, hogy hol kellene lennie az elemnek, ha szerepelne a listában.

A következő példa keresi egy adott elem meglétét, és beilleszti a helyére, ha még nem szerepel:

int pos = Collections.binarySearch(list, key);
    if (pos < 0)
       l.add(-pos-1);

21.4. Ellenőrző kérdések

  • Mik a gyűjtemények?
  • Milyen részei vannak a gyűjtemény keretrendszernek? Mire szolgálnak?
  • Írjon példát olyan gyűjtemény interfészre, amely engedélyezi a többszörös tárolást!
  • Írjon példát olyan gyűjtemény interfészre, amely nem engedélyezi a többszörös tárolást!
  • Mi a Set interfész specialitása más gyűjteményekhez képest?
  • Mi a List interfész specialitása más gyűjteményekhez képest?
  • Mi a Map interfész specialitása más gyűjteményekhez képest?
  • Mi az iterátor? Mire használhatjuk? Hogyan jön létre?

Igaz vagy hamis? Indokolja!

  • A Set elemei indexelhetők.
  • Egy Iterator objektum segítségével a kollekció elemei többször is bejárhatók.
  • A Comparator segítségével egy TreeSet rendezettsége kívülről is megadható.
  • A Set implementációi minden esetben rendezettek.
  • A TreeSet osztály implementálja a Set interfészt.
  • Minden kollekció implementálja az Iterator interfészt.
  • A kollekcióban lehet primitív adatokat is tárolni.

Melyik interfészt érdemes alkalmazni?

Olyan tároló objektumra van szükségünk, amelyikbe egyedi elemeket akarunk tárolni. A sorrend nem lényeges, de a többszörös tárolás semmiképpen sem megengedett.

  • Set
  • List
  • Map

Mit tesz egy Set objektum annak érdekében, hogy ne legyenek duplikált elemei?

  • Az add metódus kivételt dob, ha duplikált elemet akarunk beszúrni.
  • Az add metódus false értéket ad vissza, ha duplikált elemet akarunk beszúrni.
  • A duplikált értékeket a fordító kiszűri.