Jelenlegi hely

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.