HashSet у Java

Клас HashSet реалізує інтерфейс Set, що ґрунтується на хеш-таблиці, а також підтримується за допомогою екземпляра HashMap. У HashSet елементи не впорядковані, немає жодних гарантій, що елементи будуть знаходитися у тому самому порядку через якийсь час. Операції додавання, видалення і пошуку будуть виконуватися за константний час за умови, що хеш-функція правильно розподіляє елементи по "кошиках", про що буде розказано далі. Декілька важливих пунктів про HashSet:

• Оскільки клас реалізує інтерфейс Set, він може зберігати тільки унікальні значення;
• Може зберігати NULL- значення;
• Порядок додавання елементів обчислюється за допомогою хеш-коду;
• HashSet також реалізує інтерфейси Serializable і Cloneable.

Для підтримання постійного часу виконання операцій час, що витрачається на дії з HashSet, має бути прямо пропорційний кількості елементів у HashSet + "ємність" вбудованого екземпляра HashMap (кількість «кошиків»). Тому для підтримки продуктивності дуже важливо не встановлювати занадто високу початкову ємність (або занадто низький коефіцієнт завантаження). Початкова ємність – початкова кількість комірок («кошиків») у хеш-таблиці. Якщо всі комірки будуть заповнені, їхня кількість збільшиться автоматично. Коефіцієнт завантаження – показник того, наскільки заповненим може бути HashSet до того моменту, коли його ємність автоматично збільшиться. Коли кількість елементів у HashSet стає більшою, ніж добуток початкової ємності та коефіцієнта завантаження, хеш-таблиця ре-хешується (наново обчислюються хешкоди елементів, і таблиця перебудовується відповідно до отриманих значень), і кількість комірок у ній збільшується у 2 рази. Коефіцієнт завантаження = Кількість збережених елементів у таблиці / розмір хеш-таблиці Наприклад, якщо початкова кількість комірок у таблиці дорівнює 16, і коефіцієнт завантаження дорівнює 0,75, то з цього випливає, що коли кількість заповнених комірок сягне 12, їхня кількість автоматично збільшиться. Коефіцієнт завантаження і початкова ємність – два головні чинники, від яких залежить продуктивність операцій з HashSet. Коефіцієнт завантаження, що дорівнює 0,75, у середньому забезпечує хорошу продуктивність. Якщо цей параметр збільшити, тоді зменшиться навантаження на пам'ять (оскільки це зменшить кількість операцій ре-хешування і перебудовування), але це вплине на операції додавання і пошуку. Щоб мінімізувати час, що витрачається на ре-хешування, потрібно правильно підібрати параметр початкової ємності. Якщо початкова ємність більша за максимальну кількість елементів, поділену на коефіцієнт завантаження, то жодної операції ре-хешування не відбудеться в принципі. Важливо: HashSet не є структурою даних із вбудованою синхронізацією, тому якщо з ним працюють одночасно кілька потоків, і щонайменше один із них намагається внести зміни, необхідно забезпечити синхронізований доступ ззовні. Часто це робиться через інший об'єкт, що синхронізується, який інкапсулює HashSet. Якщо такого об'єкта немає, то найкраще підійде метод Collections.synchronizedSet(). Наразі це найкращий засіб для запобігання несинхронізованим операціям з HashSet.

Set s = Collections.synchronizedSet(new HashSet(...));

Конструктори HashSet:

1. HashSet h = new HashSet(); – конструктор за замовчуванням. Початкова ємність за замовчуванням – 16, коефіцієнт завантаження – 0,75.
2. HashSet h = new HashSet(int initialCapacity) – конструктор із заданою початковою ємністю. Коефіцієнт завантаження – 0,75.
3. HashSet h = new HashSet(int initialCapacity, float loadFactor); – конструктор із заданими початковою ємністю і коефіцієнтом завантаження.
4. HashSet h = new HashSet(Collection C) – конструктор, що додає елементи з іншої колекції.

Код нижче демонструє деякі методи HashSet:

import java.util.*; 
  
class Test 
{ 
    public static void main(String[]args) 
    { 
        HashSet<String> h = new HashSet<String>(); 
  
        // Додаємо елементи в HashSet за допомогою методу add() 
        h.add("India"); 
        h.add("Australia"); 
        h.add("South Africa"); 
        h.add("India");// намагаємося додати ще один такий самий елемент
  
        // Виводимо елементи HashSet у консоль
        System.out.println(h); 
        System.out.println("List contains India or not:" + 
                           h.contains("India"))); 
  
        // Видаляємо елементи з множини за допомогою методу remove() 
        h.remove("Australia"); 
        System.out.println("List after removing Australia:"+h); 
  
        // Проходимося по елементах HashSet за допомогою ітератора:
        System.out.println("Iterating over list:"); 
        Iterator<String> i = h.iterator(); 
        while (i.hasNext()) 
            System.out.println(i.next()); 
    } 
} 

Виведення: Усі класи, що реалізують інтерфейс Set, внутрішньо підтримуються реалізаціями Map. HashSet зберігає елементи за допомогою HashMap. Хоч і для додавання елемента в HashMap він має бути представлений у вигляді пари «ключ-значення», в HashSet додається тільки значення. Насправді значення, які ми передаємо в HashSet, є ключем до об'єкта HashMap, а як значення в HashMap використовується константа. Таким чином, у кожній парі «ключ-значення» всі ключі матимуть однакові значення. Реалізація HashSet у java doc:

private transient HashMap map;

// Конструктор - 1
// Усі конструктори неявно створюють об'єкт HashMap.
public HashSet()
{
    // Створюємо неявно об'єкт HashMap
    map = new HashMap();
}

// Конструктор- 2
public HashSet(int initialCapacity)
{
    // Створюємо неявно об'єкт HashMap
    map = new HashMap(initialCapacity);
}

// Об'єкт класу Object, який щоразу виступає в ролі значення в HashMap
private static final Object PRESENT = new Object();

Якщо поглянути на метод add() у HashSet:

public boolean add(E e)
{
   return map.put(e, PRESENT) == null;
}

Можна помітити, що метод add() у HashSet викликає метод put() у внутрішнього об'єкта HashMap, передаючи йому як ключ елемент, що додається, а як значення – константу PRESENT. Схожим чином працює і метод remove(). У ньому викликається метод remove() внутрішнього об'єкта HashMap:

public boolean remove(Object o)
{
  return map.remove(o) == PRESENT;
}

HashSet ґрунтується на хеш-таблиці, і операції додавання, видалення або пошуку в середньому будуть виконуватися за константний (О(1)) час. Методи HashSet:

1. boolean add(E e): додає елемент у HashSet, якщо такий відсутній, якщо ж такий елемент уже присутній, метод повертає false.
2. void clear(): видаляє всі елементи з множини.
3. boolean contains(Object o): Повертає true, якщо цей елемент присутній у множині.
4. boolean remove(Object o): видаляє цей елемент із множини, якщо такий присутній.
5. Iterator iterator(): повертає ітератор для елементів множини.
6. boolean isEmpty(): повертає true, якщо в множині немає елементів.
7. Object clone(): виконує поверхневе клонування HashSet.

Оригінал статті Javadoc