Java Collection API

Kategória: Java standard könyvtárak.

Áttekintés

Szinte minden programban szükség van adatok memóriában történő tárolására. Erre a tömb elvileg alkalmas, viszont nagyon gyakran ki kell egészíteni ugyanazokkal a műveletekkel: kiolvasás, beszúrás, törlés, annak biztosítása, hogy adott esetben csak egyszer fordulhasson elő egy elem, mindig sorba legyen rendezve stb. Mindezt feladatra szabott hatékonysággal. Ezeket tömbökkel megvalósítani nem lehetetlen, de a leprogramozása nagyon sok időt elvesz, a probléma pedig kellően elterjedt ahhoz, hogy számos programozási nyelvben általános megoldások születtek rá. A Java programozási nyelvben ez a Java Collections Framework, melyet magyarra kb. így lehetne fordítani: Java gyűjtemény keretrendszer. Az alábbi ábra ebben a keretrendszerben található interfészeket és osztályokat tartalmazza:

collections.jpg

Lássuk a lényegesebb részeket részletesebben! A Collection egy interfész, ami olyan alapfüggvényeket deklarál, mint pl. egy elem beszúrása vagy törlése, elem keresése, a pillanatnyi elemszám, az elemeken való végigiterálás stb., tehát amelyek mindegyik adatszerkezet esetén előfordulnak. Ebből 3 további interfész származik, ill. van egy negyedik is, ami más eljárásokat tartalmaz:

  • Set (halmaz): egy elem egyszer fordulhat elő, és alapértelmezésben a sorrend nem garantált. Van azonban egy ebből származó interfész, a SortedSet, amelyben az elemek rendezve vannak. Konkrét megvalósítások:
    • HashSet: hasító tábla alapú megvalósítás.
    • LinkedHashSet: megjegyzi a beszúrás sorrendjét, és garantált a bejárási sorrend.
    • TreeSet: bináris keresőfa, ami mindig rendezve van.
  • List (lista): egy elem akárhányszor előfordulhat, és a sorrend adott (de nem feltétlenül rendezett). Konkrét megvalósítások:
    • ArrayList: tömbös megvalósítás. Ha nincs jó okunk mást használni, akkor érdemes ezt választani.
    • Vector: olyan mint az ArrayList, az eljárásai viszont ennek szinkronizáltak, aminek akkor van jelentősége, ha több programszál is használhatja (a többszálúságot ld. a megfelelő fejezetben). A neve kissé félrevezető, mert lényegében semmi köze sincs a matematikai értelembe vett vektorhoz.
    • LinkedList: láncolt lista, melyben beszúrás a végére ill. kiolvasás onnan gyors, az általános címzés lassú.
  • Queue (verem): ez egy olyan adatszerkezet, amelyben az elején vagy a végén lehet csak műveleteket végrehajtani: beszúrás, olvasás, törlés. Kétféle megvalósítás van:
    • LinkedList: ez egyben lista is, ld. fenn.
    • PriorityQueue: ahogy a neve is tartalmazza, egy prioritási sorba helyezi az elemeket, pl. a legnagyobb kerül legelőre, azaz a beszúrás sorrendje nem marad meg.
  • Map (asszociatív tömb): ez kulcs-érték párokat tartalmaz, egy kulcsnak egy értéke lehet. Tehát ha egy olyan kulcsnak adunk értéket, aminek már volt, akkor az felülíródik. Megvalósítások:
    • HashMap: véletlen sorrend.
    • LinkedHashMap: megőrzi a sorrendet.
    • TreeMap: kulcs szerint sorba rendez.
    • Hashtable: szinkronizált függvények.

A Java gyűjtemény keretrendszer generikus típusokat tartalmaz. Pl. egy Stringekből álló listát a következőképpen tudunk létrehozni: List<String> myList = new ArrayList<String>();. A használt osztályok a java.util csomagban találhatóak, amelyek nem importálódnak automatikusan, így a fenti példában a fejlécbe az alábbi sorokat is be kell szúrni: import java.util.List; és import java.util.ArrayList;.

