Hashset java доступ к элементу

Class HashSet

Type Parameters: E — the type of elements maintained by this set All Implemented Interfaces: Serializable , Cloneable , Iterable , Collection , Set Direct Known Subclasses: JobStateReasons , LinkedHashSet

This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element.

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:

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

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.

This class is a member of the Java Collections Framework.

Источник

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

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) – конструктор, добавляющий элементы из другой коллекции.

 import java.util.*; class Test < public static void main(String[]args) < HashSeth = new HashSet(); // Добавляем элементы в 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 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 вызывает метод put() у внутреннего объекта HashMap , передавая ему в качестве ключа добавляемый элемент, а в качестве значения – константу PRESENT. Сходным образом работает и метод remove() . В нем вызывается метод remove() внутреннего объекта HashMap :

 public boolean remove(Object o)

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 .

Источник

Java — how to get element from HashSet?

Tehya-Blanchard

1. Overview

In java Set / HashSet / LinkedHashSet don’t have get method.

Ofcourse it is possible to ‘GET’ element from Set in java, we just need to think a bit different when using this data structure. What I mean by this?

When we want to GET element from Set in java we just need to check if Set contains the object we want to get. So we already have our element we want to get from HashSet, the only think left to do is to check if Set have this object inside by using contains method with correctly implemented hashCode() and equals() .

HashSet internally uses HashMap and contains method on HashSet calls HashMap containsKey method.

Internally HashSet uses HashMap which looks like this:

private transient HashMap map;

We can go inside JDK and check it by ourselves.

The best way to understand what I mean is by analyzing below 2 examples.

When we use intellij IDEA we can just click on contains method and attach the debugger inside.

2. Example 1 — HashSet with String

This example uses String, String have internal hashCode and equals implemented in JDK.

import java.util.HashSet; import java.util.Set; public class JavaGetElementFromHashSetExample1 < public static void main(String[] args) < Setset = new HashSet<>(); set.add("A"); set.add("B"); set.add("C"); // get A // we already have String "A" // so we just only need to check if "A" exists in HashSet System.out.println(set.contains("A")); // true // get D System.out.println(set.contains("D")); // false > >

String — Internal hashCode and equals implemented in JDK.

public int hashCode() < int h = hash; if (h == 0 && value.length >0) < char val[] = value; for (int i = 0; i < value.length; i++) < h = 31 * h + val[i]; >hash = h; > return h; > public boolean equals(Object anObject) < if (this == anObject) < return true; >if (anObject instanceof String) < String anotherString = (String)anObject; int n = value.length; if (n == anotherString.value.length) < char v1[] = value; char v2[] = anotherString.value; int i = 0; while (n-- != 0) < if (v1[i] != v2[i]) return false; i++; >return true; > > return false; >

HashSet — contains JDK implementation (as we can see HashSet internally uses HashMap)

package java.util; public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable < // . private transient HashMapmap; // . public boolean contains(Object o) < return map.containsKey(o); >// . >

3. Example 2 — HashSet with custom User objects

In this example we implement explicit hashCode and equals for User class.

When we invoke contains method

import java.util.HashSet; import java.util.Objects; import java.util.Set; public class JavaGetElementFromHashSetExample2 < public static void main(String[] args) < Setset = new HashSet<>(); set.add(new User(1L, "A")); set.add(new User(2L, "B")); set.add(new User(3L, "C")); // get 1st user by checking if set contains our User object // User class implement custom hash code and equals method // we use key User(1L, "A") to 'get' user from Set // we already have this object so we just only need to check if // object is in our hash set System.out.println(set.contains(new User(1L, "A"))); // true // get 4th user System.out.println(set.contains(new User(4L, "D"))); // false > private static class User < private long userId; private String username; public User() < >public User(long userId, String username) < this.userId = userId; this.username = username; >public long getUserId() < return userId; >public void setUserId(long userId) < this.userId = userId; >public String getUsername() < return username; >public void setUsername(String username) < this.username = username; >@Override public boolean equals(Object o) < if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; User user = (User) o; return userId == user.userId && Objects.equals(username, user.username); >@Override public int hashCode() < return Objects.hash(userId, username); >@Override public String toString() < return "User'; > > >

Источник