Ръководство за HashSet в Java

1. Общ преглед

В тази статия ще се потопим в HashSet. Това е една от най-популярните реализации на Set, както и неразделна част от Java Collections Framework.

2. Въведение в HashSet

HashSet е една от основните структури от данни в API на Java Collections .

Нека си припомним най-важните аспекти на това изпълнение:

  • Той съхранява уникални елементи и разрешава нули
  • Той е подкрепен от HashMap
  • Той не поддържа реда за вмъкване
  • Не е безопасно за нишки

Имайте предвид, че тази вътрешна HashMap се инициализира, когато се създаде екземпляр на HashSet :

public HashSet() { map = new HashMap(); }

Ако искате да влезете по-задълбочено в това как работи HashMap , можете да прочетете статията, фокусирана върху нея тук.

3. API

В този раздел ще разгледаме най-често използваните методи и ще разгледаме няколко прости примера.

3.1. добави ()

Методът add () може да се използва за добавяне на елементи към набор. Договорът за метод гласи, че елемент ще бъде добавен само когато вече не присъства в набор. Ако е добавен елемент, методът връща true, в противен случай - false.

Можем да добавим елемент към HashSet като:

@Test public void whenAddingElement_shouldAddElement() { Set hashset = new HashSet(); assertTrue(hashset.add("String Added")); }

От гледна точка на изпълнение, методът add е изключително важен. Подробностите за внедряването илюстрират как вътрешно работи HashSet и използва метода на пускане на HashMap :

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

На картата променливата е препратка към вътрешния, за архивиране на HashMap:

private transient HashMap map;

Би било добра идея първо да се запознаете с хеш кода, за да разберете подробно как са организирани елементите в базирани на хеш структури от данни.

Обобщавайки:

  • А HashMap е масив от кофи с капацитет по подразбиране от 16 елемента - всяка кофа съответства на различна стойност хеш-код
  • Ако различните обекти имат една и съща стойност на хеш-код, те се съхраняват в една група
  • Ако се достигне коефициентът на натоварване , се създава нов масив два пъти по-голям от предишния и всички елементи се преизчисляват и преразпределят между новите съответни групи
  • За да извлечем стойност, хешираме ключ, модифицираме го и след това отиваме в съответната група и търсим в потенциалния свързан списък в случай, че има повече от един обект

3.2. съдържа()

Целта на метода contains е да провери дали даден елемент присъства в даден HashSet . Връща true, ако елементът бъде намерен, иначе false.

Можем да проверим за елемент в HashSet :

@Test public void whenCheckingForElement_shouldSearchForElement() { Set hashsetContains = new HashSet(); hashsetContains.add("String Added"); assertTrue(hashsetContains.contains("String Added")); }

Всеки път, когато даден обект бъде предаден на този метод, се изчислява хеш стойността. След това съответното местоположение на кофа се разрешава и преминава.

3.3. Премахване()

Методът премахва посочения елемент от набора, ако той присъства. Този метод връща true, ако набор съдържа посочения елемент.

Нека да видим работещ пример:

@Test public void whenRemovingElement_shouldRemoveElement() { Set removeFromHashSet = new HashSet(); removeFromHashSet.add("String Added"); assertTrue(removeFromHashSet.remove("String Added")); }

3.4. изчисти ()

Използваме този метод, когато възнамеряваме да премахнем всички елементи от набор. Основната реализация просто изчиства всички елементи от основната HashMap.

Нека да видим това в действие:

@Test public void whenClearingHashSet_shouldClearHashSet() { Set clearHashSet = new HashSet(); clearHashSet.add("String Added"); clearHashSet.clear(); assertTrue(clearHashSet.isEmpty()); }

3.5. размер ()

Това е един от основните методи в API. Използва се интензивно, тъй като помага при идентифицирането на броя на елементите, присъстващи в HashSet . Основната реализация просто делегира изчислението на метода size () на HashMap .

Нека да видим това в действие:

@Test public void whenCheckingTheSizeOfHashSet_shouldReturnThesize() { Set hashSetSize = new HashSet(); hashSetSize.add("String Added"); assertEquals(1, hashSetSize.size()); }

3.6. празно е()

Можем да използваме този метод, за да разберем дали даден екземпляр на HashSet е празен или не. Този метод връща true, ако наборът не съдържа елементи:

@Test public void whenCheckingForEmptyHashSet_shouldCheckForEmpty() { Set emptyHashSet = new HashSet(); assertTrue(emptyHashSet.isEmpty()); }

3.7. итератор ()

Методът връща итератор върху елементите в Set . Елементите се посещават без определен ред и итераторите са бързи .

Тук можем да наблюдаваме реда на случайните итерации:

@Test public void whenIteratingHashSet_shouldIterateHashSet() { Set hashset = new HashSet(); hashset.add("First"); hashset.add("Second"); hashset.add("Third"); Iterator itr = hashset.iterator(); while(itr.hasNext()){ System.out.println(itr.next()); } }

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.

Let's see that in action:

@Test(expected = ConcurrentModificationException.class) public void whenModifyingHashSetWhileIterating_shouldThrowException() { Set hashset = new HashSet(); hashset.add("First"); hashset.add("Second"); hashset.add("Third"); Iterator itr = hashset.iterator(); while (itr.hasNext()) { itr.next(); hashset.remove("Second"); } } 

Alternatively, had we used the iterator's remove method, then we wouldn't have encountered the exception:

@Test public void whenRemovingElementUsingIterator_shouldRemoveElement() { Set hashset = new HashSet(); hashset.add("First"); hashset.add("Second"); hashset.add("Third"); Iterator itr = hashset.iterator(); while (itr.hasNext()) { String element = itr.next(); if (element.equals("Second")) itr.remove(); } assertEquals(2, hashset.size()); }

The fail-fast behavior of an iterator cannot be guaranteed as it's 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'd be wrong to write a program that depended on this exception for its correctness.

4. How HashSet Maintains Uniqueness?

When we put an object into a HashSet, it uses the object's hashcode value to determine if an element is not in the set already.

Each hash code value corresponds to a certain bucket location which can contain various elements, for which the calculated hash value is the same. But two objects with the same hashCode might not be equal.

So, objects within the same bucket will be compared using the equals() method.

5. Performance of HashSet

The performance of a HashSet is affected mainly by two parameters – its Initial Capacity and the Load Factor.

The expected time complexity of adding an element to a set is O(1) which can drop to O(n) in the worst case scenario (only one bucket present) – therefore, it's essential to maintain the right HashSet's capacity.

An important note: since JDK 8, the worst case time complexity is O(log*n).

The load factor describes what is the maximum fill level, above which, a set will need to be resized.

We can also create a HashSet with custom values for initial capacity and load factor:

Set hashset = new HashSet(); Set hashset = new HashSet(20); Set hashset = new HashSet(20, 0.5f); 

In the first case, the default values are used – the initial capacity of 16 and the load factor of 0.75. In the second, we override the default capacity and in the third one, we override both.

A low initial capacity reduces space complexity but increases the frequency of rehashing which is an expensive process.

On the other hand, a high initial capacity increases the cost of iteration and the initial memory consumption.

As a rule of thumb:

  • A high initial capacity is good for a large number of entries coupled with little to no iteration
  • A low initial capacity is good for few entries with a lot of iteration

It's, therefore, very important to strike the correct balance between the two. Usually, the default implementation is optimized and works just fine, should we feel the need to tune these parameters to suit the requirements, we need to do judiciously.

6. Conclusion

In this article, we outlined the utility of a HashSet, its purpose as well as its underlying working. We saw how efficient it is in terms of usability given its constant time performance and ability to avoid duplicates.

We studied some of the important methods from the API, how they can help us as a developer to use a HashSet to its potential.

As always, code snippets can be found over on GitHub.