Liigu peamise sisu juurde

Set ehk hulk

Sissejuhatus​

Set ehk hulk on kollektsioon elementidest, mis ei sisalda korduvaid elemente. Erinevalt järjenditest, hulgas puudub elementidel kindel järjekord (kuid mõned kindlad implementatsioonid hoiavad sisemiselt järge). Samuti ei ole elemendid hulkades läbipääsetavad läbi indeksite.

Hulkasid kasutatakse peamiselt:

  • Duplikaatide eemaldamiseks kollektsioonidest
  • Duplikaatide leidmiseks
  • Elemendi olemasolu kiireks kontrollimiseks ning selle kaudu ka topelt operatsioonide vältimiseks
  • Hulgatehete läbiviimiseks (union, intersection jne.)

Javas on mitmeid erinevaid hulkade implementatsioone. Enim kasutatavad nendest on Set liidesel põhinevad implementatsioonid HashSet, LinkedHashSet ja TreeSet.

  • HashSet puhul pole elementide järjestus määratud.
  • LinkedHashSet puhul on elemendid järjestatud sisestuse järjekorras.
  • TreeSet puhul on elemendid järjestatud sorteerimisega.

HashSet​

HashSet on kõige enim levinud Set implementatsioon. See salvestab elemente paisktabeli (hash table) abil, mille tõttu on operatsioonid selle hulga implementatsiooniga toimuvad enamus kordadest konstantse ajaga.

HashSet-i loomine​

HashSet-i saab luua järgnevalt:

// Empty set
HashSet<String> names = new HashSet<>();

// Set with initial elements
HashSet<Integer> numbers = new HashSet<>();
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(2); // Duplicate doesn't get added

// Result would be [1, 2, 3]

HashSet-i töö põhimõte​

Nagu varasemalt mainitud, siis HashSet töötab paisktabeli toel sisemiselt. See tähendab, et:

  1. Kui lisada hulka element, siis arvutatakse selle elemendi räsikood välja hashCode() meetodi kaudu.
  2. Sama räsiväärtusega elemendid grupeeritakse kokku (sisuliselt tekib "ämber" elementidest).
  3. Kui element on sama räsiga ning ka equals() tagastab true (ehk on samad elemendid), siis elementi ei lisata hulka.

Paisktabel võimaldab väga kiireid operatsioone elementidega. Elementide lisamine, eemaldamine ja olemasolu kontroll toimub enamus kordadest konstantse ajaga ehk O(1) kiirusega, kuna elemendi õige asukoht leitakse räsifunktsiooni abil ilma kõiki elemente läbi vaatamata.
Samas ei taga paisktabel elementide kindlat järjekorda. Elemendid ei esine lisamise järjekorras ega mõnes muus loogilises järjestuses, vaid sõltuvad nende räsiväärtustest ja sisemisest jaotusest tabelis.
Lisaks võib elementide paigutus ajas muutuda. Kui paisktabeli maht täitub ja toimub selle suurendamine, arvutatakse elementide asukohad uuesti ning need võivad sattuda teistesse grupeeringutesse. Seetõttu ei sobi HashSet juhul, kui elementide järjekord peab olema püsiv või etteaimatav. See on tõhus juhtudel, kus on vaja kiiret otsingut ja kontrolli suurte andmehulkade seas.

Levinumad operatsioonid​

Elementide lisamine​

Set-i add(T element) meetod tagastab tõeväärtuse vastavalt sellele, kas element lisati või mitte.

HashSet<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Apple");    // Returns false - already exists
System.out.println(set.size());  // 2

// Adds all provided elements into set, filtering out duplicates
set.addAll(Arrays.asList("Apple", "Banana", "Coconut"));

Elementide eemaldamine​

Sama kehtib ka elementide eemaldamise kohta.

set.remove("Apple");
boolean wasRemoved = set.remove("Orange");   // false - wasn't in set

//removes all elements from set
exampleSet.clear();

Elementide olemasolu kontrollimine​

boolean hasApple = set.contains("Apple");    // Very fast - O(1)

// Checks the size of set
int length = exampleSet.size();

TreeSet​

TreeSet salvestab andmeid sorteeritud järjestuses. Elementide lisamisel hulk sorteeritakse automaatselt ära.

TreeSet-i loomine​

TreeSet-i saab luua järgnevalt:

TreeSet<String> names = new TreeSet<>();
names.add("Charlie");
names.add("Alice");
names.add("Bob");
names.add("Bob");   // Duplicate not added

System.out.println(names);  // [Alice, Bob, Charlie]

TreeSet-i töö põhimõte​

