Java for Beginner
745 subscribers
714 photos
201 videos
12 files
1.16K links
Канал от новичков для новичков!
Изучайте Java вместе с нами!
Здесь мы обмениваемся опытом и постоянно изучаем что-то новое!

Наш YouTube канал - https://www.youtube.com/@Java_Beginner-Dev

Наш канал на RUTube - https://rutube.ru/channel/37896292/
Download Telegram
HashSet, особенности и внутреннее устройство

HashSet — это одна из наиболее часто используемых реализаций интерфейса Set в Java. Она обеспечивает хранение уникальных элементов и не гарантирует их порядок. Основные преимущества HashSet включают быструю вставку, удаление и проверку на наличие элемента, что делает его предпочтительным выбором для множества задач, связанных с уникальными данными.

Особенности HashSet

Уникальность элементов:
HashSet хранит только уникальные элементы. Если попытаться добавить дубликат, он будет проигнорирован.

Отсутствие упорядоченности:
В отличие от некоторых других коллекций, таких как TreeSet, HashSet не гарантирует порядка элементов. Порядок может изменяться с течением времени.

Производительность:
HashSet обеспечивает быструю производительность операций add, remove, и contains, обычно с временной сложностью O(1), что достигается за счет использования хеш-таблицы.

Разрешение коллизий:
Внутренне HashSet использует механизм разрешения коллизий, что позволяет эффективно справляться с ситуациями, когда два или более различных элемента имеют одинаковый хеш-код.

Не синхронизирован:
HashSet не является потокобезопасным. Если он используется в многопоточной среде, то необходимо явно синхронизировать доступ к нему.

Внутреннее устройство HashSet

Базовая структура данных:

HashSet основан на HashMap, где каждый элемент множества является ключом в HashMap, а значение всегда одно и то же (PRESENT, которое является статической константой).
По сути,
HashSet — это оболочка над HashMap, обеспечивающая уникальность элементов за счет использования ключей.
private transient HashMap<E,Object> map;

// Заглушка значения для всех ключей
private static final Object PRESENT = new Object();


Хеширование и корзины (buckets):

Каждый элемент, добавляемый в HashSet, сначала хешируется. Затем вычисляется индекс корзины (bucket), в которую этот элемент должен быть помещен. Корзина представляет собой связанный список или дерево, хранящее элементы с одинаковыми хеш-кодами.
На основе хеш-кода определяется индекс корзины в массиве корзин.
Если два объекта имеют одинаковый хеш-код, то они попадают в одну и ту же корзину, что приводит к коллизии.


Разрешение коллизий:

В HashMap, а соответственно и в HashSet, используется метод цепочек для разрешения коллизий. Это означает, что в случае коллизии элементы добавляются в связанный список, находящийся в соответствующей корзине.
Если количество элементов в корзине превышает определенный порог (обычно 8), связанный список преобразуется в дерево, что улучшает производительность поиска.


Перестройка (rehashing):

Когда количество элементов в HashSet достигает определенного порога (обычно при заполнении на 75%), происходит перераспределение и увеличение количества корзин, чтобы уменьшить количество коллизий. Это называется перестройкой или rehashing.

Равенство объектов:

Для корректной работы HashSet элементы должны корректно реализовывать методы equals() и hashCode(). Это необходимо для определения уникальности элементов и корректного размещения их в корзинах.

Пример кода внутреннего устройства
import java.util.HashSet;

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

// Добавление элементов
set.add("Apple");
set.add("Banana");
set.add("Orange");

// Попытка добавить дубликат
boolean isAdded = set.add("Apple"); // Вернет false, так как "Apple" уже существует

// Вывод элементов
for (String fruit : set) {
System.out.println(fruit);
}
}
}


Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://javarush.com/groups/posts/2147-hashset-v-java
https://ru.hexlet.io/qna/java/questions/kak-rabotaet-hashset-v-java

#Java #Training #Medium #HashSet
👍2
Основные методы HashSet и их использование

add(E e):

Добавляет указанный элемент в этот набор, если он еще отсутствует.
Возвращает true, если элемент был добавлен, и false, если элемент уже присутствует в наборе.
HashSet<String> set = new HashSet<>();
boolean added = set.add("Apple"); // Возвращает true
added = set.add("Apple"); // Возвращает false, так как элемент уже существует


remove(Object o):

Удаляет указанный элемент из набора, если он присутствует.
Возвращает true, если элемент был удален, и false, если его не было в наборе.

boolean removed = set.remove("Apple"); // Возвращает true, если "Apple" был удален
removed = set.remove("Banana"); // Возвращает false, если "Banana" не был в наборе


contains(Object o):

Проверяет, присутствует ли указанный элемент в наборе.
Возвращает true, если элемент присутствует, и false в противном случае.

boolean exists = set.contains("Apple"); // Возвращает true, если "Apple" присутствует


