HashSet

참고 링크
https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html

HashSet

java.lang.Object
    java.util.AbstractCollection<E>
        java.util.AbstractSet<E>
            java.util.HashSet<E>

Set<E> : 셋 데이터를 처리하는 것과 관련된 메서드를 지정
Cloneable : Object 클래스의 clone() 메서드가 제대로 수행될 수 있음을 지정
Serializable : 원격으로 객체를 전송, 파일 I/O 가능

Set 을 확장한 클래스이며, 무엇보다 중복을 허용하지 않기 때문에, 데이터가 같은지를 확인하는 것이 핵심이다.
때문에, equals() 메서드와 hashCode() 메서드는 값의 중복을 확인하는데, 매우 중요한 역할을 한다.
- equals() : 값이 같은지
- hashCode() : 레퍼런스가 같은지

생성자

HashSet() : 데이터를 저장할 수 있는 16개의 공간과, 0.75의 로드 팩터를 갖는 객체를 생성한다.
HashSet(Collection<? extends E> c) : 매개 변수로 받은 컬렉션의 객체의 데이터를 HashSet에 담는다.
HashSet(int initialCapacity) : 매개변수로 받은 개수만큼 데이터 저장 공간과 0.75의 로드 팩터를 갖는 객체를 생성한다.
HashSet(int initialCapacity, float loadFactor) : 첫번째 매개변수로 받은 개수만큼 데이터 저장 공간과, 두번째 매개변수로 받은 만큼의 로드팩터를 갖는 객체를 생성

로드팩터란?
로드팩터 = 데이터의 개수(Data size) / 저장 공간(Capacity)
만약 데이터의 개수가 증가해 로드팩터의 값이 본래 로드팩터 값(초기 지정)보다 커지면, 저장공간은 증가되고 해시 재정리 작업(rehashing)을 해야만 한다.
데이터가 해시 재정리 작업에 들어가면, 내부에 갖고 있는 자료 구조를 다시 생성하는 단계를 거쳐야 하기에 성능에 영향을 미친다.
로드 팩터가 낮을 때는 빠른 성능(검색/삽입/삭제)과 낮은 해시충돌 발생, 하지만 메모리 낭비가 있을 수 있다.
로드 팩터가 높을 때는 메모리 효율성을 좋지만, 해시 충돌이 많이 발생해 성능 저하(검색/삽입/삭제) 가능성이 높다.

데이터 저장 과정

1. HashMap 호출

HashSet 에 데이터가 저장될 때, 내부적으로 HashMap.put(E e, Boolean.TRUE) 의 형태로 HashMap 을 호출한다.

2. 해시값 계산

HashMap 내부에서 키값에 대해hashCode() 메서드를 사용하여 해시값을 계산한다.

3. 버킷 할당

해시값에 따라 요소가 저장될 버킷을 찾는다.
만약 해당 버킷이 비어있다면 요소를 버킷에 바로 저장한다.

4. 중복 확인

버킷에 이미 값이 존재한다면 equals() 메서드를 사용하여, true 를 리턴하면 저장하지 않고, false 를 리턴한다면 데이터를 저장한다.

5. 해시 충돌 처리

해시값이 같은 요소가 이미 버킷에 존재하는 경우, 충돌이 발생한다.
HashSet 은 체이닝(chaining) 방식을 사용하여, 같은 버킷에 LinkedList 를 사용하여 데이터를 저장한다.
Java 8 부터는 해시 충돌시, 기본적으로는 LinkedList 를 사용하지만, 버킷에 저장된 수가 8개 이상이 되면 red-block tree 를 사용한다.

주요 메서드 목록

boolean add(E e) : 데이터를 추가한다.
void clear() : 모든 데이터를 삭제한다.
Object clone() : HashSet 객체를 복사한다. 하지만 담겨 있는 데이터들은 복사하지 않는다.
boolean contains(Object o) : 지정한 객체가 존재하는지를 확인
boolean isEmpty() : 데이터가 있는지 확인한다.
Iterator<E> iterator() : 데이터를 꺼내기 위한 Iterator 객체를 리턴한다 .
boolean remove(Object o) : 매개 변수로 넘어온 객체를 삭제한다.
int size() : 데이터의 개수를 리턴한다.

예제

HashSet 은 중복이 제거되기는 하지만, 순서는 신경쓰지 않기 때문에, 아래 예제에서 순서가 바뀌어 나올 수도 있다.

public class SetSample {

    public static void main (String[] args){
        SetSample setSample = new SetSample();
        String[] test = new String[]{
          "a","a","b","b","c","c","d","d","e",
                "f","f","g","g","h","h","i","i","j",
                "k","k","l","l","m","m","n","n","n",
        };
        System.out.println(setSample.getTestKind(test));
    }
    
    public int getTestKind(String[] s){
        HashSet<String> hashSet = new HashSet<>();
        for(String string : s){
            hashSet.add(string);
        }

        return hashSet.size();
    }
}

추가적으로 Iterator 를 통해서도 결과를 얻을 수 있다.

public int getTestKind(String[] s){
    HashSet<String> hashSet = new HashSet<>();
    for(String string : s){
        hashSet.add(string);
    }

    Iterator<String> iterator = hashSet.iterator();
    while(iterator.hasNext()){
        System.out.println(iterator.next());
    }
    return hashSet.size();
}

HashSet 시간복잡도(해시 충돌 여부가 성능의 Key)

생성

최선 : O(1)
- 해시 충돌이 없는 상태
최악 : O(n)
- 해시 충돌이 많거나, rehasing 이 일어나는 경우

읽기

최선 : O(1)
- 해시 충돌이 없는 상태
최악 : O(n)
- 해시 충돌이 많은 경우

수정

중복을 허용하지 않기 때문에, 수정은 없다.

삭제

최선 : O(1)
- 해시 충돌이 없는 상태
최악 : O(n)
- 해시 충돌이 많은 경우

PreviousSet, Queue NextLinkedHashSet

Last updated 1 year ago