Gyakorlati alapok III.
Halmaz (Set)
Ismételjük meg az
előző fejezet legfontosabb megállapításait:
a Set fő jellegzetessége, hogy nem tartalmazhat duplikált-többszörös elemeket. 2 db Set akkor egyenlő, ha ugyanazon elemeket tartalmazzák.
Valós életből vett példák: bármilyen általánosabb megközelítésű katalógus,
például állat-, és növényfajok, autómárkák, országnevek, megyenevek,
fegyvernemek, stb. adatbázisa.
Eleddig kellő mennyiségű kód került bemutatásra ahhoz, hogy végre konkrét
kollekció-implementálással próbálkozzunk, így rögtön csapjunk is bele a
kódlecsóba (micsoda képzavar)!
A legelső, egyúttal talán legizgalmasabb a Set azon tulajdonságának
vizsgálata, miszerint nem tartalmazhat duplikált-többszörös elemeket, először
tehát ezt ellenőrizzük le. Egy egyszerű, a Set interfészből
továbbspecializált HashSet típusú halmazt hozunk létre és megpróbáljuk
kétszer beletenni a 4 sztringet:
import java.util.*;
public class Main {
public static void main(String[] args) {
Set<String> halmaz = new HashSet<String>();
halmaz.add("2");
halmaz.add("1");
halmaz.add("5");
halmaz.add("4");
halmaz.add("4");
halmaz.add("3");
System.out.println(halmaz);
}
}
Végeredmény:
[1, 2, 3, 4, 5]
Próbálkozásunk nem sikerült, a halmaz az elemeket garantáltan csakis
egyszeresen fogja tartalmazni. Egyúttal vegyük észre, milyen egyszerűen
tudtuk kinyomtatni a konzolra a halmaz tartalmát, valamint a Java-rendszer
valamilyen rendezőelv szerint rögtön rendezte is. Azt gondolnánk, hogy ez szám
szerinti növekvő sor, ami csak látszólag igaz, mert bár itt a belső,
String-rendezési
elv és a szám szerinti növekvés speciel megegyezik, de valójában nem azonosak.
Ennek bizonyítására kissé át kell alakítanunk a kódot:
import java.util.*;
public class Main {
public static void main(String[] args) {
Set<String> halmaz = new HashSet<String>();
halmaz.add("23");
halmaz.add("110");
halmaz.add("555");
halmaz.add("40");
halmaz.add("40");
halmaz.add("3456");
System.out.println(halmaz);
}
}
Végeredmény:
[110, 23, 555, 3456, 40]
Itt már láthatóan nincs növekvő számsor. Ebből és más tapasztalatokból
levonhatunk általánosabb következtetéseket is:
a HashSet az elemeket alapértelmezésben rendezetlenül, egy
hash-táblában tárolja. Ez a leggyorsabb elemhozzáférést biztosítja, ha a
kollekció bejárása nem fontos.
A Set következő specializációja, a TreeSet az elemeket egy
bináris fában (nevezik piros-fekete fának is)...
...tárolja és ez bár az előzőnél rendezettebb szerkezetet jelent, mégsem oldja fel a fenti rendezési problémát:
import java.util.*;
public class Main {
public static void main(String[] args) {
Set<String> halmaz = new TreeSet<String>();
halmaz.add("23");
halmaz.add("110");
halmaz.add("555");
halmaz.add("40");
halmaz.add("40");
halmaz.add("3456");
System.out.println(halmaz);
}
}
Végeredmény:
[110, 23, 3456, 40, 555]
Természetesen hiába erőltetünk
String típusú elemeken számokhoz köthető
rendezési szempontokat, ehhez nyilvánvalóan számokká kell alakítanunk az
elemtípust (itt Integer, amely típus ráadásul objektumtípus is). Egyúttal a
40
esetében megint csak megpróbálkozunk a duplikált elemtartalommal:
import java.util.*;
public class Main {
public static void main(String[] args) {
Set<Integer> halmaz = new TreeSet<Integer>();
halmaz.add(23);
halmaz.add(110);
halmaz.add(555);
halmaz.add(40);
halmaz.add(40);
halmaz.add(3456);
System.out.println(halmaz);
}
}
Végeredmény:
[23, 40, 110, 555, 3456]
Az elemduplikálás most sem volt sikeres, ám az elemrendezést a TreeSet
alapértelmezésben biztosította.
A művelet természetesen működik
for-each ciklussal is:
import java.util.*;
public class Main {
public static void main(String[] args) {
Set<Integer> halmaz = new TreeSet<Integer>();
halmaz.add(23);
halmaz.add(110);
halmaz.add(555);
halmaz.add(40);
halmaz.add(40);
halmaz.add(3456);
for(int i : halmaz) {
System.out.print(i + " ");
}
}
}
Végeredmény:
23 40 110 555 3456
Most nézzünk meg néhány további metódust. Például lekérdezzük a Set méretét (size()),
ellenőrizzük, hogy üres-e (isEmpty()), eltávolítjuk az utolsóként betett
elemet (remove(6)), végül töröljük a teljes tartalmát (clear()):
import java.util.*;
public class Main {
public static void main(String[] args) {
Set<Integer> halmaz = new TreeSet<Integer>();
halmaz.add(2);
halmaz.add(1);
halmaz.add(5);
halmaz.add(3);
halmaz.add(4);
halmaz.add(6);
System.out.println("A Set elemei: " + halmaz);
System.out.println("A Set mérete: " + halmaz.size() + " elem");
System.out.println("A Set üres? " + halmaz.isEmpty());
halmaz.remove(5);
System.out.println("A Set elemei az 5. elem eltávolítása után: " + halmaz);
halmaz.clear();
System.out.println("A Set elemeinek törlése után: " + halmaz);
}
}
Végeredmény:
A Set elemei: [1, 2, 3, 4, 5]
A Set mérete: 5 elem
A Set üres? false
A Set elemei az 5. elem eltávolítása után: [1, 2, 3, 4]
A Set elemeinek törlése után: []
Most fogalmazzunk meg egy olyan kódot, amelyik egy bemeneti tömbből
leválogatja az egyszeres és duplikált elemeket (4 és 5). Valósítsuk ezt meg
Set-ek segítségével:
import java.util.*;
public class Main {
public static void main(String args[]) {
String [] bemenetiTomb = new String [] {"1", "2", "3", "4", "4", "5", "5",
"6"};
Set<String> halmazEgyediElemeknek = new HashSet<String>();
Set<String> halmazDuplikaltElemeknek = new HashSet<String>();
for(String elem : bemenetiTomb)
if(!halmazEgyediElemeknek.add(elem))
halmazDuplikaltElemeknek.add(elem);
halmazEgyediElemeknek.removeAll(halmazDuplikaltElemeknek);
System.out.println("Egyedi elemek: " + halmazEgyediElemeknek);
System.out.println("Duplikált elemek: " + halmazDuplikaltElemeknek);
}
}
Végeredmény:
Egyedi elemek: [1, 2, 3, 6]
Duplikált elemek: [4, 5]
Ismétlésképpen gyorsan emlékezzünk vissza a tömeges műveletek definícióira:
-
boolean addAll - halmazelméletben unióképzés – a 2 kollekció egyesítése (hasonlóan a 2 tömb uniója című fejezethez),
-
boolean removeAll - halmazelméletben különbségképzés – a célkollekció minden olyan elemének eltávolítása, amelyet a bemeneti kollekció tartalmazott (hasonlóan a 2 tömb különbsége című fejezethez),
-
boolean containsAll – halmazelméletben részhalmazképzés – a célkollekció tartalmaz minden olyan elemet, amelyet a bemeneti kollekció tartalmazott.
-
boolean retainAll – halmazelméletben metszet, azaz közös rész képzése – a célkollekció és bemeneti kollekció közös elemeit fogja tartalmazni (hasonlóan a 2 tömb metszete című fejezethez).
A Set alapszintű vizsgálatai után érdemes néhány jellemző tömeges műveletet is implementálnunk (bulk operations). Ehhez 2 db Set-re lesz szükségünk, amelyek elemei különbözni fognak, kivéve az utolsó 2 elem esetében (10 és 11). Talán a legtipikusabb példát vesszük erre: a páros-páratlan számok vizsgálatát.
import java.util.*;
public class Main {
public static void main(String[] args) {
Set<Integer> halmazParatlan = new HashSet<Integer>();
halmazParatlan.addAll(Arrays.asList(new Integer[] {1, 3, 5, 7, 9, 10, 11}));
Set<Integer> halmazParos = new HashSet<Integer>();
halmazParos.addAll(Arrays.asList(new Integer[] {2, 4, 6, 8, 10, 11}));
System.out.println("A halmazok külön:" + "\n" + halmazParos + "\n" +
halmazParatlan);
System.out.println();
Set<Integer> halmazUnio = new HashSet<Integer>(halmazParatlan);
halmazUnio.addAll(halmazParos);
System.out.print("A 2 halmaz úniója: " + halmazUnio);
System.out.println();
Set<Integer> halmazKozosResz = new HashSet<Integer>(halmazParatlan);
halmazKozosResz.retainAll(halmazParos);
System.out.print("A 2 halmaz közös része: " + halmazKozosResz);
System.out.println();
Set<Integer> halmazKulonbseg = new HashSet<Integer>(halmazParatlan);
halmazKulonbseg.removeAll(halmazParos);
System.out.print("A 2 halmaz különbsége: " + halmazKulonbseg);
}
}
Végeredmény:
A halmazok külön:
[2, 4, 6, 8, 10, 11]
[1, 3, 5, 7, 9, 10, 11]
A 2 halmaz úniója: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
A 2 halmaz közös része: [10, 11]
A 2 halmaz különbsége: [1, 3, 5, 7, 9]
A példák bemutatása során érdekes dolgot vehettünk észre. Példányosításkor...
Set<Integer> halmazKozosResz = new HashSet<Integer>(halmazParatlan);
...a bal oldali, úgynevezett referenciatípus interfész típusú (Set), míg a jobb oldali, az objektumtípus már konkrét, példányosított osztálytípus (HashSet).
Ezt az eljárást sok helyen alkalmazzák, mert nagyon praktikus, ha a Set
konkrét, implementációs típusát kell megváltoztatni, hiszen ilyenkor csupán át
kell írni a típust ahhoz, hogy az új, kívánt tulajdonságok elérhetővé
váljanak.
Említsük még meg a Set egy további specializációját, neve LinkedHashSet. Ebben
a halmaztípusban az elemek között (rejtett) mutatók tartják fent a
kapcsolatot. Ennek eredménye például, hogy a halmazelemek listázása az
elembevitel sorrendjében történik. Ezt láthatjuk az alábbi futtatható
Java-kódban. Illetve újfent megpróbálkozunk duplikált elembevitellel (halmaz.add(4)),
amely természetesen a Set jellegéből adódóan nem fog sikerülni:
import java.util.*;
public class Main {
public static void main(String[] args) {
Set<Integer> halmaz = new LinkedHashSet<Integer>();
halmaz.add(5);
halmaz.add(1);
halmaz.add(3);
halmaz.add(2);
halmaz.add(4);
halmaz.add(4);
System.out.println(halmaz);
}
}
Végeredmény:
[5, 1, 3, 2, 4]
Utolsó tulajdonságvizsgálatként pedig ellenőrizzük le a fent
említett egyenlőségállításunkat:
2 db Set akkor egyenlő, ha ugyanazon elemeket tartalmazzák.
Ehhez természetesen 2 db halmazt kell használnunk, amelyeket kissé fapados módszerrel, különböző sorrendben és elemredundanciával (4-4 és 5-5), de lényegében azonosan fogunk feltölteni. Ezért az equals() függvény TRUE értéket fog visszaadni:
import java.util.*;
public class Main {
public static void main(String[] args) {
Set<Integer> halmaz1 = new HashSet<Integer>();
halmaz1.add(5);
halmaz1.add(1);
halmaz1.add(3);
halmaz1.add(2);
halmaz1.add(4);
halmaz1.add(4);
System.out.println("1. halmaz: " + halmaz1);
Set<Integer> halmaz2 = new HashSet<Integer>();
halmaz2.add(1);
halmaz2.add(5);
halmaz2.add(5);
halmaz2.add(3);
halmaz2.add(2);
halmaz2.add(4);
System.out.println("2. halmaz: " + halmaz2);
System.out.println("A halmazok egyenlők?");
System.out.println(halmaz1.equals(halmaz2));
}
}
Végeredmény:
1. halmaz: [1, 2, 3, 4, 5]
2. halmaz: [1, 2, 3, 4, 5]
A halmazok egyenlők?
true
Nyilvánvalóan az egyenlőség megbontása esetén a végeredmény már false lesz:
import java.util.*;
public class Main {
public static void main(String[] args) {
Set<Integer> halmaz1 = new HashSet<Integer>();
halmaz1.add(5);
halmaz1.add(1);
halmaz1.add(3);
halmaz1.add(2);
halmaz1.add(4);
halmaz1.add(4);
System.out.println("1. halmaz: " + halmaz1);
Set<Integer> halmaz2 = new HashSet<Integer>();
halmaz2.add(1);
halmaz2.add(6);
halmaz2.add(5);
halmaz2.add(3);
halmaz2.add(2);
halmaz2.add(4);
System.out.println("2. halmaz: " + halmaz2);
System.out.println("A halmazok egyenlők?");
System.out.println(halmaz1.equals(halmaz2));
}
}
Végeredmény:
1. halmaz: [1, 2, 3, 4, 5]
2. halmaz: [1, 2, 3, 4, 5, 6]
A halmazok egyenlők?
false
Most pedig nézzünk meg egy rövid hasznossági összefoglalót a különböző
halmaztípusokról!
Használjunk HashSet-et, ha:
-
ha csakis egyedi elemeket akarunk tárolni,
-
ha az elemsorrend nem fontos,
-
ha az elemek bevitelének sorrendje nem fontos,
-
ha a leggyorsabb elemhozzáférést keressük,
-
a halmazban maximum 1 db null objektumot tárolhatunk.
Használjunk TreeSet-et, ha:
-
ha csakis egyedi elemeket akarunk tárolni,
-
ha az elemsorrend és rendezés fontos lehet,
-
ha az elemek bevitelének sorrendje fontos lehet,
-
ha az elemhozzáférés és rendezések gyorsasága nem fontos,
-
a halmazban nem tárolhatunk null objektumot (NullPointerException).
Használjunk LinkedHashSet-et, ha:
-
ha csakis egyedi elemeket akarunk tárolni,
-
ha az elemsorrend fontos lehet,
-
ha az elemek bevitelének sorrendje kiemelten fontos lehet,
-
ha nem keressük a leggyorsabb elemhozzáférést,
-
a halmazban maximum 1 db null objektumot tárolhatunk.
Pénzes László