TreeSet kasutab sisemiselt red-black tree struktuuri. Sisuliselt on tegemist tasakaalustatud binaarse otsingupuuga. See tähendab, et:

  1. Elemendid salvestatakse puustruktuuri
  2. Igat elementi võrreldakse teistega, et säilitada sorteeritud järjestus
  3. Puu tasakaalustatakse automaatselt ümber

Näiteks, hulga [10, 5, 3, 15, 7] puustruktuur oleks:

TreeSet salvestab elemente alati sorteeritud kujul. Vaikimisi kasutatakse selleks elementide loomulikku järjestust, kuid vajadusel saab määrata ka kohandatud võrdlusreegleid Comparator liidese abil. Andmed hulgas on igal ajahetkel korrektselt järjestatud ning neid ei ole vaja eraldi sorteerida.
Võrreldes HashSet-iga on TreeSet aeglasem. Elementide lisamine, eemaldamine ja olemasolu kontrollimine toimub O(log n) ajaga, mis tuleneb sisemisest andmestruktuurist.
TreeSet-i üheks oluliseks eeliseks on alamhulkade või vahemike loomine. Kuna elemendid on järjestatud, siis saab efektiivselt võtta näiteks kindlasse vahemikku kuuluvaid elemente. Kui tekib vajadus enda poolt loodud objekte hoida sellises hulgas, siis need elemendid peavad olema omavahel võrreldavad. See tähendab, et antud klass peab realiseerima Comparable liidest või TreeSet-i loomise hetkel peab Comparator-i ette andma (saab anda argumendina kaasa loomise hetkel). Ilma võrdlusmehhanismita ei ole võimalik elemente puus õigesse kohta paigutada ning TreeSet kaotaks oma mõtte ära seljuhul.

Spetsiifilised TreeSet-i operatsioonid​

Lisaks Set liidesest tulevatele meetoditele on TreeSet-il ka mõned omapärased meetodid olemas:

TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(2);
numbers.add(8);
numbers.add(1);
numbers.add(9);

// Get first and last
System.out.println(numbers.first());    // 1
System.out.println(numbers.last());     // 9

// Get elements lower/higher than value
System.out.println(numbers.lower(5));   // 2 (highest element < 5)
System.out.println(numbers.higher(5));  // 8 (lowest element > 5)

// Get subset
Set<Integer> subset = numbers.subSet(2, 8);  // [2, 5] (2 inclusive, 8 exclusive)
Set<Integer> headSet = numbers.headSet(5);   // [1, 2] (< 5)
Set<Integer> tailSet = numbers.tailSet(5);   // [5, 8, 9] (>= 5)

Võrdlusmehhanism​

Selleks, et TreeSet korrektselt töötaks, peab sinna salvestatav andmetüüp kas realiseerima Comparable liidest või hulgale endale peab võrdlusloogika ette andma.

// Works - Integer implements Comparable
TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(2);  // OK

// Works - String implements Comparable
TreeSet<String> words = new TreeSet<>();
words.add("banana");
words.add("apple");  // OK - sorted alphabetically

Kui nüüd proovida lisada objekti, mille klass ei realiseeri Comparable liidest, tõstatakse erind:

class Person {
    String name;
    int age;
}

TreeSet<Person> people = new TreeSet<>();
people.add(new Person());  // ClassCastException - Person cannot be cast to Comparable

Seda saab lahendada kahel viisil, kas klass ise realiseerib Comprarable liidest või see antakse hulga loomise hetkel kaasa:

// Sort people based on name
TreeSet<Person> people = new TreeSet<>((p1, p2) -> p1.name.compareTo(p2.name));

LinkedHashSet​

LinkedHashSet on sarnane HashSet'iga, kuid erinevalt viimasest sälitab LinkedHashSet oma elementide järjekorra lisamise alusel. Sisuliselt ta liidab endas kokku HashSet-i ja LinkedList-i omadusi, tagades ka elementide unikaalsust.

LinkedHashSet-i loomine​

LinkedHashSet-i saab luua järgnevalt:

LinkedHashSet<String> names = new LinkedHashSet<>();
names.add("Charlie");
names.add("Alice");
names.add("Bob");

System.out.println(names);  // [Charlie, Alice, Bob] - insertion order maintained

LinkedHashSet-i töö põhimõte​

LinkedHashSet töötab LinkedList-ile sarnaselt ehk ta hoiab endas sõlmede ahelat, kus iga sõlm koosneb elemendist ning viitest eelmisele ja järgmisele sõlmele. Erinevuseks on, et LinkedHashSet kasutab otsingute läbi viimiseks paisktabelit ja räsiväärtusi. Selline lähenemine kasutab küll rohkem mälu, kuid eeliseks on kiired operatsioonid hulkadega (võrreldav HashSet-iga).

Millist millal eelistada?​