Van még két osztály statikus metódusokkal: Arrays és Collections. Ezek statikus metódusokat tartalmaznak, amelyekkel különböző műveleteket tudunk végrehajtani a tömbökön ill. gyűjtemény osztályokon, pl. a Collections.sort() függvény helyben lerendezi a paraméterül átadott Collection-t. (Ld. az s karaktert az osztálynév végén; a Collection egy interfész, amelyből a Set, a List és a Queue származik, a Collections pedig egy, nagyrészt statikus eljárásokat tartalmazó osztály. Ebből az apró eltérésből gyakran adódik félreértés.)

A fentiekben használtunk olyan fogalmakat, hogy sorrend meg rendezett. Nézzük meg az alábbi két angol szót, melyeknek a magyar nyelvű jelentése az, hogy rendezett, de két különböző dolgot jelent:

  • Ordered: ez azt jelenti, hogy adott a sorrend, pl. a beszúrás sorrendje, tehát ha végiglépkedünk a struktúra elemein, akkor ugyanabban a sorrendben történik a bejárás, ahogy a beszúrás történt. Ennek ellenkezője az, amikor a sorrend nem garantált. Vonatkozó fogalom még az, hogy egy rendezés (erről később lesz szó) megtartja-e a sorrendet az egyenlő elemek között. Tegyük fel, hogy van egy osztály, aminek van olyan mezője, amely nem játszik szerepet az összehasonlításnál, azaz ha két objektum csak abban a mezőben tér el egymástól, akkor egyenlőnek tekinthető. Így megkülönböztethető a két osztály. Itt arról van szó, hogy egy rendezés garantálja-e e két elem eredeti sorrendjét vagy nem. Vegyünk egy példát, ahol ennek jelentősége van! Először lerendezzük a fájlokat dátum szerint, majd kiterjesztés szerint. Ha sorrend tartó rendezést használunk, akkor kiterjesztés szerint, azon beül dátum szerint lesznek rendezve a fájlok. Ha a rendezés nem sorrend tartó, akkor a végső rendezés kiterjesztés szerinti lesz, azon belül viszont össze-vissza.
  • Sorted: ez azt jelenti, hogy az elemek nagyság szerint sorba vannak rendezve, így amikor végiglépkedünk rajta, akkor egy adott rendezési elv szerint először a legkisebbet kapjuk, majd a másodikat, és így tovább. Az egyszerű típusoknál létezik természetes sorrend: pl. számok esetén adott, String esetén az alapértelmezett rendezés a lexikografikus. Azonban az olyan osztályok esetén, ahol több mező van, már nincs természetes sorrend, ott meg kell adni, hogy mi alapján szeretnénk a rendezést végrehajtani. Ezt a Comparable (generikus) interfész megvalósításával tudjuk megadni. Az interfész egy függvényt definiál: compareTo(other), melynek egy paramétere van, a másik elem, amivel az összehasonlítást végezzük. Úgy kell megvalósítani, hogy a visszatérési érték pozitív (általában 1) legyen, ha az adott objektum nagyobbnak számít a paraméterül átadottnál, negatív (általában -1), ha alacsonyabbnak, és 0, ha egyenlőnek.

Lássunk példákat!

Egy egyszerű halmaz

Az alábbi példában létrehozzuk a gyümölcsök halmazát!

import java.util.HashSet;
import java.util.Set;
 
public class Main {
    public static void main(String[] args) {
        Set<String> fruits = new HashSet<String>();
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("peach");
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("apple");
        fruits.add("cherry");
        for (String fruit : fruits) {
            System.out.println(fruit);
        }
    }
}

