[Java] HashSet

HashSet, java.util.HashSet, Java HashSet, 해시셋

정의

java.util.HashSet<E> 는 HashMap 을 백킹으로 사용하는 Set 구현. 내부적으로 모든 원소를 HashMap 의 key 로 저장하고, value 는 dummy 상수 PRESENT.

평균 O(1) 의 add/remove/contains. 순서는 보장되지 않는다. 가장 흔한 Set 구현.

내부 구조

public class HashSet<E> extends AbstractSet<E> implements Set<E>, ... {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object();

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
    public boolean contains(Object o) {
        return map.containsKey(o);
    }
    // ...
}

HashMap 의 모든 동작과 성능 특성을 그대로 물려받는다. capacity/loadFactor, treeify 같은 내용은 HashMap 참고.

복잡도

작업	평균	최악 (Java 8+)
add	O(1)	O(log n)
contains	O(1)	O(log n)
remove	O(1)	O(log n)
순회	O(n + capacity)	같음

null 허용

원소 하나는 null 가능 (HashMap 의 null key 처럼).

Set<String> s = new HashSet<>();
s.add(null);                     // OK
s.add(null);                     // false (이미 있음)
s.contains(null);                // true

Set.of(null) 은 NPE.

함정

HashMap 의 함정이 그대로 적용.

• 가변 객체 사용 금지
• equals / hashCode 규약 준수
• thread-safe 가 아님 → 동시성 필요 시 Collections.synchronizedSet 또는 ConcurrentHashMap.newKeySet()
• iterator 는 fail-fast iterator

참고

• Object
• Iterable
• Collection
• Set
• Map
• HashMap
• TreeSet
• ConcurrentHashMap