isEmpty():

Проверяет, пуст ли набор.
Возвращает true, если набор пуст, и false в противном случае.

boolean isEmpty = set.isEmpty(); // Проверка, пуст ли набор


size():

Возвращает количество элементов в наборе.
int size = set.size(); // Получение размера набора


clear():

Удаляет все элементы из набора. После вызова этого метода набор будет пустым.
set.clear(); // Очищает набор


iterator():

Возвращает итератор для обхода элементов в наборе.
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}


Примеры использования HashSet

Фильтрация уникальных значений:
HashSet идеально подходит для удаления дубликатов из списка элементов. Например, чтобы извлечь уникальные слова из текста.
String[] words = {"apple", "banana", "apple", "orange", "banana"};
HashSet<String> uniqueWords = new HashSet<>(Arrays.asList(words));

System.out.println(uniqueWords); // Вывод: [apple, banana, orange]


Множество без дубликатов в математических операциях:

В математике и информатике часто используются множества для выполнения операций, таких как пересечение, объединение и разность. HashSet идеально подходит для реализации этих операций.
HashSet<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4));
HashSet<Integer> set2 = new HashSet<>(Arrays.asList(3, 4, 5, 6));

// Объединение
set1.addAll(set2);
System.out.println("Union: " + set1); // Вывод: Union: [1, 2, 3, 4, 5, 6]

// Пересечение
set1.retainAll(set2);
System.out.println("Intersection: " + set1); // Вывод: Intersection: [3, 4]

// Разность
set1.removeAll(set2);
System.out.println("Difference: " + set1); // Вывод: Difference: [1, 2]


Проверка на наличие дубликатов:

HashSet можно использовать для быстрой проверки, содержится ли элемент в наборе или нет. Например, для проверки уникальности данных при их вставке в базу данных.
HashSet<String> emails = new HashSet<>();
String newEmail = "user@example.com";

if (!emails.add(newEmail)) {
System.out.println("Этот email уже используется!");
} else {
System.out.println("Email добавлен.");
}


#Java #Training #Medium #HashSet
Коллекции в Java

Глава 3. Set — множества

Реализации: HashSet, LinkedHashSet, TreeSet.

Применение множеств: удаление дубликатов, проверка уникальности


Интерфейс Set<E> имеет несколько реализаций в JCF, каждая оптимизирована под разные сценарии. Все они обеспечивают уникальность элементов, но отличаются по порядку, сортировке и времени операций.


HashSet<E>

Описание: HashSet — самая распространенная реализация Set, основанная на хэш-таблице (HashMap внутри). Она хранит элементы в "корзинах" (buckets) на основе их хэш-кода, что обеспечивает быстрый поиск и добавление.

Особенности:
Уникальность: Да, дубликаты игнорируются.
Порядок: Нет гарантированного порядка (зависит от хэша, может меняться при ресайзе).
Сортировка: Нет.
Null: Разрешен один null.
Big O: Средний случай — O(1) для add, remove, contains (константное время). Worst-case — O(n) при коллизиях хэшей, но редко с хорошим hashCode().


Внутренняя работа: Элементы хранятся как ключи в HashMap (значения — dummy объект). Хэш-код определяет бакет, equals() — проверку уникальности.

Нюансы:
Зависит от hashCode() и equals(): Плохо реализованные методы приводят к коллизиям и снижению производительности.
Ресайз: При заполнении >75% (load factor) таблица удваивается, что может занять O(n) времени.
Thread-safety: Не безопасен для многопоточности — используйте Collections.synchronizedSet(new
HashSet<>()).
Память: Занимает больше, чем ArrayList, из-за хэш-таблицы.


Пример кода:
javaimport java.util.HashSet;
import java.util.Set;

public class Main {
public static void main(String[] args) {
Set<String> fruits = new HashSet<>();
fruits.add("Яблоко");
fruits.add("Банан");
fruits.add("Яблоко"); // Игнорируется

System.out.println(fruits.contains("Банан")); // true
fruits.remove("Яблоко");

for (String fruit : fruits) {
System.out.println(fruit); // Порядок непредсказуем, например: Банан
}
}
}

Вывод: contains вернет true, размер 1 после удаления, порядок случайный.


LinkedHashSet<E>

Расширение HashSet с двусвязным списком для сохранения порядка вставки. Внутри — HashMap с LinkedHashMap-логикой.

Особенности:
Уникальность: Да.
Порядок: Сохраняет порядок вставки (insertion order).
Сортировка: Нет.
Null: Разрешен один null.
Big O: O(1) для add/remove/contains (как
HashSet), но с overhead на ссылки списка.

Внутренняя работа: Каждый элемент имеет ссылки prev/next для списка, плюс хэш-таблица для уникальности.