Figyeljük meg az alábbiakat!

  • A forrás két import utasítással kezdődik.
  • A változó típusának megadásakor egy interfészt adtunk meg (Set). Ez egy jó programozási gyakorlat.
  • A típus után csúcsos zárójelben következik a típus (String).
  • A konkrét típus nem lehet Set, hanem egy adott implementációt kell választanunk. A példában ez a HashSet.
  • A HashSet után csúcsos zárójelben ismét szerepel a típus. Ennek megadása a Java gyűjtemény keretrendszer megalkotásakor kötelező volt, később opcionális lett.
  • A kiírási sorrend nálam a következő: banana, apple, cherry, peach. Látható, hogy mindegyik elem csak egyszer fordul elő, és a sorrend eléggé össze-vissza van: sem a beszúrás sorrendje, sem más egy egyértelmű sorrend (pl. lexikografikus sorrend, a szavak hossza stb.) nem felfedezhető. Ez a halmazműveletek sajátja.

Sorba rendezett halmaz

A fenti példában cseréljük ki a HashSet-et erre: TreeSet (az import utasításban és a példányosításnál is). A kiírási sorrend lexikografikus lesz: apple. banana, cherry, peach. (A TreeSet valójában egy ún. piros-fekete fa.)

Egy egyszerű lista

Listák esetén a beszúrási sorrend garantált, közvetlenül tudunk címezni lekérdezéskor és beszúráskor is (emlékeztetőül: a sorszámozás 0-ról indul), és sorba is tudjuk rendezni. Lássuk az alábbi példát!

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public class Main {
    public static void main(String[] args) {
        List<String> fruits = new ArrayList<String>();
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("peach");
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("apple");
        fruits.add("cherry");
        System.out.println("fruits[2] = " + fruits.get(2));
        fruits.set(1, "grape");
 
        for (String fruit : fruits) {
            System.out.println(fruit);
        }
 
        Collections.sort(fruits);
        System.out.println("Sorted:");
        for (String fruit : fruits) {
            System.out.println(fruit);
        }
    }
}

A struktúra feltöltését követően kiírjuk a tömb második (valójában harmadik, mivel a sorszámozás 0-ról indul) elemét, ami a peach. Utána az első (valójában második) elem értékét erre állítjuk: grape (eredetileg banana volt). Az ezt követő kiíráskor már a grape jelenik meg a banana helyett, egyébként azt tapasztaljuk, hogy mindegyik elem benne maradt (így pl. az apple háromszor), és az eredeti sorrendben történik a kiírás. A listát sorba is tudjuk rendezni, amit az utolsó pár sor illusztrál.

Egy összetett lista példa

Most lássunk egy olyan példát, amelyben egy magunk által létrehozott struktúra példányait helyezzük egy listába, majd lerendezzük:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public class MyStructure implements Comparable<MyStructure> {
    private int number;
    private String name;
    private String remark;
 
    public MyStructure(int number, String name, String remark) {
        this.number = number;
        this.name = name;
        this.remark = remark;
    }
 
    @Override
    public String toString() {
        return "MyStructure [number=" + number + ", name=" + name + ", remark=" + remark + "]";
    }
 
    public int compareTo(MyStructure other) {
        if (number > other.number) {
            return 1;
        } else if (number < other.number) {
            return -1;
        } else {
            return name.compareTo(other.name);
        }
    }
 
    public static void main(String[] args) {
        List<MyStructure> myList = new ArrayList<MyStructure>();
        myList.add(new MyStructure(2, "apple", "remark1"));
        myList.add(new MyStructure(1, "banana", "remark2"));
        myList.add(new MyStructure(2, "apple", "remark3"));
        myList.add(new MyStructure(2, "banana", "remark4"));
        myList.add(new MyStructure(1, "apple", "remark5"));
        Collections.sort(myList);
        for (MyStructure element: myList) {
            System.out.println(element);
        }
    }
}

Ha lefuttatjuk, az eredmény az alábbi:

