Інтерфейс Set та клас HashSet - уроки програмування для дітей

В Java колекції типу множин (Sets) є ключовими структурами даних, які зберігають унікальні елементи, не допускаючи дублікатів. Інтерфейс Set є основою для всіх реалізацій множин. Класи, такі як HashSet, TreeSet, а також інтерфейси SortedSet і NavigableSet, розширюють функціональність Set і надають різні можливості для зберігання та обробки даних.

1. Інтерфейс Set

Set — це колекція, яка не дозволяє дублікати, тобто кожен елемент може бути доданий лише один раз. Основна відмінність між Set і іншими колекціями (наприклад, List) полягає в тому, що множина не зберігає порядок елементів і не дозволяє зберігати однакові значення.

Основні методи інтерфейсу Set:

add(E e): додає елемент у множину, якщо його ще немає в колекції.
remove(Object o): видаляє елемент з множини.
contains(Object o): перевіряє, чи є елемент у множині.
size(): повертає кількість елементів у множині.
isEmpty(): перевіряє, чи порожня множина.

2. Клас HashSet

HashSet — це найпоширеніша реалізація інтерфейсу Set, яка використовує хешування для зберігання елементів. Хеш-таблиці дозволяють виконувати операції пошуку, вставки та видалення елементів дуже швидко — за час O(1).

Особливості HashSet:

Швидкий доступ: Використання хешування дозволяє виконувати операції над елементами за константний час.
Без порядку: HashSet не гарантує, що елементи будуть зберігатися або виводитися в певному порядку.
Унікальні елементи: Як і всі множини, HashSet не допускає дублікатів.

Приклад використання HashSet:

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

public class Main {
public static void main(String[] args) {
Set<String> set = new HashSet<>();
set.add(“Київ”);
set.add(“Львів”);
set.add(“Одеса”);
set.add(“Київ”); // Дублікати не допускаються

System.out.println(set); // Може вивести елементи в довільному порядку
System.out.println(set.contains(“Львів”)); // Виведе true
}
}

Переваги HashSet:

Швидкий доступ до елементів через хешування.
Ефективність при великих наборах даних завдяки використанню хеш-таблиць.

Недоліки:

Немає порядку: HashSet не гарантує збереження елементів у певному порядку.

3. Інтерфейс SortedSet

SortedSet — це підінтерфейс Set, який гарантує, що елементи зберігаються в сортованому порядку. Кожен елемент порівнюється з іншими, і множина автоматично підтримує елементи в відсортованому вигляді.

Основні методи `SortedSet`:

first(): повертає найменший елемент.
last(): повертає найбільший елемент.
headSet(E toElement): повертає підмножину елементів, менших за заданий.
tailSet(E fromElement): повертає підмножину елементів, більших або рівних заданому.

Приклад використання SortedSet:

import java.util.SortedSet;
import java.util.TreeSet;

public class Main {
public static void main(String[] args) {
SortedSet<Integer> sortedSet = new TreeSet<>();
sortedSet.add(5);
sortedSet.add(2);
sortedSet.add(9);
sortedSet.add(1);

System.out.println(sortedSet); // Виведе [1, 2, 5, 9] у відсортованому порядку
System.out.println(sortedSet.first()); // Виведе 1 (найменший елемент)
System.out.println(sortedSet.last()); // Виведе 9 (найбільший елемент)
}
}

4. Інтерфейс `NavigableSet

NavigableSet — це розширення інтерфейсу SortedSet, яке додає методи для навігації по множині та виконання запитів щодо найближчих елементів.

Основні методи NavigableSet:

lower(E e): повертає найбільший елемент, який менший за заданий.
higher(E e): повертає найменший елемент, який більший за заданий.
ceiling(E e): повертає найменший елемент, який більший або рівний заданому.
floor(E e): повертає найбільший елемент, який менший або рівний заданому.

Приклад використання NavigableSet:

import java.util.NavigableSet;
import java.util.TreeSet;

public class Main {
public static void main(String[] args) {
NavigableSet<Integer> navSet = new TreeSet<>();
navSet.add(10);
navSet.add(20);
navSet.add(30);
navSet.add(40);

System.out.println(navSet.lower(30)); // Виведе 20 (найбільший елемент менший за 30)
System.out.println(navSet.higher(30)); // Виведе 40 (найменший елемент більший за 30)
System.out.println(navSet.floor(30)); // Виведе 30 (найбільший елемент менший або рівний 30)
System.out.println(navSet.ceiling(25)); // Виведе 30 (найменший елемент більший або рівний 25)
}
}

5. Клас TreeSet

TreeSet — це клас, який реалізує інтерфейси NavigableSet та SortedSet на основі бінарного дерева (зазвичай червоно-чорного). Він автоматично зберігає елементи у відсортованому порядку і забезпечує додаткову функціональність навігації.

Особливості TreeSet:

Сортування: Елементи зберігаються у відсортованому порядку.
Швидкі операції пошуку: Завдяки використанню бінарного дерева, операції пошуку та вставки мають час O(log n).
Додаткова навігація: За допомогою інтерфейсу NavigableSet, TreeSet дозволяє легко шукати елементи, більші чи менші за певне значення.

Приклад використання TreeSet:

import java.util.TreeSet;

public class Main {
public static void main(String[] args) {
TreeSet<String> treeSet = new TreeSet<>();
treeSet.add(“Яблуко”);
treeSet.add(“Банан”);
treeSet.add(“Груша”);

System.out.println(treeSet); // Виведе [Банан, Груша, Яблуко] (відсортовано за алфавітом)
}
}

Переваги TreeSet:

Автоматичне сортування елементів.
Швидкий пошук завдяки структурі бінарного дерева.
Підтримує операції з навігації по множині.

Недоліки:

Повільніший доступ до елементів порівняно з HashSet, оскільки операції вставки та пошуку виконуються за час O(log n), а не за O(1).

Висновок

Set — це основний інтерфейс для роботи з множинами, який гарантує збереження лише унікальних елементів.
HashSet забезпечує швидкий доступ і маніпуляцію елементами, але не підтримує жодного порядку.
SortedSet забезпечує автоматичне сортування елементів, а NavigableSet додає можливість навігації та виконання складніших запитів.
TreeSet — це реалізація SortedSet і NavigableSet, яка зберігає елементи у відсортованому порядку, використовуючи структуру дерева, забезпечуючи при цьому швидкий пошук і навігацію.

Вибір між цими структурами даних залежить від вимог до збереження порядку, швидкості доступу та необхідної функціональності для маніпуляцій з елементами.

Інтерфейс Set та клас HashSetSortedSet, NavigableSet, TreeSet