[DataStructure] HashSet (Java)

HashSet

참고링크

Module java.base
Package java.util
Class HashSet<E>
java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractSet<E>
java.util.HashSet<E>
Type Parameters:
E - the type of elements maintained by this set
All Implemented Interfaces:
Serializable, Cloneable, Iterable<E>, Collection<E>, Set<E>
Direct Known Subclasses:
JobStateReasons, LinkedHashSet
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, Serializable

설명

이 클래스는 해시 테이블(실제로는 HashMap 인스턴스)에 의해 지원되는 Set 인터페이스를 구현합니다.
집합의 반복 순서를 보장하지 않습니다. 특히 order가 시간이 지나도 일정하게 유지된다는 보장은 없습니다.
이 클래스는 null 요소를 허용합니다.

이 클래스는 해시 함수가 버킷 간에 요소를 적절하게 분산한다고 가정할 때 기본 작업(추가, 제거, 포함 및 크기 조정)에 대해 일정한 시간 성능을 제공합니다.
이 Set을 Iterating하려면 HashSet 인스턴스의 크기(요소 수)와 지원하는 HashMap 인스턴스의 "capacity"(버킷 수)의 합에 비례하는 시간이 필요합니다.
따라서 Iterator 성능이 중요한 경우 초기 용량을 너무 높게(또는 너무 낮게 로드 팩터) 설정하지 않는 것이 매우 중요합니다.

Note 이 구현은 동기화되지 않습니다.
여러 스레드가 hash set에 동시에 액세스하고 스레드 중 적어도 하나가 set를 수정하는 경우 외부에서 동기화되어야 합니다.
이것이 일반적으로 set을 자연스럽게 캡슐화 하는 일부 개체에서 동기화하여 수행됩니다.
그러한 개체가 없으면 Collections.synchronizedSet 메서드를 사용하여 set을 "wrapped"해야 합니다,

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

이 클래스의 iterator 메서드에 의해 반환된 iterator는 fail-fast입니다: iterator가 생성된 후 언제든지 set이 수정되면 iterator의 자체 제거 메서드를 통하지 않고 어떤 방식으로든 Iterator는 ConcurrentModificationException을 throw합니다. 따라서 동시 수정에 직면하여 iterator는 미래의 불확실한 시간에 임의적이고 비결정적인 동작의 위험을 감수하기보다는 빠르고 깔끔하게 실패합니다.

iterator의 fail-fast 동작은 일반적으로 동기화되지 않은 동시 수정이 있는 경우 확실한 보장을 하는 것이 불가능하기 때문에 보장할 수 없습니다. Fail-fast iterator는 최선을 다해 ConcurrentModificationException을 발생시킵니다. 따라서 정확성을 위해 이 예외에 의존하는 프로그램을 작성하는 것은 잘못된 것입니다. iterator의 fail-fast 동작은 버그를 감지하는 데만 사용해야 합니다.

이 클래스는 Java Collections Framework의 멤버입니다.

Set Interface를 구현했고 Set interfase는 Collection 인터페이스를 상속받았습니다.

Since

1.2

생성자

HashSet()
비어있는 새로운 set을 구축합니다. 지원하는 HashMap 인스턴스는 기본 초기 용량(16)과 로드 계수(0.75)를 가집니다.
HashSet​(int initialCapacity)
비어있는 새로운 set을 구축합니다. 지원하는 HashMap 인스턴스는 기본 초기 용량(initialCapacity)과 로드 계수(0.75)를 가집니다.
HashSet​(int initialCapacity, float loadFactor)
비어있는 새로운 set을 구축합니다. 지원하는 HashMap 인스턴스는 기본 초기 용량(initialCapacity)과 로드 계수(loadFactor)를 가집니다.
HashSet​(Collection<? extends E> c)
Constructs a new set containing the elements in the specified collection.
특정한 collection의 elements를 담고있는 새로운 set을 구축합니다.

메서드

boolean    add​(E e)    
만약 존재하는게 없을 경우 이 set에 특정 element를 추가합니다.
void    clear()    
이 set에 있는 elements들을 모두 제거합니다.
Object    clone()
이 HashSet 인스턴스의 얕은 복사본을 반환합니다. 요소 자체는 복제되지 않습니다.
boolean    contains​(Object o)    
만약 이 set에 특정 element가 있다면 true를 반환합니다.
boolean    isEmpty()    
만약 이 set에 elements가 하난도 없다면 true를 반환합니다.
Iterator<E>    iterator()    
이 set의 elements에 대한 iterator를 반환합니다.
boolean    remove​(Object o)    
만약 이 set에 특정 element가 존재한다면 이 set에 있는 해당 element를 제거합니다.
int    size()    
이 set에 있는 elements의 개수를 반환합니다.(이것은 cardinality라고 합니다.)
Spliterator<E>    spliterator()    
이 set의 element에 대해 [late-binding](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Spliterator.html#binding) 및 fail-fast [Spliterator](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Spliterator.html]를 만듭니다.

#### Methods declared in interface java.util.Collection ####
clear, containsAll, equals, hashCode, isEmpty, parallelStream, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray, toArray

#### Methods declared in interface java.lang.Iterable ####
forEach

사용법

package com.basic;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

public class HashSetExample {
    public static void main(String[] args){
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        HashSet<Integer> hashSet = new HashSet<>();

        int a = 10;

        hashSet.add(a);
        hashSet.add(2);
        hashSet.add(3);
        hashSet.addAll(arrayList);
        hashSet.remove(a);

        System.out.println("hashSet.isEmpty():"+hashSet.isEmpty());
        System.out.println("hashSet.size():"+hashSet.size());
        System.out.println("hashSet.toString():"+hashSet.toString());

        Iterator iterHashSet = hashSet.iterator();
        while(iterHashSet.hasNext()){
            System.out.println("hashSet key:"+iterHashSet.next());
        }
    }
}

시간복잡도

add(e) - O(1)
remove(e) - O(1)
contains(e) - O(1)

참고링크

공간복잡도

대부분의 Collection들은 O(n)
참고링크
참고링크