MyStructure [number=1, name=apple, remark=remark5]
MyStructure [number=1, name=banana, remark=remark2]
MyStructure [number=2, name=apple, remark=remark1]
MyStructure [number=2, name=apple, remark=remark3]
MyStructure [number=2, name=banana, remark=remark4]

Ez egy kicsit hosszabb és összetettebb példa a szokásosnál; lássuk részletesebben! Az osztály 3 attribútumot tartalmaz: egy számot és két stringet. A konstruktora beállítja mindhárom értéket. A valóságban legalább lekérdező függvényeket meg szoktunk valósítani, most az egyszerűség érdekében ettől eltekintünk. Az osztály felüldefiniálja a toString() metódust, amit a java.lang.Object deklarál, ennek segítségével fogjuk majd kiírni. A compareTo() függvény először a számot hasonlítja össze, egyenlőség esetén az első stringet (name), és ha az is egyenlő, akkor egyenlőnek tekinti a két objektumot, a második string (remark) nem játszik szerepet az összehasonlításban. Végül a főprogramban létrehoz egy MyStructure típusú elemeket tartalmazó listát, behelyez 5 elemet, melyek közül kettő logikailag egyenlő, és lerendezi azokat. A rendezés megtartja az eredeti sorrendet. AZ eredmény azt, amit vártunk: először szám szerint rendez, utána lexikografikusan.

Asszociatív tömb

Amint arról szó volt, az asszociatív tömb kulcs-érték párokat tartalmaz. Lássunk egy példát!

import java.util.HashMap;
import java.util.Map;
 
public class HashMapExample {
 
    public static void main(String[] args) {
        Map<String, Integer> myMap = new HashMap<String, Integer>();
        myMap.put("apple", 4);
        myMap.put("banana", 3);
        myMap.put("peach", 4);
        myMap.put("banana", 5);
        myMap.put("cherry", 2);
        System.out.println(myMap.get("banana"));
    }
 
}

Ha egy kulcsnak már van értéke, akkor az felülíródik. Így a fenti program eredménye 5 lesz.

equals() és hashCode()

A java.lang.Object deklarál két olyan függvényt, melyek ugyan függetlenek a Java gyűjtemény keretrendszertől, viszont igazi jelentőségüket itt kapják; ezek az equals() és a hashCode().

A boolean equals(Object obj) függvényt úgy kell megvalósítani, hogy a visszatérési értéke igaz (true) legyen, ha a paraméterül kapott objektum logikailag megegyezik az adott objektummal, és hamis (false) különben. A jelentőségének megértéséhez a következőket vegyük figyelembe:

  • Az alapértelmezett megvalósítás olyan, hogy a két objektum memóriacímét hasonlítja össze. Lehet, hogy a két objektum összes mezője megegyezik, viszont az egyenlőség vizsgálat hamis értékkel tér vissza.
  • Az előző állításban nem véletlen a bizonytalanság. Ugyanis a Java virtuális gép fel van készítve olyan memóriaoptimalizálásra, hogy ha egy nem megváltoztatható osztályból olyan példányt hozunk létre, ami már létezik, akkor nem foglal le újabb memóriaterületet, hanem a már létezőre állítja a hivatkozást. Ez különösen gyakori a Stringek esetén. Így egy ugyanolyan tartalmú, de külön létrehozott két osztálypéldány összehasonlításának az eredménye nem definiált.
  • A leggyakoribb megvalósítás olyan, hogy sorba veszi az az attribútumokat, és ha mindegyik megegyezik, akkor igazzal tér vissza, ha nem, akkor hamissal. Jogosan vetődik fel a kérdés, hogy miért nem ez az alapértelmezett megvalósítás; A Scalaban például az alapértelmezett megvalósítás nem a memóriacímeket, hanem a tartalmakat hasonlítja össze. Pár dolgot azonban érdemes figyelembe venni a megvalósításnál.
    • Objektumok összehasonlítása során nem az ==-t használjuk, hanem az equals()-t, különben ugyanazzal a problémával szembesülünk, mint az eredeti esetben: tartalom helyet cím összehasonlítás. Persze lehet, hogy arra vagyunk kíváncsiak, hogy fizikailag ugyanarra a memóriacímre mutat-e a két hivatkozás.
    • Gyűjtemények összehasonlítása esetén figyeljünk arra, hogy hogyan szeretnénk végrehajtani az összehasonlítást: ugyanarra a memóriaterületre hivatkozik-e a két referencia, ugyanazokat az elemeket tartalmazza-e; ha a sorrend is számít, akkor ugyanabban a sorrendben vannak-e; számít-e a típus (pl. egyenlőnek számít-e egy ArrayList és egy Vector, ha egyébként ugyanazokat az elemeket tartalmazzák, ugyanabban a sorrendben).
    • Elképzelhető, hogy az összehasonlítás során nem szeretnénk minden mezőt felhasználni. Például elképzelhető, hogy az osztály tartalmaz egy megjegyzés mezőt, és ha az osztály két példánya csak ebben tér el egymástól, akkor azt egyenlőnek tekintjük. Ez is figyelembe kell venni a megvalósításnál.

