Algoritmai ir duomenų struktūros

Aibė (angl. set) yra struktūrinis duomenų tipas, naudojamas laikyti unikalius elementus be pasikartojimų ir be konkrečios įterpimo tvarkos (išskyrus tam tikrus įgyvendinimus). Aibė dažnai naudojama situacijose, kai svarbu išsaugoti unikalius duomenis ir nereikia rūpintis jų tvarka.

Java kalboje Set yra sąsaja (interface), kuri priklauso Java kolekcijų karkasui (angl. Java Collections Framework) ir paveldi Collection sąsają. Set sąsaja nurodo, kad visi elementai turi būti unikalūs ir kad du identiški elementai negali egzistuoti vienoje aibėje.

1. Pagrindinės Set sąsajos savybės

Java Set sąsaja turi kelias svarbias savybes:

• Unikalūs elementai: Aibė leidžia saugoti tik unikalius elementus. Jei bandysime pridėti dublikatą, jis bus ignoruojamas.
• Tvarkos nebuvimas: Dauguma Set įgyvendinimų nesiūlo specifinės elementų tvarkos, todėl negalime numatyti, kokia tvarka elementai bus laikomi. Tačiau kai kurie įgyvendinimai, pvz., LinkedHashSet, išlaiko įterpimo tvarką, o TreeSet – natūralią elementų tvarką.
• Nėra tiesioginės prieigos pagal indeksą: Skirtingai nuo List, Set neturi elementų indeksų, todėl elementai negali būti pasiekiami pagal konkrečią poziciją.

2. Set sąsajos pagrindiniai metodai

Set sąsaja turi kelis pagrindinius metodus, kurie leidžia atlikti dažniausias aibės operacijas:

• add(E e): Prideda elementą į aibę. Jei elementas jau yra aibėje, jis nepridedamas.
• remove(Object o): Pašalina nurodytą elementą iš aibės.
• contains(Object o): Patikrina, ar aibė turi tam tikrą elementą.
• size(): Grąžina aibės elementų skaičių.
• isEmpty(): Patikrina, ar aibė yra tuščias.
• clear(): Pašalina visus elementus iš aibės.
• iterator(): Grąžina Iterator objektą, leidžiantį pereiti per visus aibės elementus.

3. Aibės įgyvendinimai Java kalboje

Java kalboje Set sąsają gali įgyvendinti kelios pagrindinės klasės: HashSet, LinkedHashSet ir TreeSet. Kiekviena iš jų turi unikalių savybių ir pritaikymų.

a) HashSet

HashSet yra dažniausiai naudojamas aibės įgyvendinimas Java kalboje, pagrįstas „hash“ lentele (angl. hash table). Jis nesiūlo jokios specifinės elementų tvarkos, todėl elementai bus saugomi atsitiktine tvarka.

• Privalumai: Greitos add, remove, ir contains operacijos su O(1) laiko sudėtingumu.
• Trūkumai: Nėra tvarkos, todėl negalime numatyti, kokia tvarka elementai bus išdėstyti aibėje.

Pavyzdys:

import java.util.HashSet;
import java.util.Set;

public class HashSetExample {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();

        set.add("Apple");
        set.add("Banana");
        set.add("Cherry");
        set.add("Apple");  // Nepavyks pridėti, nes "Apple" jau yra aibėje

        System.out.println("Aibė: " + set);  // Gali būti atsitiktinė tvarka
        System.out.println("Ar aibė turi 'Banana'? " + set.contains("Banana"));  // true
    }
}

b) LinkedHashSet

LinkedHashSet yra aibė, pagrįsta „hash“ lentele, tačiau išlaikantis elementų įterpimo tvarką. Tai reiškia, kad elementai bus saugomi tokia tvarka, kokia jie buvo pridėti.

• Privalumai: Išlaiko įterpimo tvarką, todėl galime tikėtis, kad elementai bus atspausdinti ta pačia tvarka, kuria jie buvo pridėti.
• Trūkumai: Šiek tiek lėtesnis už HashSet dėl papildomų nuorodų, reikalingų tvarkai išlaikyti.

Pavyzdys:

import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetExample {
    public static void main(String[] args) {
        Set<String> set = new LinkedHashSet<>();

        set.add("Dog");
        set.add("Cat");
        set.add("Bird");

        System.out.println("Aibė: " + set);  // Išlaikys įterpimo tvarką: [Dog, Cat, Bird]
    }
}

c) TreeSet

TreeSet yra aibė, pagrįstas dvejetainiu paieškos medžiu (angl. binary search tree), kuris automatiškai rūšiuoja elementus pagal natūralią tvarką arba nurodytą Comparator.

• Privalumai: Išlaiko elementus surūšiuotus. Puikiai tinka, kai reikia rūšiuotos aibės.
• Trūkumai: Lėtesnis nei HashSet, nes add, remove, ir contains operacijos užima O(log n) laiko.

Pavyzdys:

import java.util.Set;
import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        Set<String> set = new TreeSet<>();

        set.add("Peach");
        set.add("Apple");
        set.add("Orange");

        System.out.println("Rūšiuotas aibė: " + set);  // Elementai bus surūšiuoti: [Apple, Orange, Peach]
    }
}

4. Aibės panaudojimo atvejai

Aibė yra naudinga duomenų struktūra įvairiose situacijose, kai reikia išlaikyti unikalius duomenis arba greitai patikrinti, ar tam tikras elementas jau yra aibėje. Štai keletas naudojimo atvejų:

• Unikalių reikšmių saugojimas: Aibė puikiai tinka saugoti unikalius elementus, pavyzdžiui, vartotojų ID, kurie neturi kartotis.
• Duomenų filtravimas: Jei reikia pašalinti dublikatus iš didelio duomenų rinkinio, aibė padeda greitai gauti tik unikalius elementus.
• Paieškos optimizavimas: HashSet leidžia greitai patikrinti, ar elementas egzistuoja aibėje, todėl gali būti naudojamas optimizuoti algoritmus, kuriems reikia efektyviai vykdyti paieškas.
• Matematinės operacijos su aibėmis: Kai reikia atlikti aibės operacijas, pvz., sąjungą, sankirtą arba atimtį, Java Set struktūra tam puikiai tinka.

5. Aibės privalumai ir trūkumai Java kalboje

Privalumai:

• Unikalumas: Aibė užtikrina, kad visi elementai yra unikalūs, todėl nereikia rūpintis dėl dublikatų.
• Greita paieška: HashSet leidžia greitai atlikti contains, add ir remove operacijas su O(1) laiko sudėtingumu.
• Lankstūs įgyvendinimai: Java suteikia kelis skirtingus aibės įgyvendinimus (HashSet, LinkedHashSet, TreeSet), kurie siūlo pasirinkimą tarp našumo ir tvarkos.

Trūkumai:

• Nėra tiesioginės prieigos: Skirtingai nei sąraše (List), aibėje elementai neturi indeksų, todėl negalime prieiti prie konkrečios pozicijos.
• Tvarkos nebuvimas: HashSet nesiūlo jokių tvarkos garantijų, todėl negalime numatyti, kokia tvarka elementai bus išdėstyti.
• Lėtesnis už List kai kuriose operacijose: Jei reikia tvarkingo duomenų rinkinio ir dažnai pasiekti elementus pagal poziciją, tuomet aibė nėra tinkamas pasirinkimas, nes prieiga gali būti sudėtingesnė.

6. Kodas su pagrindinių Set metodų pavyzdžiais

Štai pavyzdys, kaip naudoti pagrindinius aibės metodus Java kalboje:

import java.util.HashSet;
import java.util.Set;

public class SetExample {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();

        // Pridėti elementus
        set.add("Apple");
        set.add("Banana");
        set.add("Cherry");
        set.add("Apple");  // Nepavyks pridėti "Apple" antrą kartą, nes jis jau yra aibėje

        // Patikrinti, ar aibė turi tam tikrą elementą
        boolean hasBanana = set.contains("Banana");
        System.out.println("Ar aibė turi 'Banana'? " + hasBanana);  // true

        // Pašalinti elementą
        set.remove("Cherry");

        // Aibės dydis
        System.out.println("Aibės dydis: " + set.size());  // 2

        // Iteracija per aibės elementus
        System.out.println("Aibės elementai: ");
        for (String element : set) {
            System.out.println(element);
        }
    }
}