LinkedHashSet
LinkedHashSet — это одна из реализаций интерфейса Set в Java, которая сочетает в себе преимущества HashSet и LinkedList. Как и HashSet, LinkedHashSet гарантирует уникальность элементов, но в отличие от HashSet, он сохраняет порядок вставки элементов. Это делает его полезным в ситуациях, когда важно сохранить последовательность добавления элементов, но при этом необходимо гарантировать их уникальность.
Отличие от HashSet
Порядок элементов:
Основное отличие между LinkedHashSet и HashSet заключается в порядке элементов. В HashSet порядок элементов не гарантируется и может изменяться при выполнении операций с множеством. В LinkedHashSet же порядок элементов всегда соответствует порядку их вставки.
Дополнительные накладные расходы:
За поддержку порядка вставки приходится платить дополнительными накладными расходами на хранение связанного списка, что делает LinkedHashSet немного более ресурсоемким по сравнению с HashSet.
Использование памяти:
Внутри LinkedHashSet требует больше памяти, поскольку кроме данных элементов, он хранит ссылки на предыдущий и следующий элементы, что поддерживает связный список.
Особенности LinkedHashSet
Сохраняемый порядок вставки:
Как упоминалось ранее, порядок элементов в LinkedHashSet соответствует порядку их добавления. Это делает его полезным для реализации кешей, где порядок имеет значение, или для задач, где важна последовательность операций.
Уникальность элементов:
Как и любой другой Set, LinkedHashSet гарантирует, что каждый элемент будет уникальным. При добавлении дубликата он просто игнорируется.
Производительность:
Операции добавления, удаления, и проверки наличия элемента в LinkedHashSet имеют временную сложность O(1), аналогично HashSet. Однако из-за дополнительного управления связным списком, реальная производительность может быть несколько ниже.
Не синхронизирован:
Как и HashSet, LinkedHashSet не является потокобезопасным. Для использования в многопоточной среде доступ к нему необходимо явно синхронизировать.
Внутреннее устройство LinkedHashSet
LinkedHashSet основан на HashMap, но с дополнительным механизмом для поддержания порядка элементов.
Комбинация HashMap и LinkedList:
Внутренне LinkedHashSet использует LinkedHashMap, который сам по себе является расширением HashMap, но с добавлением двусвязного списка для хранения порядка элементов.
Каждая запись в LinkedHashMap содержит три ссылки: на ключ (элемент Set), на следующий элемент и на предыдущий элемент. Это позволяет сохранять итерируемый порядок элементов.
Порядок вставки:
В LinkedHashMap для каждого элемента поддерживается порядок вставки через двусвязный список. Это достигается с помощью дополнительных ссылок в каждом элементе: before и after, указывающих на предыдущий и следующий элементы соответственно.
Пример внутреннего устройства:
Когда вы добавляете элементы в LinkedHashSet, они хранятся в HashMap (в случае LinkedHashSet — в LinkedHashMap), и порядок вставки сохраняется в связном списке.
В данном случае элементы будут храниться и выводиться в порядке: Apple, Banana, Orange.
Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://www.baeldung.com/java-linkedhashset
https://www.examclouds.com/ru/java/java-core-russian/interface-set
#Java #Training #Medium #LinkedHashSet
LinkedHashSet — это одна из реализаций интерфейса Set в Java, которая сочетает в себе преимущества HashSet и LinkedList. Как и HashSet, LinkedHashSet гарантирует уникальность элементов, но в отличие от HashSet, он сохраняет порядок вставки элементов. Это делает его полезным в ситуациях, когда важно сохранить последовательность добавления элементов, но при этом необходимо гарантировать их уникальность.
Отличие от HashSet
Порядок элементов:
Основное отличие между LinkedHashSet и HashSet заключается в порядке элементов. В HashSet порядок элементов не гарантируется и может изменяться при выполнении операций с множеством. В LinkedHashSet же порядок элементов всегда соответствует порядку их вставки.
Дополнительные накладные расходы:
За поддержку порядка вставки приходится платить дополнительными накладными расходами на хранение связанного списка, что делает LinkedHashSet немного более ресурсоемким по сравнению с HashSet.
Использование памяти:
Внутри LinkedHashSet требует больше памяти, поскольку кроме данных элементов, он хранит ссылки на предыдущий и следующий элементы, что поддерживает связный список.
Особенности LinkedHashSet
Сохраняемый порядок вставки:
Как упоминалось ранее, порядок элементов в LinkedHashSet соответствует порядку их добавления. Это делает его полезным для реализации кешей, где порядок имеет значение, или для задач, где важна последовательность операций.
Уникальность элементов:
Как и любой другой Set, LinkedHashSet гарантирует, что каждый элемент будет уникальным. При добавлении дубликата он просто игнорируется.
Производительность:
Операции добавления, удаления, и проверки наличия элемента в LinkedHashSet имеют временную сложность O(1), аналогично HashSet. Однако из-за дополнительного управления связным списком, реальная производительность может быть несколько ниже.
Не синхронизирован:
Как и HashSet, LinkedHashSet не является потокобезопасным. Для использования в многопоточной среде доступ к нему необходимо явно синхронизировать.
Внутреннее устройство LinkedHashSet
LinkedHashSet основан на HashMap, но с дополнительным механизмом для поддержания порядка элементов.
Комбинация HashMap и LinkedList:
Внутренне LinkedHashSet использует LinkedHashMap, который сам по себе является расширением HashMap, но с добавлением двусвязного списка для хранения порядка элементов.
Каждая запись в LinkedHashMap содержит три ссылки: на ключ (элемент Set), на следующий элемент и на предыдущий элемент. Это позволяет сохранять итерируемый порядок элементов.
public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, Serializable {
private transient LinkedHashMap<E, Object> map;
// Значение для всех ключей в LinkedHashSet
private static final Object PRESENT = new Object();
public LinkedHashSet() {
map = new LinkedHashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
}
Порядок вставки:
В LinkedHashMap для каждого элемента поддерживается порядок вставки через двусвязный список. Это достигается с помощью дополнительных ссылок в каждом элементе: before и after, указывающих на предыдущий и следующий элементы соответственно.
Пример внутреннего устройства:
Когда вы добавляете элементы в LinkedHashSet, они хранятся в HashMap (в случае LinkedHashSet — в LinkedHashMap), и порядок вставки сохраняется в связном списке.
LinkedHashSet<String> linkedSet = new LinkedHashSet<>();
linkedSet.add("Apple");
linkedSet.add("Banana");
linkedSet.add("Orange");
В данном случае элементы будут храниться и выводиться в порядке: Apple, Banana, Orange.
Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://www.baeldung.com/java-linkedhashset
https://www.examclouds.com/ru/java/java-core-russian/interface-set
#Java #Training #Medium #LinkedHashSet
Хабр
Структуры данных в картинках. LinkedHashMap
Привет Хабрачеловеки! После затяжной паузы, я попробую продолжить визуализировать структуры данных в Java. В предыдущих статьях были замечены: ArrayList , LinkedList , HashMap . Сегодня заглянем...
Основные методы LinkedHashSet и их применение
add(E e):
Добавляет указанный элемент в множество, если он еще отсутствует.
Возвращает true, если элемент был добавлен, и false, если он уже присутствовал в множестве.
remove(Object o):
Удаляет указанный элемент из множества, если он присутствует.
Возвращает true, если элемент был удален, и false, если его не было в множестве.
contains(Object o):
Проверяет, присутствует ли указанный элемент в множестве.
Возвращает true, если элемент присутствует, и false в противном случае.
isEmpty():
Проверяет, пусто ли множество.
Возвращает true, если множество пусто, и false в противном случае.
size():
Возвращает количество элементов в множестве.
clear():
Удаляет все элементы из множества. После вызова этого метода множество будет пустым.
iterator():
Возвращает итератор для обхода элементов в множестве. Порядок обхода будет соответствовать порядку вставки элементов.
clone():
Создает поверхностную копию LinkedHashSet.
Примеры использования LinkedHashSet
Сохранение порядка уникальных элементов:
LinkedHashSet отлично подходит для ситуаций, когда важно сохранить порядок уникальных элементов, например, при обработке пользовательских данных в том порядке, в котором они были введены.
Реализация простого кеша:
LinkedHashSet может использоваться для реализации кеша, где важно сохранить порядок недавнего использования элементов.
Создание списка с исключением дубликатов:
LinkedHashSet позволяет быстро создать список уникальных элементов, сохраняя их порядок.
#Java #Training #Medium #LinkedHashSet
add(E e):
Добавляет указанный элемент в множество, если он еще отсутствует.
Возвращает true, если элемент был добавлен, и false, если он уже присутствовал в множестве.
LinkedHashSet<String> set = new LinkedHashSet<>();
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());
}
clone():
Создает поверхностную копию LinkedHashSet.
LinkedHashSet<String> clonedSet = (LinkedHashSet<String>) set.clone();
Примеры использования LinkedHashSet
Сохранение порядка уникальных элементов:
LinkedHashSet отлично подходит для ситуаций, когда важно сохранить порядок уникальных элементов, например, при обработке пользовательских данных в том порядке, в котором они были введены.
LinkedHashSet<String> orderedSet = new LinkedHashSet<>();
orderedSet.add("One");
orderedSet.add("Two");
orderedSet.add("Three");
orderedSet.add("Two"); // Дубликат будет проигнорирован
for (String item : orderedSet) {
System.out.println(item);
}
// Вывод будет в порядке вставки: One, Two, Three
Реализация простого кеша:
LinkedHashSet может использоваться для реализации кеша, где важно сохранить порядок недавнего использования элементов.
LinkedHashSet<String> cache = new LinkedHashSet<>();
cache.add("Page1");
cache.add("Page2");
cache.add("Page3");
if (cache.size() > 2) {
String first = cache.iterator().next();
cache.remove(first);
}
cache.add("Page4");
System.out.println(cache);
// Вывод: [Page2, Page3, Page4]
Создание списка с исключением дубликатов:
LinkedHashSet позволяет быстро создать список уникальных элементов, сохраняя их порядок.
List<String> listWithDuplicates = Arrays.asList("a", "b", "c", "a", "b");
LinkedHashSet<String> uniqueSet = new LinkedHashSet<>(listWithDuplicates);
System.out.println(uniqueSet); // Вывод: [a, b, c]
#Java #Training #Medium #LinkedHashSet
Коллекции в 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, из-за хэш-таблицы.
Пример кода:
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.
Пример кода:
#Java #для_новичков #beginner #Collections #HashSet #LinkedHashSet #TreeSet
Глава 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, из-за структуры дерева.
Пример кода:
Применение множеств: Удаление дубликатов и проверка уникальности
Множества идеальны для задач, где нужна уникальность без дубликатов.
Удаление дубликатов:
Преобразуйте List или массив в Set — дубликаты автоматически удалятся.
Нюанс: Порядок может потеряться (используйте LinkedHashSet для сохранения).
Пример кода:
Проверка уникальности:
Используйте contains() для быстрой проверки наличия (O(1) в HashSet).
Или add() — если false, элемент уже есть.
Нюанс: Для больших данных Set эффективнее, чем перебор List (O(n)).
Пример кода:
Полезные советы для новичков
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
Реализация 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