Az int hashCode() függvény (hasító függvény) jelentőségét a hasító táblák megismerésével érthetjük meg, ld. az Algoritmusok és adatszerkezetek oldal megfelelő részét. Röviden összefoglalva: képzeljünk el sorszámozott vödröket. Ez a függvény valójában azt a számot adja vissza, hogy ha az adott objektumot bele kellene tenni valamelyik vödörbe, akkor melyikbe kerüljön. Ennek akkor van jelentősége, hogy ha meg szeretnénk keresni, akkor melyik vödörben keressük. A vödörben viszont nincs rend, így érdemes olyan sok vödröt felállítani, hogy egy vödörbe várhatóan ne kerüljön túl sok elem. Abszolút ideális esetben pont annyi vödör van, ahány elemszám, és mindegyik külön vödörbe kerül. Ezt elérni lényegében lehetetlen, törekedni viszont lehet rá. A leggyakoribb hiba az az, hogy sok elem ugyanazt a vödröt jelöli meg, és sok vödör üresen marad.

A számmal kapcsolatban egyetlen megkötés van csak: a logikailag egyenlőnek tekintett objektumoknak ugyanaz legyen. Elméletben az is helyes, ha mindegyik objektum ugyanazt a számot adja vissza; ez esetben mindegyik ugyanabba a vödörbe kerül, és egy idő után nehéz lesz bármit megtalálni. Ráadásul a jó hasító függvény igyekszik a hasonló értékű objektumoknak jelentősen eltérő értéket adni.

A jó hashCode() függvény megértéséhez lássunk egy való életből vett példát: képzeljünk el egy könyvtárat! Tegyük fel, hogy a vödrök itt a polcok, mindegyik egy számmal van betűvel van megjelölve,a polcon belül viszont összevissza vannak a könyvek. Az első ötletünk az, hogy a hasító függvény képződjön a könyv címének első betűjében: 1, ha A, 2 ha Á és így tovább. A probléma az, hogy az 1-es sorszámú polc roskadozni fog a könyvektől, így ott elég nehéz lesz bármit is megtalálni, míg mondjuk a Q betű sorszámát tartalmazó polc kongani fog az ürességtől. Azon túl, hogy célszerű több részre osztani, érdemes a fentinél bonyolultabb megoldást találni, pl. összeadni a könyv címében szereplő összes betű sorszámát, elosztani az összes lehetséges értékek számával, és venni az osztás maradékát. Ebben a példában láthatjuk, hogy miért van jelentősége annak, hogy az egyenlőnek tekintett objektumok miért kapjanak ugyanolyan hasító értéket: pl. ha a könyv ISBN számát is figyelembe vennénk, akkor ugyanannak a könyvnek két külön kiadása külön polcra kerülne.

