C, PHP, VB, .NET

Множествата са по принцип по-прости структури спрямо речниците. Те се базират на един основен интерфейс Set. Докато при речниците имахме комбинации от Key и Value, при множествата има само един единствен елемент, който е едновремено Key и Value. Или казано по друг начин множествата са речници при които всяко Value се използва за Key само за себе си. Веднага можете да се досетите, че е много лесно един Set да бъде реализиран чрез Map – например ако подавате един и същи обект за Key и Value в който и да е Map, той ще работи като Set.

С казаното дотук не е изненада, че в Java популярните имплементиращи интерфейс Set класове HashSet, LinkedHashSet и TreeSet всъщност използват именно HashMap, LinkedHashMap и TreeMap вътре в себе си. Например извиквайки метод add на един HashSet, той извиква метод put на вградения в него HashMap, като му подава параметри put(yourObject, dummyObject), където yourObject е вашия обект (използва се за key), а DummyObject e вградена в HashSet референция към следното:

private static final Object dummyObject = new Object();

Както виждате този dummyObject е винаги един и същи за всички елементи на множеството. В така създадения речник не можете да добавите друг Value за същия Key, защото интерфейс Set и неговите стандартни имплементации няма да ви предожат подобен метод. Другите популярни класове в стандартните библиотеки – LinkedHashSet и TreeSet – също използват тази техника.

От всичко казано дотук, можем да си изведем и най-важното свойство на класовете имплементиращи Set – не позволяват един и същи обект да бъде вкаран два пъти в множеството! Действително ако вие се опитате да добавите един и същи обект два пъти в Set, това ще кореспондира на дублираща се комбинация Key (обекта) и Value (dummy обекта) в съответния Map. Забележете, че това няма общо с колизиите при HashSet – и тук е възможно два или повече различни обекта да генерират един и същи хеш код и в тези случаи обектите отново се подреждат в линеен списък.

1. Интерфейсът Set

Интерфейс Set се различава съществено от интерфейс Map не само по входните параметри на методите (вместо два вече ще е само един), но и по имената им.

• boolean add(E e) – добавя елемент в множеството. Ако такъв елемент вече съществува, връща false, иначе true;
• boolean addAll(Collection<? extends E> c) – добавя всички елементи от дадена колекция в множеството. Ако има някаква промяна в множеството (имало е недублиращ елемент и той е добавен), връща true. Ако всички елементи вече са били налични в множеството, връща false;
• void clear() – изтрива всички елементи в множеството;
• boolean contains(Object o) – проверява дали подадения елемент присъства в множеството;
• boolean containsAll(Collection<?> c) – проверява дали всички елементи от подадената колекция се съдържат в множеството;
• boolean equals(Object o) – сравнява множеството с друго множество;
• int hashCode() – хеш код за самото множество (ще е нужно ако самото то бъде използвано като елемент в друго множество);
• boolean isEmpty() – показва дали множеството е празно или не;
• Iterator<E> iterator() – дава итератор;
• boolean remove(Object o) – изтрива елемент от множеството. Ако е имало такъв елемент и е изтрит, връща true. В противен случай връща false;
• boolean removeAll(Collection<?> c) – изтрива всички елементи от множеството, които съвпадат с подадената колекция. Ако поне един е изтрит, връща true. В противен случай връща false;
• boolean retainAll(Collection<?> c) – премахва от множеството всички елементи, които не присъстват в подадената колекция. Ако поне един е изтрит, връща true. В противен случай връща false;
• int size() – указва колко елемента има записани в множеството;
• default Spliterator<E> spliterator() – връща Spliterator;
• Object[] toArray() – превръща множеството в масив от обекти;
• <T> T[] toArray(T[] a) – превръща множеството в масив от обекти, като типа на масива ще съвпадне с типа на подадения като входен параметър обект. Това е доста специфичен метод, който прави лесен преход между колекциите и масивите – ще покажем как се използва по-долу.

2. Примери

Задача 1. Намерете уникалните думи във файла problems.txt и ги изведете на екрана.

Решение: Понеже не се изисква сортиране, ще използваме HashSet:

import java.util.HashSet;
import java.util.Scanner;
import java.io.FileReader;
import java.io.IOException;
import java.util.Iterator;

public class HashSetExample{
  public static void main(String[] args){
    Scanner sc = null;
    try{
      sc = new Scanner(new FileReader("problems.txt"));
    }
    catch(IOException e){
      System.out.println("Error reading the file");
      return;
    }
    
    HashSet<String> uniqueWords = new HashSet<String>();
    while(sc.hasNext()){
      uniqueWords.add(sc.next());
    }
    
    System.out.println("Уникалните думи са:");
    for(String word: uniqueWords){
      System.out.println(word);
    }
    
    System.out.println("\nСъщото нещо реализирано чрез iterator:");
    Iterator<String> it = uniqueWords.iterator();
    while(it.hasNext()){
      System.out.println(it.next());
    }
  }
}

Задача 2. Решете задача 1, но този път изведете думите подредени по азбучен ред

Решение: Просто заменете HashSet с TreeSet.

Задача 3. Демонстрирайте как горния HashSet се превръща в обикновен масив

Решение:

import java.util.HashSet;

public class HashSetExample{
  public static void main(String[] args){
    HashSet hs = new HashSet();
    hs.add("abc");
    hs.add("def");
    hs.add("abc"); // нарочно - ще бъде пропуснато
        
    String[] arr = hs.toArray(new String[0]);
    for(String el:arr) System.out.println(el);
  }
}

3. Множествата в многонишкова среда

HashSet, LinkedHashSet и TreeSet не са thread-safe, т.е. не са синхронизирани. Синхронизацията трябва да извършвате или ръчно, или чрез удобния Collections.synchronizedSet(Set set) метод. Ето как можем да направим това:

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

public class HashSetExample{
  public static void main(String[] args){
    Set<String> hs = Collections.synchronizedSet(new HashSet<String>());
    hs.add("abc");
    hs.add("def");
    hs.add("abc"); // нарочно - ще бъде пропуснато
        
    hs.forEach(System.out::println);
  }
}

Трябва да знаете, че Java не предлага еквивалентен на ConcurrentHashMap метод! За сметка на това можете много лесно да си създадете без проблем метод newSetFromMap на клас Collections, в който като параметър да подадете ConcurrentHashMap обект. Горният пример ще изглежда по следния начин:

import java.util.Set;
import java.util.HashSet;
import java.util.concurrent.ConcurrentHashMap;
import java.util.Collections;

public class HashSetExample{
  public static void main(String[] args){
    Set<String> hs = Collections.newSetFromMap(new ConcurrentHashMap<String,Boolean>());
    hs.add("abc");
    hs.add("def");
    hs.add("abc"); // нарочно - ще бъде пропуснато
        
    hs.forEach(System.out::println);
  }
}

Поради същите съображения, които бяха изложени в предишната статия, втория пример е по-ефективен от първия.