Рубрики

HashSet в Java

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

  • Реализует Set Interface .
  • Базовая структура данных для HashSet является хеш-таблицей.
  • Поскольку он реализует интерфейс Set, повторяющиеся значения не допускаются.
  • Объекты, которые вы вставляете в HashSet, не обязательно будут вставлены в том же порядке. Объекты вставляются на основе их хэш-кода.
  • Элементы NULL разрешены в HashSet.
  • HashSet также реализует интерфейсы Searlizable и Cloneable.

Теперь для поддержания постоянной производительности по времени итерация по 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. Это лучше всего делать во время создания, чтобы предотвратить случайный несинхронизированный доступ к набору, как показано ниже:

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

Конструкторы в HashSet:

  1. HashSet h = новый HashSet ();
    Начальная емкость по умолчанию — 16, а коэффициент загрузки по умолчанию — 0,75.
  2. HashSet h = новый HashSet (int initialCapacity);
    loadFactor по умолчанию 0,75
  3. HashSet h = новый HashSet (int initialCapacity, float loadFactor );
  4. HashSet h = новый HashSet (коллекция C);

Ниже программа иллюстрирует несколько основных операций HashSet:

   
// Java-программа для демонстрации работы HashSet

import java.util.*;

  

class Test

{

    public static void main(String[]args)

    {

        HashSet<String> h = new HashSet<String>();

  

        // Добавление элементов в HashSet usind 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"));

  

        // Удаление элементов из HashSet с помощью remove ()

        h.remove("Australia");

        System.out.println("List after removing Australia:"+h);

  

        // перебираем элементы хеша

        System.out.println("Iterating over list:");

        Iterator<String> i = h.iterator();

        while (i.hasNext())

            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
Все классы интерфейса Set внутренне поддерживаются Map. HashSet использует HashMap для внутреннего хранения своего объекта. Вам должно быть интересно, что для ввода значения в HashMap нам нужна пара ключ-значение, но в HashSet мы передаем только одно значение.

Хранение в HashMap
На самом деле значение, которое мы вставляем в HashSet, действует как ключ к объекту карты, и для его значения java использует постоянную переменную. Таким образом, в паре ключ-значение все ключи будут иметь одинаковое значение.

Реализация HashSet в Java-документе :

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();

Если мы посмотрим на метод add () класса HashSet:

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

Мы можем заметить, что метод add () класса HashSet внутренне вызывает метод put () для поддержки объекта HashMap, передавая указанный вами элемент в качестве ключа и константу «PRESENT» в качестве его значения.

Метод remove () также работает аналогичным образом. Внутренне вызывает метод удаления интерфейса Map.

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

Сложность времени операций HashSet: Базовая структура данных для HashSet является хеш-таблицей. Таким образом, амортизировать (в среднем или обычном случае) сложность времени для операций добавления, удаления и поиска (содержит метод) операции HashSet занимает O (1) времени.

Методы в HashSet:

  1. логическое добавление (E e) : используется для добавления указанного элемента, если он отсутствует, если он присутствует, вернуть false.
  2. void clear (): Используется для удаления всех элементов из набора.
  3. boolean contains (Object o): Используется для возврата true, если элемент присутствует в множестве.
  4. boolean remove (Object o): Используется для удаления элемента, если он присутствует в наборе.
  5. Iterator iterator (): используется для возврата итератора по элементу в наборе.
  6. boolean isEmpty (): Используется, чтобы проверить, является ли набор пустым или нет. Возвращает true для пустого и false для непустого условия для множества.
  7. int size (): Используется для возврата размера набора.
  8. Object clone (): используется для создания мелкой копии набора.

Ссылка: https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html

Эта статья предоставлена Dharmesh Singh . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

HashSet в Java

0.00 (0%) 0 votes