Lényeges elvárás a hashCode() függvénnyel kapcsolatban az, hogy gyors legyen. Ennek a jelentősége a következő: az equals() sor esetben lassú (tegyük fel, hogy sok attribútumot tartalmaznak az összehasonlítandó objektumok, melyek közül lehet drága is, pl. két lista összehasonlítása), viszont a legtöbb esetben az összehasonlítandó elemek különböznek. Tegyük fel, hogy nagyon sok összehasonlítást kell egymás után végrehajtani (pl. rendezéskor). EZ esetben célszerű előbb a könnyen kiszámolható és könnyen összehasonlítható hashCode() értékeket összehasonlítani, és azok egyezősége esetén végrehajtani csak a éyleges összehasonlítást. (És itt van jelentősége annak, hogy hasonló, de nem egyenlő elemek kapjanak különböző értéket, lehetőleg egymástól távolit.)

Minden olyan adatszerkezetben jelentősége van a hasító függvénynek, melyben szerepel a Hash előtag (HashMap, Hashtable, HashSet, …). Az egyenlőségvizsgálattal kapocslatos megkötés miatt többnyire együtt szoktuk megvalósítani e két függvényt. Ha a már említett Comparable interfészt is megvalósítjuk, akkor érdemes ezt a kettőt is megvalósítani, legalább amiatt, hogy a compareTo() és az equals() konzisztens legyen.

Lássunk egy példát!

import java.util.HashSet;
import java.util.Set;
 
public class MyStructure {
    private int number;
    private String name;
    private String remark;
 
    public MyStructure(int number, String name, String remark) {
        this.number = number;
        this.name = name;
        this.remark = remark;
    }
 
    @Override
    public String toString() {
        return "MyStructure [number=" + number + ", name=" + name + ", remark=" + remark + "]";
    }
 
    @Override
    public int hashCode() {
        System.out.println("hashCode() called");
        final int prime = 31;
        int result = 1;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        result = prime * result + number;
        return result;
    }
 
    @Override
    public boolean equals(Object obj) {
        System.out.println("equals() called for " + this + " and " + obj);
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        MyStructure other = (MyStructure) obj;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        if (number != other.number)
            return false;
        return true;
    }
 
    public static void main(String[] args) {
        Set<MyStructure> mySet = new HashSet<MyStructure>();
        mySet.add(new MyStructure(2, "apple", "remark1"));
        mySet.add(new MyStructure(1, "banana", "remark2"));
        mySet.add(new MyStructure(2, "apple", "remark3"));
        mySet.add(new MyStructure(2, "banana", "remark4"));
        mySet.add(new MyStructure(1, "apple", "remark5"));
        for (MyStructure element: mySet) {
            System.out.println(element);
        }
    }
}

A példa sok mindenben megegyezik a fentivel, van viszont pár eltérés:

  • Nem listát, hanem nem sorba rendezhető halmazt hozunk létre, így nincs jelentősége a Comparable interfész megvalósításának. Nincs nagy jelentősége, de az egyszerűség érdekében kivettem.
  • A halmaz konkrét megvalósulása a HashSet, így jelentősége van a hashCode() függvénynek.
  • Az equals() és a hashCode() csak a number és a name értékét veszi figyelembe, a remark-ot nem. Ilyen értelemben kompatibilis az eredeti, compareTo() függvényt is tartalmazó megvalósítással.
  • E két függvényt valójában az Eclipse-ben található Source → Generate hashCode() and equals()… segítéségével hoztam létre. AZ első, kiíró sorokat kézzel adtam hozzá.
  • A futás eredménye az alábbi. Ebből látszik, hogy a hashCode() és az equals() függvény is meghívódott, és az eredményből hiányzik a remark3, mert az logikailag egegyezik a remark1-gyel.