Нюансы:
Больше памяти, чем HashSet (из-за ссылок).
Итерация: O(n), но предсказуема по порядку вставки.
Полезен для кэшей с LRU (least recently used), но для простого порядка — эффективен.
Thread-safety: Нет, как у
HashSet.

Пример кода:
javaimport java.util.LinkedHashSet;
import java.util.Set;

public class Main {
public static void main(String[] args) {
Set<String> fruits = new LinkedHashSet<>();
fruits.add("Яблоко");
fruits.add("Банан");
fruits.add("Апельсин");

for (String fruit : fruits) {
System.out.println(fruit); // Яблоко, Банан, Апельсин — порядок вставки
}
}
}

Вывод: Элементы в том порядке, в котором добавлены.



#Java #для_новичков #beginner #Collections #HashSet #LinkedHashSet #TreeSet
👍3
TreeSet<E>

Реализация SortedSet<E>, основанная на красно-черном дереве. Автоматически сортирует элементы.

Особенности:
Уникальность: Да.
Порядок: Нет (игнорирует порядок вставки), но отсортирован по натуральному порядку или Comparator.
Сортировка: Да, всегда отсортирован.
Null: Не разрешен (NullPointerException при сравнении).
Big O: O(log n) для add/remove/contains (дерево балансировано).


Внутренняя работа: Элементы хранятся в узлах дерева, сравниваются через Comparable.compareTo() или Comparator.


Нюансы:

Элементы должны реализовывать Comparable<E> или предоставить Comparator при создании: new TreeSet<>(comparator).
Для custom классов: Реализуйте Comparable или Comparator, иначе ClassCastException.
Итерация: O(n), в отсортированном порядке.
Дополнительные методы: first(), last(), headSet(E to), tailSet(E from) — для подмножеств.
Thread-safety: Нет, используйте Collections.synchronizedSortedSet(new TreeSet<>()).
Память: Больше, чем
HashSet, из-за структуры дерева.

Пример кода:
javaimport java.util.TreeSet;
import java.util.Set;

public class Main {
public static void main(String[] args) {
Set<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(1);
numbers.add(3);

for (Integer num : numbers) {
System.out.println(num); //отсортировано
}

// С Comparator для обратного порядка
Set<Integer> reverseNumbers = new TreeSet<>((a, b) -> b - a);
reverseNumbers.add(5);
reverseNumbers.add(1);
reverseNumbers.add(3);
System.out.println(reverseNumbers); // [5, 3, 1]
}
}

Вывод: Элементы всегда отсортированы.



Применение множеств: Удаление дубликатов и проверка уникальности


Множества идеальны для задач, где нужна уникальность без дубликатов.

Удаление дубликатов:
Преобразуйте List или массив в Set — дубликаты автоматически удалятся.
Нюанс: Порядок может потеряться (используйте LinkedHashSet для сохранения).


Пример кода:
javaimport java.util.ArrayList;
import java.util.List;
import java.util.HashSet;
import java.util.Set;

public class Main {
public static void main(String[] args) {
List<String> duplicates = new ArrayList<>();
duplicates.add("Яблоко");
duplicates.add("Банан");
duplicates.add("Яблоко");

Set<String> unique = new HashSet<>(duplicates);
System.out.println(unique); // [Банан, Яблоко]

// С сохранением порядка
Set<String> orderedUnique = new LinkedHashSet<>(duplicates);
System.out.println(orderedUnique); // [Яблоко, Банан]
}
}

Вывод: Уникальные элементы, без дубликатов.


Проверка уникальности:
Используйте contains() для быстрой проверки наличия (O(1) в HashSet).
Или add() — если false, элемент уже есть.
Нюанс: Для больших данных Set эффективнее, чем перебор List (O(n)).


Пример кода:
javaimport java.util.HashSet;
import java.util.Set;

public class Main {
public static void main(String[] args) {
Set<String> users = new HashSet<>();
users.add("user1");

if (users.contains("user2")) {
System.out.println("Пользователь существует");
} else {
users.add("user2");
System.out.println("Новый пользователь добавлен");
}

if (!users.add("user1")) {
System.out.println("Дубликат не добавлен"); // add возвращает false
}
}
}

Вывод: Проверка и добавление без дубликатов.



Полезные советы для новичков

HashSet по умолчанию: Для большинства случаев уникальности.
Custom классы: Всегда реализуйте equals() и hashCode() (используйте IDE: Generate → equals() and hashCode()).
Comparator в TreeSet: Для custom сортировки: new TreeSet<>((a, b) -> a.compareTo(b)).
Удаление дубликатов: Удобно для списков из файлов или БД.
Память: TreeSet дороже по памяти,
HashSet — оптимален.
Ошибки: ClassCastException в TreeSet без Comparable; ConcurrentModificationException при модификации во время итерации (используйте Iterator.remove()).



#Java #для_новичков #beginner #Collections #HashSet #LinkedHashSet #TreeSet
👍2