HashSet/HashMap의 내부 구조 및 중복 제거 메커니즘

HashSet은 Java Collections Framework의 핵심 구성 요소 중 하나로, 중복을 허용하지 않는 집합(Set) 자료구조를 구현한다.

 

1. HashSet의 주요 특징

• 중복 요소를 허용하지 않음 : 데이터 동등성 확인을 위한 equals(), hashCode() 메서드 필요
• 순서를 보장하지 않음 : 인덱스가 매개 변수로 넘어가는 메서드(get(int index), indexOf(Object o) 등)이 없음
• null 요소 허용 
• 비동기(non-synchronized) 구현
• O(1) 시간 복잡도의 기본 연산

2. 내부 구조 

2-1) 주요 필드

HashSet 필드

위의 코드에서 볼 수 있듯이 HashSet은 내부적으로 HashMap을 사용하여 구현한다.

HashSet은 요소들을 HashMap의 key로 저장한다.

모든 값에 대한 value로는 동일한 더미 객체(PRESENT)를 사용한다. (키의 존재 여부만 확인하면 되기 때문)

 

2-2) 생성자

1. HashSet() : 기본 생성자, 데이터를 저장할 수 있는 16개의 공간과 0.75의 로드 팩터를 갖는 객체 생성

2. HashSet(Collection<? extends E> c) : 매개 변수로 받은 컬랙션 객체의 데이터를 HashSet에 저장

3. HashSet(int initialCapacity) : 매개 변수로 받은 개수만큼의 데이터 저장 공간과 0.75의 로드 팩터를 갖는 객체 생성

4. HashSet(int initialCapacity, float loadFactor) : 첫 매개 변수로 받은 개수만큼의 데이터 저장 공간과 두 번째 매개 변수로 받은 만큼의 로드 팩터를 갖는 객체를 생성 

 

2-3) 메모리 구조

HashMap 다음과 같은 구조로 구성된다.

 

• 버킷 배열 (Node<K,V>[])
• 각 버킷의 연결 리스트 또는 트리 구조
• 메타데이터 (크기, 수정 횟수 등)

 

3. HashSet의 중복 제거 방식

3-1) 동작 방식

HashSet의 중복 제거 방식을 알아보기 위해 add() 메서드를 보자.

HashSet - add() 메서드

 

HashSet은 새로운 요소를 추가할 때 HashMap의 put() 메서드를 호출한다는 것을 알 수 있다.

HashMap - put() 메서드

put()은 만약 동일한 키가 이미 존재한다면 키의 대응하는 previous value를 리턴하고, 키가 존재하지 않으면 null을 리턴한다.

HashSet에서는 모든 value가 PRESENT로 동일하기 때문에, map.put()이 PRESENT를 리턴하면 동일한 key가 존재하는 것이다.

 

3-2) 해시

1. 객체의 hashCode() 호출

2. 해시 보완처리

3. 버킷 인덱스 계산

index = (n - 1) & hash

 

• n은 버킷 배열의 크기 (항상 2의 거듭제곱)
• hash는 계산된 해시값

3-3) putVal() 동작 

HashSet의 add() 메서드는 map.put()을 호출하고 내부적으로 HashMap의 putVal() 메서드를 호출한다.

 

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 1. 테이블 초기화 검사
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 2. 버킷 위치 계산 및 빈 버킷 처리
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 3. 키 중복 검사
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
            // 4. 트리 노드 처리
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 5. 연결 리스트 처리
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 6. 기존 값 갱신
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 7. 크기 관리
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

 

1. 테이블 초기화 검사
   • 테이블이 비어있으면 resize()를 통해 초기화
   • 기본 초기 크기는 16
2. 버킷 위치 계산
   • (n-1) & hash 연산으로 인덱스 계산
   • 비어있는 버킷이면 새 노드 직접 삽입
3. 키 중복 검사
   • 해시값 비교 (첫 필터링)
   • 레퍼런스 동일성 검사
   • equals() 메서드로 내용 비교
4. 트리 노드 처리
   • Red-Black 트리 구조 활용
   • 로그 시간 복잡도 보장
5. 연결 리스트 처리
   • 순차 탐색으로 중복 검사
   • 필요시 트리로 변환

4. 충돌 해결 방식

4-1) 연결 리스트(Separate Chaining)

• 동일한 버킷에 여러 노드를 연결 리스트로 저장
• 간단하지만 길이가 길어질 수 있는 단점

4-2 트리화(Tree Conversion)

버킷의 크기가 특정 임계값을 넘으면 Red-Black 트리로 변환

• TREEIFY_THRESHOLD = 8 (트리화 임계값)
• UNTREEIFY_THRESHOLD = 6 (역트리화 임계값)
• 최소 버킷 배열 크기 = 64

5. 성능 최적화

5-1) 로드 팩터(Load Factor)

static final float DEFAULT_LOAD_FACTOR = 0.75f;

 

 

• 공간과 시간의 트레이드오프
• 낮은 값: 빠른 검색, 많은 메모리
• 높은 값: 적은 메모리, 느린 검색

5-2) 리사이징(Resizing)

final Node<K,V>[] resize() {
    // 새 크기 계산
    // 모든 요소 재배치
    // 임계값 조정
}

주요 변수

Node<K,V>[] oldTab = table;  // 현재 테이블
int oldCap = (oldTab == null) ? 0 : oldTab.length;  // 현재 테이블 크기
int oldThr = threshold;  // 현재 임계값
int newCap, newThr = 0;  // 새로운 크기와 임계값

1. 새로운 크기 결정 

1-1) 기존 테이블이 있는 경우 (oldCap > 0)

if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {  // 최대 용량 도달
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
            oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1;  // 크기와 임계값을 2배로
}

1-2) 초기 생성 시 (oldCap == 0)

else if (oldThr > 0)  // 초기 용량이 임계값에 지정된 경우
    newCap = oldThr;
else {  // 기본값 사용
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

2. 데이터 재배치

if (e.next == null) // 단일 노드 처리
    newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof HashMap.TreeNode) //트리 노드 처리
    ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 링크드 리스트 처리
    HashMap.Node<K,V> loHead = null, loTail = null; //기존 인덱스
    HashMap.Node<K,V> hiHead = null, hiTail = null; //새 인덱스
    HashMap.Node<K,V> next;
    do { ... //노드 분할 로직 

 

 

6. HashSet, HashMap 비교

HashSet		HashMap
Set 인터페이스 구현	구현	Map 인터페이스 구현
객체(Objects)	저장 대상	key - value 쌍
비교적 느림	성능	빠름