hashCode() called
hashCode() called
hashCode() called
equals() called for MyStructure [number=2, name=apple, remark=remark3] and MyStructure [number=2, name=apple, remark=remark1]
hashCode() called
hashCode() called
MyStructure [number=1, name=banana, remark=remark2]
MyStructure [number=2, name=banana, remark=remark4]
MyStructure [number=1, name=apple, remark=remark5]
MyStructure [number=2, name=apple, remark=remark1]

Műveletek az adatszerkezeteken

A példákban elemek hozzáadását láttuk, de természetesen számos egyéb műveletet is végre tudunk hajtani az adatstruktúrákon. Érdemes tudni, hogy melyik művelet hol van deklarálva, annak érdekében, hogy tudjuk, mit hol tudunk végrehajtani.

Collection: ezek a műveletek tehát közösek a listák, a halmazok és a sorok esetén. Noha ugyanaz a függvények szignatúrája minden esetben, az egyes műveletek futási ideje jelentősen különbözhet különböző konkrét megvalósulások esetén; ezt mindenképpen figyelembe kell venni, amikor adott adatstruktúra mellett döntünk.

  • add(elem) és addAll(collection): hozzáad egy elemet ill. egy egész gyűjteményt.
  • clear(): törli az elemeket.
  • contains(elem) és containsAll(collection): azt adja vissza, hogy a gyűjtemény tartalmazza-e a paraméterül átadott elemet vagy elemek mindegyikét.
  • boolean isEmpty(): visszaadja, hogy üres-e az adott gyűjtemény.
  • iterator(): egy iterátorral tér vissza, melynek segítségével végig tudunk lépegetni a gyűjtemény elemein, az iterátor boolean hasNext() és next() függvényeinek segítségével.
  • remove(element) és removeAll(collection): törli a paraméterül átadott elemet ill. elemeket.
  • retainAll(collection): a paraméterül átadott gyűjteménnyel való metszetét adja vissza (nincs minden esetben megvalósítva).
  • int size(): a gyűjteményben található elemek számát adja vissza.
  • toArray(): tömbként adja vissza a gyűjtemény elemeit.

A forEach(), a removeIf és a stream() függvények a Java 1.8-as újításaihoz kapcsolódnak, melyekről a megfelelő alfejezetekben lesz szó.

List: a listák setén értelmezhető a sorrend, például mindegyik elemnek van egy egyértelmű indexe (ez pl. halmazok esetén nem így van). A listán értelmezett további függvények:

  • get(index) és set(index, element): lekérdezi ill. beállítja az adott indexű elemet.
  • indexOf(element): visszaadja a paraméterül átadott elem indexét.
  • sort(comparator): a paraméterül átadott összehasonlító segítségével helyben lerendezi a listát.
  • subList(fromIndex, toIndex): a megfelelő allistával tér vissza.

Set: a halmazok esetén nincs olyan művelet, ami ne lenne benne az alap Collection interfészben.

Queue: vannak külön beszúró és kiolvasó műveletek:

  • offer(element): beszúrás
  • peek(): visszaadja, de nem törli az első elemet.
  • poll(): visszaadja és egyúttal törölni az első elemet.

Map: a kulcs-érték párok kezelésével kapocslatos függvények vannak ebben benne. Ez nem származik a Collection-ből, de tartalmazza az alábbiakat: clear(), isEmpty(), size().

  • put(key, value): adott kulcs-érték párt helyez az asszociatív tömbbe.
  • get(key): visszatér az adott kulcshoz tartozó értékkel.
  • keySet(): visszaadja az összes kulcsot.
  • values(): visszaadja az összes értéket.
  • containsKey(key) és containsValue(value): megmondja, hogy az adott kulcs vagy érték benne van-e az asszociatív tömbben.

A fenti függvényeknek vannak egyéb formái is, ill. más egyéb függvények, melyek bizonyos esetekben hasznosak lehetnek.

Algoritmusok

