해시셋&해시맵 (HashSet & HashMap)

관련 문제

문제	난이도	핵심
10816번 — 숫자 카드 2	실버 IV	등장 횟수 카운트
1620번 — 나는야 포켓몬 마스터	실버 IV	양방향 매핑
14425번 — 문자열 집합	실버 III	포함 여부 확인
1764번 — 듣보잡	실버 IV	교집합
4195번 — 친구 네트워크	골드 II	Map + Union-Find

---

1. 개념

HashSet과 HashMap은 모두 해시 테이블(Hash Table) 기반의 자료구조다.

키를 해시 함수로 변환해 저장 위치를 결정하기 때문에 탐색/삽입/삭제가 평균 O(1)이다.

HashSet  = 값(Value)만 저장    → 중복 없는 집합
HashMap  = 키-값(Key-Value) 저장 → 키로 값을 빠르게 조회

---

2. HashSet vs HashMap

	HashSet	HashMap
저장 형태	값(Value)만	키(Key) - 값(Value)
중복	불허	키 중복 불허, 값 중복 허용
주요 용도	중복 제거, 포함 여부 확인	빈도 카운트, 키-값 매핑
내부 구조	HashMap 기반	해시 테이블
순서 보장	❌	❌

순서가 필요하면 LinkedHashSet / LinkedHashMap (삽입 순서),
정렬이 필요하면 TreeSet / TreeMap (오름차순) 을 사용한다.

---

3. 핵심 포인트 2가지

해시 충돌 — 최악의 경우 O(N)이 될 수 있다

서로 다른 키가 같은 해시값을 가지는 경우를 충돌(Collision) 이라 한다.
Java는 체이닝(Chaining) 방식으로 해결하며, 충돌이 많아지면 탐색이 O(N)까지 느려진다.
알고리즘 문제에서는 대부분 평균 O(1)로 가정하고 사용한다.

getOrDefault / containsKey로 안전하게 접근하라

HashMap에서 없는 키를 get하면 null을 반환한다.
int로 바로 받으면 NullPointerException이 발생하므로 getOrDefault를 습관화하라.

// ❌ 위험한 방식
int count = map.get(key);  // key 없으면 NullPointerException

// ✅ 안전한 방식
int count = map.getOrDefault(key, 0);

---

4. 코드

HashSet 기본 연산

Set<Integer> set = new HashSet<>();

set.add(1);          // 삽입
set.add(2);
set.add(2);          // 중복 → 무시됨

set.contains(2);     // 포함 여부 확인 → true
set.remove(1);       // 삭제
set.size();          // 원소 개수 → 1
set.isEmpty();       // 비어 있는지 확인

// 순회
for (int val : set) {
    System.out.println(val);
}

HashSet 집합 연산

Set<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3, 4));
Set<Integer> b = new HashSet<>(Arrays.asList(3, 4, 5, 6));

// 교집합
a.retainAll(b);   // a = [3, 4]

// 합집합
a.addAll(b);      // a = [1, 2, 3, 4, 5, 6]

// 차집합
a.removeAll(b);   // a = [1, 2]

HashMap 기본 연산

Map<String, Integer> map = new HashMap<>();

map.put("apple", 1);       // 삽입
map.put("banana", 2);
map.put("apple", 99);      // 키 중복 → 값 덮어씀

map.get("apple");           // 값 조회 → 99
map.getOrDefault("grape", 0);  // 없는 키 → 기본값 0 반환
map.containsKey("banana"); // 키 포함 여부 → true
map.containsValue(2);      // 값 포함 여부 → true
map.remove("banana");      // 삭제
map.size();                // 키 개수 → 1

// 순회
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " : " + entry.getValue());
}

빈도 카운트 패턴

// 각 원소의 등장 횟수 세기
Map<Integer, Integer> freq = new HashMap<>();

for (int num : arr) {
    freq.put(num, freq.getOrDefault(num, 0) + 1);
}

양방향 매핑 패턴

// 이름 ↔ 번호 양방향 조회 (1620번 포켓몬 류)
Map<String, Integer> nameToId = new HashMap<>();
Map<Integer, String> idToName = new HashMap<>();

nameToId.put("Pikachu", 1);
idToName.put(1, "Pikachu");

nameToId.get("Pikachu");  // → 1
idToName.get(1);          // → "Pikachu"

---

5. 시간복잡도

연산	평균	최악
add / put	O(1)	O(N)
contains / get	O(1)	O(N)
remove	O(1)	O(N)

최악은 해시 충돌이 모든 키에서 발생하는 경우로, 실제 문제에서는 평균 O(1)로 동작한다.

---

6. 주의사항

• 순서가 필요하면 LinkedHashSet / LinkedHashMap 을 사용하라. HashSet과 HashMap은 순서를 보장하지 않는다.
• int[] 같은 배열은 HashSet/HashMap의 키로 쓸 수 없다. 배열은 equals와 hashCode가 내용 기반이 아니라 참조 기반이기 때문이다. 키로 쓰려면 List<Integer> 또는 String으로 변환하라.
• map.put(key, map.get(key) + 1) 방식은 키가 없으면 NPE가 발생한다. 항상 getOrDefault로 초기값을 지정하라.
• HashMap은 키로 null을 허용한다. null 키가 하나 존재할 수 있으므로 의도치 않게 null이 키로 들어가지 않도록 주의하라.