Enamus juhtudest eelista HashSet-i kuna see on enim levinud implementatsioon. TreeSet ja LinkedHashSet tuleks kaaluda, kui sul on vaja nende spetsiifilisi omadusi, näiteks elementide automaatne sorteerimine, alamhulkade tekitamine, sisestamise järjekorra olemasolu jne.

Hulgatehted​

Javas on võimalik hulkadel ka läbi viia hulgatehteid, näiteks:

Hulkade ühinemine (union)​

Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3));
Set<Integer> set2 = new HashSet<>(Arrays.asList(3, 4, 5));

Set<Integer> union = new HashSet<>(set1);
union.addAll(set2);
System.out.println(union);  // [1, 2, 3, 4, 5]

Piltlikult see näeks välja sedasi:

Hulkade ühisosa (intersection)​

Set<Integer> intersection = new HashSet<>(set1);
intersection.retainAll(set2);
System.out.println(intersection);  // [3]

Piltlikult see näeks välja sedasi:

Hulkade erinevus (difference)​

Set<Integer> difference = new HashSet<>(set1);
difference.removeAll(set2);
System.out.println(difference);  // [1, 2]

Piltlikult see näeks välja sedasi:

Kollektsioonide teisendamine​

Üks asi, mida väga tihti tehakse on kollektsioonide teisendamine. Täpsemalt siis järjendi teisendamise hulgaks (duplikaatide eemaldamine) ning vastupidi (tagasi järjendiks).

// List to set
List<String> listWithDuplicates = Arrays.asList("A", "B", "A", "C");
Set<String> uniqueElements = new HashSet<>(listWithDuplicates); // [A, B, C]

// Set to List:
Set<String> set = new HashSet<>(Arrays.asList("A", "B", "C"));
List<String> list = new ArrayList<>(set);

Muutumatud hulgad​

Sarnaselt järjenditele on võimalik luua ka muutumatuid hulki. Põhjused nende loomiseks on sarnased järjendite omadele.

Set<String> immutableSet = Set.of("A", "B", "C");
immutableSet.add("D");  // Throws UnsupportedOperationException

// Set.of() does not allow null elements
Set<String> set = Set.of("A", null);  // Throws NullPointerException

// Set.of() does not allow duplicates at creation
Set<String> set = Set.of("A", "B", "A");  // Throws IllegalArgumentException

Levinumad vead hulkadega tegelemisel​

hashCode() ja equals()​

Selleks et paisktabelil põhinevad hulgad korrektselt saaksid töötada, peavad sisestatavad elemendid realiseerima hashCode() ja equals() meetodeid korrektselt.
Näiteks:

class Person {
      String name;
      int age;

      // Without hashCode/equals override
  }

Person p1 = new Person();
p1.name = "Alice";
Person p2 = new Person();
p2.name = "Alice";

Set<Person> people = new HashSet<>();
people.add(p1);
people.add(p2);
System.out.println(people.size());  // 2 - treats as different objects!

Nende meetodite kohta tuleb tulevikus erladi artikkel. Sisuliselt hashCode() arvutab objekti räsiväärtuse. Räsiväärtus ei ole unikaalne ning konfliktid (hash collisions) esinevad sageli. Selleks, et lõplikult kindlaks teha kas objektid on samad kasutatakse equals() meetodit ehk kontrollitakse ka objekti sisu. Räsiväärtus võimaldab kiirelt ja efektiivselt esmast samasuskontrolli teha, kuid ainult sellele ei tohiks toetuda.

Elementide muutmine​

Elementide lisamisel hulka arvutatakse välja selle räsiväärtus ning lisatakse see paisktabelisse. Kui seda elementi nüüd muuta (vt. näidet allpool), siis muutub ka selle objekti räsiväärtus. Seda väärtust ei uuendata paisktabelis ning tulemusena elemendi olemasolu kontrollivad meetodid ei leia elementi enam üles. Näiteks:

class MutablePerson {
    String name;

    @Override
    public int hashCode() {
        return name.hashCode();
    }
}

// ...

MutablePerson person = new MutablePerson();
person.name = "Alice";

Set<MutablePerson> people = new HashSet<>();
people.add(person);

person.name = "Bob";  // Changed after adding!
System.out.println(people.contains(person));  // false - can't find it anymore!

Reeglina kui element hulka lisatakse, siis seda enam ei tohiks muuta või räsiväärtuse arvutamisest peaks välja jätma omadused, mis võivad muutuda.

Hulkade võrdlemine​

Javas hulgad on objektid, seega == operaatoriga neid võrrelda ei tohiks. Objektide omavaheliseks võrdlemiseks on ette nähtud .equals() meetod. Hulgad implementeerivad .equals() meetodit elementide sisu alusel. Erinevalt järjenditest elementide järjekorda ei arvestata.