Az adatszerkezetek és az algoritmusok kéz a kézben járnak. Amint arról már szó volt, létezik egy java.util.Collections nevű osztály (ami - ismétlem - nem összetévesztendő a java.util.Collection interfésszel), ami a leggyakoribb algoritmusok megvalósításait tartalmazza. Lássunk pár példát:

  • Collections.sort(collection): helyben sorba rendezi a paraméterül átadott collection gyűjteményt. A rendezés sorrend tartó, azaz az egyenlő elemek ugyanabban a sorrendben maradnak, amilyenben voltak eredetileg. Erre már láttunk példát a gyümölcsök sorba rendezésénél.
  • Collections.binarySearch(list, element): megkeresi az element elemet a list listában. A paraméternek tehát itt listának kell lennie, ráadásul rendezettnek. A keresés az adatszerkezetekben egy igen gyakori művelet. Egy nyilvánvaló megvalósítása az, hogy végiglépkedünk az elemeken, és mindegyiknél elvégezzük az összehasonlítást, hogy az-e a keresett elem. Ez jól működik akkor, ha nincs túl sok elem az adatszerkezetben, de sok elem esetén már problémás, különösen akkor, ha gyakran végre kell hajtani. Ha rendezve vannak az elemek, akkor van egy gyors módszer: megnézzük, hogy a felénél kisebb vagy nagyobb, a megfelelő felét ismét elfelezzük, és így tovább. Ezer elemnél 10, egymillió elemnél 20, egymilliárd elemnél 30 összehasonlítást kell elvégezni. A megvalósítás tehát nem túl bonyolult, de sok apróságra figyelni kell, pl. a határokra (pl. ha a legnagyobb elemnél is nagyobb értékre keresünk); a binarySearch() függvény pont ezt valósítja meg. És a módszerből jól látható, hogy miért kell rendezettnek lennie. A visszatérési érték a megfelelő elem indexe, ill. ha nincs benne, akkor egy negatív szám, melynek az abszolút értéke az az érték, ahova be kellene szúrni az elemet.
  • boolean Collections.disjoint(collection1, collection2): megállapítja, hogy a paraméterül átadott két gyűjtemény diszjunkt-e, azaz van-e közös elemük (ekkor nem diszjunkt, azaz a visszatérési értéke false).
  • Collections.copy(dest, source): a source listából bemásolja az elemeket a dest listába (felülírva a dest-ben már benne levő megfelelő hosszúságú elemeket).
  • Collections.fill(list, element): a listát feltölti a megadott elemekkel.
  • int Collections frequency(collection, element): a paraméterül átadott element elem előfordulási számát adja vissza a collection gyűjteményben.
  • int Collections.indexOfSublist(source, target) és int Collections.lastIndexOfSublist(source, target): a source listában megkeresi a target allistát, és annak az első ill. utolsó előfordulását adja vissza. Ezt tehát pl. szókeresésre lehet használni, ha a lista elemei betűk.
  • Collections.max(collection) és Collections.min(collection): a gyűjtemény legnagyobb ill. legkisebb értékét adja vissza. A gyűjtemény elemeinek értelemszerűen összehasonlíthatónak kell lenniük, vagy az összehasonlítót paraméterül át kell adni.
  • Collections.replaceAll(list, oldValue, newValue): a listában kicseréli az összes oldaValue elemet newValue-ra.
  • Collections.reverse(list): megfordítja a paraméterül átadott lista sorrendjét.
  • Collections.rotate(list, distance): körbe forgatja a lista elemeit distance lépéssel.
  • Collections.suffle(list): véletlenszerűen összekeveri a lista elemeit.

Még számos egyéb függvény definiált, így mielőtt megvalósítunk egy algoritmust, érdemes megnézni, hogy az meg van-e már valósítva.

Az Arrays a Collections-höz hasonló függvényeket tartalmaz, a paraméter viszont nem valamilyen Collection, hanem tömb.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License