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

Вывод:

[South Africa, Australia, India]
List contains India or not:true
List after removing Australia:[South Africa, India]
Iterating over list:
South Africa
India

Все классы, реализующие интерфейс 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:https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html