Java HashSet клас реалізує інтерфейс Set, який підтримується хеш-таблицею, яка насправді є екземпляром HashMap. Немає жодних гарантій щодо порядку повторення наборів хешів, що означає, що клас не гарантує постійний порядок елементів з часом. Цей клас допускає нульовий елемент. Клас також пропонує постійну продуктивність часу для основних операцій, таких як додавання, видалення, містить і розмір, припускаючи, що хеш-функція правильно розподіляє елементи між сегментами, про що ми розповімо далі в статті.
Функції Java HashSet
Нижче наведено кілька важливих функцій HashSet:
- Реалізує Встановити інтерфейс .
- Базовою структурою даних для HashSet є Хеш-таблиця .
- Оскільки він реалізує інтерфейс встановлення, повторювані значення не допускаються.
- Об’єкти, які ви вставляєте в HashSet, не гарантовано будуть вставлені в тому самому порядку. Об’єкти вставляються на основі їх хеш-коду.
- У HashSet дозволені елементи NULL.
- HashSet також реалізує Серіалізований і Можливість клонування інтерфейси.
Оголошення HashSet
public class HashSet extends AbstractSet implements Set, Cloneable, Serializable>
де І це тип елементів, що зберігаються в HashSet.
Приклад HashSet Java
Java
// Java program to illustrate the concept> // of Collection objects storage in a HashSet> import> java.io.*;> import> java.util.*;> > class> CollectionObjectStorage {> > >public> static> void> main(String[] args)> >{> >// Instantiate an object of HashSet> >HashSet set =>new> HashSet();> > >// create ArrayList list1> >ArrayList list1 =>new> ArrayList();> > >// create ArrayList list2> >ArrayList list2 =>new> ArrayList();> > >// Add elements using add method> >list1.add(>1>);> >list1.add(>2>);> >list2.add(>1>);> >list2.add(>2>);> >set.add(list1);> >set.add(list2);> > >// print the set size to understand the> >// internal storage of ArrayList in Set> >System.out.println(set.size());> >}> }> |
машинописний тип дати
>
>Вихід:
1>
Перед збереженням об’єкта HashSet перевіряє, чи є наявний запис за допомогою методів hashCode() і equals(). У наведеному вище прикладі два списки вважаються рівними, якщо вони містять однакові елементи в однаковому порядку. Коли ви викликаєте hashCode() у двох списках, вони обидва дадуть однаковий хеш, оскільки вони однакові.
Примітка: HashSet робить не зберігати дублікати елементів , якщо ви надаєте два рівних об’єкти, тоді він зберігає лише перший, тут це list1.
Ієрархія HashSet така:
Внутрішня робота HashSet
Усі класи інтерфейсу Set мають внутрішню резервну копію Map. HashSet використовує HashMap для внутрішнього зберігання свого об’єкта. Вам, мабуть, цікаво, що для введення значення в HashMap нам потрібна пара ключ-значення, але в HashSet ми передаємо лише одне значення.
Зберігання в HashMap: Насправді значення, яке ми вставляємо в HashSet, діє як ключ до об’єкта карти, а для його значення Java використовує постійну змінну. Отже, у парі ключ-значення всі значення будуть однаковими.
Реалізація HashSet у Java doc
private transient HashMap map; // Constructor - 1 // All the constructors are internally creating HashMap Object. public HashSet() { // Creating internally backing HashMap object map = new HashMap(); } // Constructor - 2 public HashSet(int initialCapacity) { // Creating internally backing HashMap object map = new HashMap(initialCapacity); } // Dummy value to associate with an Object in Map private static final Object PRESENT = new Object();> Якщо ми подивимося на додати() метод класу HashSet:
public boolean add(E e) { return map.put(e, PRESENT) == null; }> Ми можемо помітити, що метод add() класу HashSet внутрішньо викликає поставити() метод підтримки об’єкта HashMap шляхом передачі елемента, який ви вказали як ключ, і константи PRESENT як його значення. видалити() метод також працює таким же чином. Він внутрішньо викликає метод видалення інтерфейсу Map.
public boolean remove(Object o) { return map.remove(o) == PRESENT; }> HashSet зберігає не лише унікальні об’єкти, але й унікальну колекцію об’єктів люблю ArrayList , LinkedList , вектор тощо.
Конструктори класу HashSet
Щоб створити HashSet, нам потрібно створити об’єкт класу HashSet. Клас HashSet складається з різних конструкторів, які дозволяють можливе створення HashSet. Нижче наведено конструктори, доступні в цьому класі.
1. HashSet()
Цей конструктор використовується для створення порожнього об’єкта HashSet, у якому початкова ємність за замовчуванням становить 16, а коефіцієнт завантаження за замовчуванням – 0,75. Якщо ми хочемо створити порожній HashSet з іменем hs, тоді його можна створити так:
HashSet hs = new HashSet();>
2. HashSet(int initialCapacity)
Цей конструктор використовується для створення порожнього об’єкта HashSet, у якому початковий Capacity вказано під час створення об’єкта. Тут коефіцієнт навантаження за замовчуванням залишається 0,75.
HashSet hs = new HashSet(int initialCapacity);>
3. HashSet(int initialCapacity, float loadFactor)
Цей конструктор використовується для побудови порожнього об’єкта HashSet, у якому початкова ємність і коефіцієнт навантаження вказуються під час створення об’єкта.
HashSet hs = new HashSet(int initialCapacity, float loadFactor);>
4. HashSet (Колекція)
Цей конструктор використовується для створення об’єкта HashSet, що містить усі елементи з даної колекції. Коротше кажучи, цей конструктор використовується, коли потрібне будь-яке перетворення з будь-якого об’єкта Collection в об’єкт HashSet. Якщо ми хочемо створити HashSet з іменем hs, його можна створити так:
HashSet hs = new HashSet(Collection C);>
Нижче наведено виконання вищевказаних тем:
Java
// Java program to Demonstrate Working> // of HashSet Class> > // Importing required classes> import> java.util.*;> > // Main class> // HashSetDemo> class> GFG {> > >// Main driver method> >public> static> void> main(String[] args)> >{> > >// Creating an empty HashSet> >HashSet h =>new> HashSet();> > >// Adding elements into HashSet> >// using add() method> >h.add(>'India'>);> >h.add(>'Australia'>);> >h.add(>'South Africa'>);> > >// Adding duplicate elements> >h.add(>'India'>);> > >// Displaying the HashSet> >System.out.println(h);> >System.out.println(>'List contains India or not:'> >+ h.contains(>'India'>));> > >// Removing items from HashSet> >// using remove() method> >h.remove(>'Australia'>);> >System.out.println(>'List after removing Australia:'> >+ h);> > >// Display message> >System.out.println(>'Iterating over list:'>);> > >// Iterating over hashSet items> >Iterator i = h.iterator();> > >// Holds true till there is single element remaining> >while> (i.hasNext())> > >// Iterating over elements> >// using next() method> >System.out.println(i.next());> >}> }> |
>
>Вихід:
[South Africa, Australia, India] List contains India or not:true List after removing Australia:[South Africa, India] Iterating over list: South Africa India>
Методи в HashSet
| МЕТОД | ОПИС |
|---|---|
| додати (І і) | Використовується для додавання зазначеного елемента, якщо його немає, якщо він присутній, повертає false. |
| очистити() | Використовується для видалення всіх елементів із набору. |
| містить (об'єкт o) | Використовується для повернення істини, якщо елемент присутній у наборі. |
| видалити (об'єкт o) | Використовується для видалення елемента, якщо він присутній у наборі. |
| ітератор() | Використовується для повернення ітератора над елементом у наборі. |
| пусто() | Використовується для перевірки того, чи набір порожній. Повертає true для порожньої та false для непорожньої умови для набору. |
| розмір() | Використовується для повернення розміру набору. |
| клонувати() | Використовується для створення неглибокої копії набору. |
Виконання різних операцій над HashSet
Давайте подивимося, як виконати кілька часто використовуваних операцій над HashSet.
1. Додавання елементів у HashSet
Щоб додати елемент до HashSet, ми можемо використати метод add(). Однак порядок вставки не зберігається в HashSet. Нам потрібно пам’ятати, що повторювані елементи заборонені, і всі повторювані елементи ігноруються.
приклад
Java
// Java program to Adding Elements to HashSet> > // Importing required classes> import> java.io.*;> import> java.util.*;> > // Main class> // AddingElementsToHashSet> class> GFG {> > >// Method 1> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Creating an empty HashSet of string entities> >HashSet hs =>new> HashSet();> > >// Adding elements using add() method> >hs.add(>'Geek'>);> >hs.add(>'For'>);> >hs.add(>'Geeks'>);> > >// Printing all string el=ntries inside the Set> >System.out.println(>'HashSet elements : '> + hs);> >}> }> |
>
>Вихід:
HashSet elements : [Geek, For, Geeks]>
2. Видалення елементів у HashSet
Значення можна видалити з HashSet за допомогою методу remove().
приклад
Java
// Java program Illustrating Removal Of Elements of HashSet> > // Importing required classes> import> java.io.*;> import> java.util.*;> > // Main class> // RemoveElementsOfHashSet> class> GFG {> > >// Main driver method> >public> static> void> main(String[] args)> >{> >// Creating an> >HashSet hs =>new> HashSet();> > >// Adding elements to above Set> >// using add() method> >hs.add(>'Geek'>);> >hs.add(>'For'>);> >hs.add(>'Geeks'>);> >hs.add(>'A'>);> >hs.add(>'B'>);> >hs.add(>'Z'>);> > >// Printing the elements of HashSet elements> >System.out.println(>'Initial HashSet '> + hs);> > >// Removing the element B> >hs.remove(>'B'>);> > >// Printing the updated HashSet elements> >System.out.println(>'After removing element '> + hs);> > >// Returns false if the element is not present> >System.out.println(>'Element AC exists in the Set : '> >+ hs.remove(>'AC'>));> >}> }> |
>
>Вихід:
Initial HashSet [A, B, Geek, For, Geeks, Z] After removing element [A, Geek, For, Geeks, Z] Element AC exists in the Set : false>
3. Ітерація через HashSet
Перебирайте елементи HashSet за допомогою методу iterator(). Крім того, найвідомішим є використання покращений цикл for.
приклад
Кодовий блок
кордон cssВихід
A, B, Geek, For, Geeks, Z, A, B, Geek, For, Geeks, Z,>
Часова складність операцій HashSet: Базовою структурою даних для HashSet є хеш-таблиця. Отже, амортизуйте (у середньому чи звичайному випадку) складність часу для додавання, видалення та пошуку (містить метод) операції HashSet О(1) час.
Продуктивність HashSet
HashSet розширює клас Abstract Set і реалізує встановити , Cloneable і Серіалізований інтерфейси, де E — тип елементів, які підтримуються цим набором. Безпосередньо відомим підкласом HashSet є LinkedHashSet.
Тепер для підтримки постійної продуктивності в часі ітерація через HashSet вимагає часу, пропорційного сумі розміру екземпляра HashSet (кількість елементів) плюс ємність резервного екземпляра HashMap (кількість сегментів). Таким чином, дуже важливо не встановлювати надто високу початкову потужність (або занадто низький коефіцієнт завантаження), якщо важлива продуктивність ітерації.
- Початкова потужність: Початкова ємність означає кількість сегментів під час створення хеш-таблиці (HashSet внутрішньо використовує структуру даних хеш-таблиці). Кількість відер буде автоматично збільшено, якщо поточний розмір заповниться.
- Коефіцієнт навантаження: Коефіцієнт завантаження — це міра того, наскільки заповнюється HashSet, перш ніж його ємність буде автоматично збільшено. Коли кількість записів у хеш-таблиці перевищує добуток коефіцієнта завантаження на поточну ємність, хеш-таблиця повторно хешується (тобто внутрішні структури даних перебудовуються), щоб хеш-таблиця мала приблизно вдвічі більше відер.
Number of stored elements in the table Load Factor = ----------------------------------------- Size of the hash table>
приклад: Якщо внутрішня ємність дорівнює 16, а коефіцієнт завантаження дорівнює 0,75, то кількість відер буде автоматично збільшено, коли таблиця містить 12 елементів.
Вплив на продуктивність:
Коефіцієнт завантаження та початкова потужність є двома основними факторами, які впливають на продуктивність операцій HashSet. Коефіцієнт завантаження 0,75 забезпечує дуже ефективну продуктивність з огляду на часову та просторову складність. Якщо ми збільшимо значення коефіцієнта завантаження більше, ніж це, то витрати пам’яті будуть зменшені (оскільки це зменшить внутрішню операцію відновлення), але це вплине на операції додавання та пошуку в хеш-таблиці. Щоб скоротити операцію повторного хешування, нам слід розумно вибрати початкову ємність. Якщо початкова ємність перевищує максимальну кількість записів, поділену на коефіцієнт завантаження, повторна операція не відбудеться.
Примітка: Реалізація в HashSet не є синхронізованою в тому сенсі, що якщо кілька потоків одночасно отримують доступ до хеш-набору, і принаймні один із потоків змінює набір, його потрібно синхронізувати зовні. Зазвичай це досягається шляхом синхронізації на якомусь об’єкті, який природно інкапсулює набір. Якщо такого об’єкта не існує, набір слід обернути за допомогою методу Collections.synchronizedSet. Це найкраще робити під час створення, щоб запобігти випадковому несинхронізованому доступу до набору, як показано нижче:
Набір s = Collections.synchronizedSet(новий HashSet(…));
Методи, що використовуються з HashSet
1. Методи, успадковані від класу java.util.AbstractSet
| метод | опис |
|---|---|
| дорівнює() | Використовується для перевірки рівності об’єкта з HashSet і їх порівняння. Список повертає значення true, лише якщо обидва HashSet містять однакові елементи, незалежно від порядку. |
| hashcode() | Повертає значення хеш-коду для цього набору. |
| removeAll(колекція) | Цей метод використовується для видалення всіх елементів із колекції, які присутні в наборі. Цей метод повертає true, якщо цей набір змінюється в результаті виклику. |
2. Методи, успадковані від класу java.util.AbstractCollection
| МЕТОД | ОПИС |
|---|---|
| addAll(колекція) | Цей метод використовується для додавання всіх елементів зі згаданої колекції до існуючого набору. Елементи додаються випадковим чином без дотримання певного порядку. |
| міститьВсе(колекція) | Цей метод використовується для перевірки того, чи містить набір усі елементи, присутні в даній колекції, чи ні. Цей метод повертає true, якщо набір містить усі елементи, і повертає false, якщо будь-який з елементів відсутній. |
| retainAll(колекція) | Цей метод використовується для збереження всіх елементів із набору, які згадуються в даній колекції. Цей метод повертає true, якщо цей набір змінився в результаті виклику. |
| toArray() | Цей метод використовується для формування масиву з тих самих елементів, що й у Set. |
| toString() | Метод toString() Java HashSet використовується для повернення рядкового представлення елементів колекції HashSet. |
3. Методи, оголошені в інтерфейсі java.util.Collection
| МЕТОД | ОПИС |
|---|---|
| parallelStream() | Повертає, можливо, паралельний потік із цією колекцією як джерелом. |
| removeIf? (фільтр предикатів) | Видаляє всі елементи цієї колекції, які задовольняють заданий предикат. |
| потік() | Повертає послідовний потік із цією колекцією як джерелом. |
| toArray? (генератор IntFunction) | Повертає масив, що містить усі елементи цієї колекції, використовуючи надану функцію генератора для розподілу повернутого масиву. |
4. Методи, оголошені в інтерфейсі java.lang.Iterable
| МЕТОД | ОПИС |
|---|---|
| forEach? (Дії споживача) | Виконує задану дію для кожного елемента Iterable, доки всі елементи не будуть оброблені або дія не викличе виняткову ситуацію. |
5. Методи, оголошені в інтерфейсі java.util.Set
| МЕТОД | ОПИС |
|---|---|
| addAll? (Колекція c) | Додає всі елементи вказаної колекції до цього набору, якщо вони ще не присутні (необов’язкова операція). |
| міститьВсе? (Колекція c) | Повертає true, якщо цей набір містить усі елементи вказаної колекції. |
| дорівнює? (Об'єкт o) | Порівнює вказаний об’єкт із цим набором на рівність. |
| hashCode() | Повертає значення хеш-коду для цього набору. |
| removeAll? (Колекція c) | Вилучає з цього набору всі його елементи, які містяться у вказаній колекції (необов’язкова операція). |
| retainAll? (Колекція c) | Зберігає лише елементи цього набору, які містяться у вказаній колекції (необов’язкова операція). |
| toArray() | Повертає масив, що містить усі елементи цього набору. |
| toArray?(T[] a) | Повертає масив, що містить усі елементи цього набору; тип середовища виконання поверненого масиву – це тип зазначеного масиву. |
Поширені запитання щодо HashSet у Java
Q1. Що таке HashSet в Java?
відповідь:
HashSet — це тип класу, який розширює AbstractSet і реалізує інтерфейси Set.
Q2. Чому використовується HashSet?
відповідь:
HashSet використовується для уникнення повторюваних даних і пошуку значення за допомогою швидкого методу.
Q3. Відмінності між HashSet і HashMap.
відповідь:
| Основа | HashSet | HashMap |
|---|---|---|
| Реалізація | HashSet реалізує інтерфейс Set. | HashMap реалізує інтерфейс storesMap. |
| Дублікати | HashSet не допускає повторюваних значень. | HashMap зберігає пари ключів і значень і не допускає дублікатів ключів. Якщо ключ повторюється, старий ключ замінюється новим значенням. |
| Кількість об'єктів під час зберігання об'єктів | Для HashSet потрібен лише один об’єкт add(Object o). | Для додавання елемента до об’єкта HashMap для HashMap потрібні два об’єкти put (клавіша K, значення V). |
| Фіктивне значення | HashSet внутрішньо використовує HashMap для додавання елементів. У HashSet аргумент, переданий у методі add(Object), служить ключем K. Java внутрішньо пов’язує фіктивне значення для кожного значення, переданого в методі add(Object). | HashMap не має поняття фіктивного значення. |
| Зберігання або додавання механізму | HashSet внутрішньо використовує об’єкт HashMap для зберігання або додавання об’єктів. | HashMap внутрішньо використовує хешування для зберігання або додавання об’єктів |
| Швидше | HashSet повільніший за HashMap. | HashMap швидше, ніж HashSet. |
| Вставка | HashSet використовує метод add() для додавання або зберігання даних. | HashMap використовує метод put() для зберігання даних. |
| приклад | HashSet — це набір, напр. {1, 2, 3, 4, 5, 6, 7}. | HashMap — це карта пари ключ -> значення (ключ до значення), наприклад. {a -> 1, b -> 2, c -> 2, d -> 1}. |
Q4. Відмінності між HashSet і TreeSet в Java.
відповідь:
| Основа | HashSet | TreeSet |
|---|---|---|
| Швидкість і внутрішня реалізація, кидкова дія | Для таких операцій, як пошук, вставка та видалення. Для цих операцій у середньому потрібен постійний час. HashSet швидший за TreeSet. HashSet реалізовано за допомогою хеш-таблиці. | TreeSet приймає O(Log n) для пошуку, вставки та видалення, що вище, ніж HashSet. Але TreeSet зберігає відсортовані дані. Крім того, він підтримує такі операції, як above() (повертає найменший вищий елемент), floor(), strop() тощо. Ці операції також є O(Log n) у TreeSet і не підтримуються в HashSet. TreeSet реалізовано за допомогою самобалансуючого бінарного дерева пошуку (червоно-чорне дерево). TreeSet підтримується TreeMap у Java. |
| Замовлення | Елементи в HashSet не впорядковані. | TreeSet підтримує об’єкти в порядку сортування, визначеному методом Comparable або Comparator у Java. Елементи TreeSet за замовчуванням сортуються в порядку зростання. Він пропонує кілька методів роботи з упорядкованим набором, наприклад first(), last(), headSet(), tailSet() тощо. |
| Нульовий об'єкт | HashSet дозволяє нульовий об’єкт. | TreeSet не дозволяє використовувати нульовий об’єкт і створює NullPointerException. Причина тому, що TreeSet використовує метод compareTo() для порівняння ключів, а compareTo() викидає java.lang.NullPointerException. |
| Порівняння | HashSet використовує метод equals() для порівняння двох об’єктів у наборі та для виявлення дублікатів. | TreeSet використовує метод compareTo() для тієї ж мети. Якщо equals() і compareTo() неузгоджені, тобто для двох рівних об’єктів, equals має повертати true, тоді як compareTo() має повертати нуль, тоді це порушить контракт інтерфейсу Set і дозволить дублікати в реалізаціях Set, таких як TreeSet |