[코딩테스트] 1. HashSet 기본 원리와 시간복잡도

HashSet은 중복을 허용하지 않는 집합 자료구조다. Java에서는 내부적으로 HashMap을 사용한다. 값을 넣으면 그 값의 해시값으로 저장 위치를 찾고, 같은 값이 이미 있으면 새로 추가하지 않는다.

HashSet이 하는 일

HashSet은 다음 질문에 빠르게 답한다.

이 값이 이미 등장했나?

그래서 HashSet은 다음 상황에 잘 맞는다.

• 중복 제거
• 방문 여부 체크
• 특정 값이 목록에 포함되는지 빠르게 확인
• 서로 다른 값의 개수 세기

반대로 다음 상황에는 부족하다.

• 같은 값이 몇 번 나왔는지 세기
• 값마다 점수, 인덱스, 상태를 저장하기
• 정렬된 순서로 꺼내기

왜 평균 O(1)인가

배열에서 값을 찾으려면 앞에서부터 비교해야 하므로 O(N)이다.

HashSet은 값을 바로 인덱스로 바꾸는 과정을 거친다.

값 → hashCode() → 배열 위치 → 같은 값인지 equals()로 확인

예를 들어 "leo"라는 문자열이 들어오면, Java는 "leo"의 해시값을 계산하고 그 해시값을 기반으로 내부 배열의 어느 칸을 볼지 결정한다. 그래서 모든 값을 순회하지 않고도 후보 위치로 바로 이동할 수 있다.

이 때문에 contains, add, remove가 평균적으로 O(1)이다.

해시 충돌

서로 다른 값이 같은 저장 위치로 몰릴 수 있다. 이를 해시 충돌이라고 한다.

충돌이 생기면 같은 칸 안에서 equals()로 실제 같은 값인지 다시 확인한다. 충돌이 적으면 빠르고, 충돌이 심하면 느려질 수 있다.

외우는 법은 다음처럼 잡으면 된다.

hashCode는 빠른 위치 후보 찾기
equals는 진짜 같은 값인지 확인

즉, HashSet은 해시값만 믿고 같은 값이라고 판단하지 않는다. 해시 위치를 찾은 뒤 실제 동등성 비교를 한다.

자주 쓰는 메서드와 시간복잡도

메서드	평균 시간복잡도	설명
add(value)	O(1)	값이 없으면 추가하고, 이미 있으면 추가하지 않는다
contains(value)	O(1)	값이 있는지 확인한다
remove(value)	O(1)	값이 있으면 제거한다
size()	O(1)	저장된 원소 개수를 반환한다
isEmpty()	O(1)	비었는지 확인한다
clear()	O(N)	전체 원소를 제거한다
순회	O(N)	저장된 원소를 한 번씩 방문한다
addAll(collection)	평균 O(M)	M개 원소를 하나씩 추가한다
removeAll(collection)	구현과 인자에 따라 다름	상대 컬렉션의 contains 비용에 영향을 받는다

removeAll은 특히 조심해야 한다. 상대 컬렉션이 ArrayList면 contains가 O(M)이라 전체가 커질 수 있다. 포함 여부를 빠르게 확인하려면 상대 컬렉션을 HashSet으로 바꿔두는 편이 안전하다.

기억하기 쉬운 원리

연산	왜 빠른가
추가	해시값으로 들어갈 위치를 바로 찾는다
탐색	해시값으로 확인할 위치를 바로 찾는다
삭제	해시값으로 삭제할 위치를 바로 찾는다
전체 순회	결국 모든 원소를 봐야 하므로 O(N)이다

HashSet은 "어디 있는지 바로 찍어보는 구조"라고 이해하면 된다. 반대로 "전체를 다 봐야 하는 작업"은 O(1)이 될 수 없다.

Java에서 주의할 점

순서가 보장되지 않는다

HashSet은 넣은 순서대로 나오지 않는다. 순서가 필요하면 다른 구조를 써야 한다.

필요한 순서	자료구조
삽입 순서 유지	LinkedHashSet
정렬 순서 유지	TreeSet
순서 필요 없음	HashSet

중복 개수를 저장하지 않는다

HashSet은 같은 값을 한 번만 저장한다.

Set<String> set = new HashSet<>();
set.add("mislav");
set.add("mislav");

System.out.println(set.size()); // 1

동명이인처럼 같은 값이 여러 번 등장할 수 있고 개수가 중요하면 HashMap<String, Integer>를 써야 한다.

기본 예시

Set<String> names = new HashSet<>();

names.add("leo");
names.add("kiki");

if (names.contains("leo")) {
    System.out.println("이미 등장한 이름");
}

names.remove("kiki");
System.out.println(names.size());

---