Class HashSet<E>
This class offers constant time performance for the basic operations ( add , remove , contains and size ), assuming the hash function disperses the elements properly among the buckets. Iterating over this set requires time proportional to the sum of the HashSet instance’s size (the number of elements) plus the «capacity» of the backing HashMap instance (the number of buckets). Thus, it’s very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.
Note that this implementation is not synchronized. If multiple threads access a hash set concurrently, and at least one of the threads modifies the set, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the set. If no such object exists, the set should be «wrapped» using the Collections.synchronizedSet method. This is best done at creation time, to prevent accidental unsynchronized access to the set:
The iterators returned by this class’s iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the Iterator throws a ConcurrentModificationException . Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
Как работает hashset в java
A Set is a Collection that cannot contain duplicate elements. It models the mathematical set abstraction.
Set have its implementation in various classes like HashSet , TreeSet , LinkedHashSet .
HashSet:
Here T can be String , Integer or any other object. HashSet allows for quick lookup of O(1) but does not sort the data added to it and loses the insertion order of items.
TreeSet:
It stores data in a sorted manner sacrificing some speed for basic operations which take O(lg(n)). It does not maintain the insertion order of items.
LinkedHashSet:
It is a linked list implementation of HashSet Once can iterate over the items in the order they were added. Sorting is not provided for its contents. O(1) basic operations are provided, however there is higher cost than HashSet in maintaining the backing linked list.
# Basics of Set
What is a Set?
A set is a data structure which contains a set of elements with an important property that no two elements in the set are equal.
Types of Set:
- HashSet: A set backed by a hash table (actually a HashMap instance)
- Linked HashSet: A Set backed by Hash table and linked list, with predictable iteration order
- TreeSet: A NavigableSet implementation based on a TreeMap.
Creating a set
Adding elements to a Set
Elements can be added to a set using the add() method
Our set after executing this method:
Delete all the elements of a Set
After this set will be:
Check whether an element is part of the Set
Existence of an element in the set can be checked using the contains() method
Output: False
Check whether a Set is empty
isEmpty() method can be used to check whether a Set is empty.
Output: True
Remove an element from the Set
Check the Size of the Set
Output: 0
# Types and Usage of Sets
Generally, sets are a type of collection which stores unique values. Uniqueness is determined by the equals() and hashCode() methods.
Как работает hashset в java
As we know that a set is a well-defined collection of distinct objects. Each member of a set is called an element of the set. So in other words, we can say that a set will never contain duplicate elements. But how in java Set interface implemented classes like HashSet, LinkedHashSet, TreeSet etc. achieve this uniqueness. In this post, we will discuss the hidden truth behind this uniqueness.
How HashSet works internally in Java?
We will understand this with an example.Let us see the output of the following program which try to add duplicate elements in a HashSet.
Now from the output, it is clear that when we try to add a duplicate element to a set using add() method, it returns false, and element is not added to hashset, as it is already present. Now the question comes, how add() method checks whether the set already contains the specified element or not. It will be more clear if we have a closer look on the add() method and default constructor in HashSet class.
Now as you can see that whenever we create a HashSet, it internally creates a HashMap and if we insert an element into this HashSet using add() method, it actually call put() method on internally created HashMap object with element you have specified as it’s key and constant Object called “PRESENT” as it’s value. So we can say that a Set achieves uniqueness internally through HashMap. Now the whole story comes around how a HashMap and put() method internally works.
As we know in a HashMap each key is unique and when we call put(Key, Value) method, it returns the previous value associated with key, or null if there was no mapping for key. So in add() method we check the return value of map.put(key, value) method with null value.
- If map.put(key, value) returns null, then the statement “map.put(e, PRESENT) == null” will return true and element is added to the HashSet(internally HashMap).
- If map.put(key, value) returns old value of the key, then the statement “map.put(e, PRESENT) == null” will return false and element is not added to the HashSet(internally HashMap).
As LinkedHashSet extends HashSet, so it internally calls constructors of HashSet using super(). Similarly creating an object of TreeSet class internally creates object of Navigable Map as backing map.
This article is contributed by Gaurav Miglani. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Руководство по HashSet в Java
В этой статье мы погрузимся вHashSet.. Это одна из самых популярных реализацийSet, а также неотъемлемая часть Java Collections Framework.
2. Введение вHashSet
HashSet — одна из фундаментальных структур данных в Java Collections API.
Напомним наиболее важные аспекты этой реализации:
Он хранит уникальные элементы и разрешает нули
Заказ на размещение не поддерживается.
Это не потокобезопасный
Обратите внимание, что этот внутреннийHashMap инициализируется при создании экземпляраHashSet:
Если вы хотите глубже понять, как работаетHashMap, вы можете прочитатьthe article focused on it here.
3. API
В этом разделе мы рассмотрим наиболее часто используемые методы и рассмотрим несколько простых примеров.
3.1. add()с
Методadd() можно использовать для добавления элементов в набор. The method contract states that an element will be added only when it isn’t already present in a set. Если элемент был добавлен, метод возвращаетtrue,, иначе —false.
Мы можем добавить элемент вHashSet, например:
С точки зрения реализации методadd чрезвычайно важен. Детали реализации иллюстрируют, какHashSet работает внутренне и использует методHashMap’sput:
Переменнаяmap является ссылкой на внутреннюю поддержкуHashMap:
Было бы неплохо сначала познакомиться сhashcode, чтобы получить подробное представление о том, как элементы организованы в структуры данных на основе хешей.
HashMap — это массивbuckets с емкостью по умолчанию 16 элементов — каждому сегменту соответствует другое значение хэш-кода.
Если различные объекты имеют одинаковое значение хэш-кода, они сохраняются в одном сегменте
Если достигаетсяload factor, создается новый массив, вдвое превышающий размер предыдущего, и все элементы повторно хешируются и перераспределяются между новыми соответствующими сегментами.
Чтобы получить значение, мы хэшируем ключ, модифицируем его, а затем переходим к соответствующему сегменту и ищем в потенциально связанном списке, если существует более одного объекта.
3.2. contains()с
The purpose of the contains method is to check if an element is present in a given HashSet. Возвращаетtrue, если элемент найден, иначеfalse.
Мы можем проверить наличие элемента вHashSet:
Всякий раз, когда объект передается этому методу, вычисляется значение хеша. Затем соответствующее местоположение сегмента решается и пересекается.
3.3. remove()с
Метод удаляет указанный элемент из набора, если он присутствует. Этот метод возвращаетtrue, если набор содержал указанный элемент.
Давайте посмотрим на рабочий пример:
3.4. clear()с
Мы используем этот метод, когда намереваемся удалить все элементы из набора. Базовая реализация просто очищает все элементы из базовогоHashMap.
Посмотрим, как это работает:
3.5. size()с
Это один из фундаментальных методов в API. Он широко используется, поскольку помогает определить количество элементов, присутствующих вHashSet. Базовая реализация просто делегирует вычисление методуHashMap’s size().
Посмотрим, как это работает:
3.6. isEmpty()с
Мы можем использовать этот метод, чтобы выяснить, является ли данный экземплярHashSet пустым или нет. Этот метод возвращаетtrue, если набор не содержит элементов:
3.7. iterator()с
Метод возвращает итератор по элементам вSet. The elements are visited in no particular order and iterators are fail-fast.
Мы можем наблюдать случайный порядок итераций здесь:
Если набор изменяется в любое время после создания итератора любым способом, кроме собственного метода удаления итератора,Iterator генерируетConcurrentModificationException.
Посмотрим, как это работает:
В качестве альтернативы, если бы мы использовали метод удаления итератора, мы бы не столкнулись с исключением:
Безотказное поведение итератора не может быть гарантировано, поскольку невозможно дать никаких жестких гарантий при наличии несинхронизированной одновременной модификации.
Отказоустойчивые итераторы выбрасываютConcurrentModificationException из соображений максимальной эффективности. Поэтому было бы неправильно писать программу, правильность которой зависела бы от этого исключения.
4. КакHashSet сохраняет уникальность?
Когда мы помещаем объект вHashSet, он использует значение объектаhashcode, чтобы определить, есть ли элемент уже в наборе.
Каждое значение хеш-кода соответствует определенному местоположению сегмента, которое может содержать различные элементы, для которых вычисленное значение хеш-кода является одинаковым. But two objects with the same hashCode might not be equal.
Таким образом, объекты в одной корзине будут сравниваться с использованием методаequals().
5. ПроизводительностьHashSet
На производительность aHashSet в основном влияют два параметра — егоInitial Capacity иLoad Factor.
Ожидаемая временная сложность добавления элемента в набор составляетO(1), которая может упасть доO(n) в худшем случае (присутствует только одна корзина) — следовательно,it’s essential to maintain the right HashSet’s capacity.
Коэффициент загрузки описывает максимальный уровень заполнения, выше которого необходимо изменить размер набора.
Мы также можем создатьHashSet с пользовательскими значениями дляinitial capacity иload factor:
В первом случае используются значения по умолчанию — начальная емкость 16 и коэффициент загрузки 0,75. Во втором мы переопределяем емкость по умолчанию, а в третьем переопределяем оба.
Низкая начальная емкость снижает сложность пространства, но увеличивает частоту повторного хеширования, что является дорогостоящим процессом.
С другой стороны,a high initial capacity increases the cost of iteration and the initial memory consumption.
Как правило большого пальца:
Высокая начальная емкость хороша для большого количества записей в сочетании с минимальной итерацией
Низкая начальная емкость хороша для нескольких записей с большим количеством итераций
Поэтому очень важно найти правильный баланс между ними. Обычно реализация по умолчанию оптимизирована и работает просто отлично, если мы чувствуем необходимость настроить эти параметры в соответствии с требованиями, мы должны действовать разумно.
6. Заключение
В этой статье мы описали полезностьHashSet, его назначение, а также основную работу. Мы увидели, насколько он эффективен с точки зрения удобства использования, учитывая его постоянную производительность по времени и возможность избежать дублирования.
Мы изучили некоторые важные методы из API, как они могут помочь нам как разработчику использоватьHashSet в полной мере.