해시
해시는 키를 이용해 값을 빠르게 저장하고 조회하는 방식이다. 코딩테스트에서는 주로 빈도 카운팅, 중복 확인, 이미 본 값 조회, 값 사이의 관계 기록에 사용한다.
이 문서에서는 해시의 동작 원리와 시간복잡도를 이해하고, Java 구현 패턴을 문제 해결에 적용하는 방법을 정리한다.
목차
- 핵심 개념
- HashMap의 동작 원리
- 충돌 처리
- 시간·공간 복잡도
- 코딩테스트 실전 활용 팁
- HashSet 활용 예제
- 해시보다 다른 자료구조가 적합한 경우
- 대표 문제 해결 패턴
- 자주 하는 실수
- 대표 문제
- 참고 자료
1. 핵심 개념
해시 테이블은 키를 해시 함수에 넣어 얻은 해시값으로 저장 위치인 버킷을 결정한다.
key → hashCode() → 버킷 위치 → key-value 저장HashMap<K, V>: 키와 값을 연결한다.HashSet<E>: 값의 존재 여부와 중복을 관리한다.- 같은 키는 하나의 값에 대응한다.
- 서로 다른 키가 같은 버킷을 사용할 수 있는데, 이를 해시 충돌이라고 한다.
HashMap의 순회 순서는 보장되지 않는다.
예를 들어 문자열의 출현 횟수를 세면 문자열이 키, 출현 횟수가 값이 된다.
입력: ["apple", "banana", "apple"]
apple → 2
banana → 12. HashMap의 동작 원리
2.1 저장
put(key, value)의 흐름은 다음과 같다.
- 키의
hashCode()를 바탕으로 해시값을 계산한다. - 해시값으로 저장할 버킷을 찾는다.
- 버킷이 비어 있으면 새 엔트리를 저장한다.
- 버킷에 엔트리가 이미 있으면 저장된 해시값을 확인하고, 필요한 경우
equals()로 실제 키가 같은지 비교한다. - 같은 키라면 값을 교체하고, 다른 키라면 충돌 처리 구조에 추가한다.
2.2 조회
get(key)도 같은 방식으로 버킷을 찾는다. 해당 버킷 안에서 해시값과 equals()를 비교해 실제 키에 연결된 값을 반환한다.
따라서 직접 만든 객체를 키로 사용할 때는 equals()와 hashCode()가 일관되어야 한다.
a.equals(b)가 true이면
a.hashCode()와 b.hashCode()도 같아야 한다.키로 사용한 객체의 필드가 저장 후 바뀌어 해시값이 달라지면 조회에 실패할 수 있다.
2.3 용량과 재해싱
버킷이 지나치게 차면 충돌이 늘어나므로 HashMap은 용량을 확장하고 엔트리를 다시 배치한다. 이를 재해싱이라고 한다.
Java HashMap의 기본 로드 팩터는 0.75다. 일반적인 코딩테스트에서는 기본 설정으로 충분하지만, 원소 수가 매우 많고 예상 크기를 알고 있다면 초기 용량을 지정해 반복적인 확장을 줄일 수 있다.
3. 충돌 처리
서로 다른 키라도 같은 버킷에 배치될 수 있다.
key A ─┐
├─ 같은 버킷
key B ─┘이를 해결하는 대표적인 방식은 다음과 같다.
- 체이닝: 같은 버킷에 여러 엔트리를 연결해 저장한다.
- 개방 주소법: 충돌 시 다른 빈 버킷을 탐색한다.
Java의 HashMap은 체이닝 계열의 방식을 사용한다. Java 8 이후에는 한 버킷에 충돌이 많이 쌓이면 일부 조건에서 연결 리스트를 균형 트리로 바꿔 탐색 성능 저하를 줄인다.
충돌 자체는 오류가 아니다. 다만 해시값이 고르게 분산되지 않으면 한 버킷에 원소가 몰려 성능이 나빠질 수 있다.
4. 시간·공간 복잡도
| 연산 | 평균 | 최악의 경우 |
|---|---|---|
put | O(1) | O(N) |
get | O(1) | O(N) |
containsKey | O(1) | O(N) |
remove | O(1) | O(N) |
| 전체 순회 | O(capacity + N) | O(capacity + N) |
- 평균
O(1)은 해시값이 버킷에 고르게 분산된다는 전제다. - 충돌이 한곳에 집중되면 최악의 경우 선형 탐색이 필요할 수 있다.
- Java 8 이후 트리화된 버킷은 일부 충돌 상황에서 탐색 비용을 줄이지만, 코딩테스트 복잡도 설명에서는 보수적으로 최악
O(N)까지 고려한다. - 전체 순회는 저장된 엔트리 수
N뿐 아니라 버킷 배열의 용량capacity에도 영향을 받는다. N개의 서로 다른 키를 저장하면 공간복잡도는O(N)이다.
주의해야 할
O(N)메서드
containsValue(value)는 특정 값이 있는지 확인하기 위해 엔트리를 차례로 살펴보므로O(N)이 걸린다. 코딩테스트에서는 가급적 사용을 피하고, 조회할 값을 Key로 저장할 수 있는지 먼저 검토한다.
5. 코딩테스트 실전 활용 팁
5.1 대용량 데이터가 예상되면 초기 용량 지정하기
HashMap은 기본 용량 16과 로드 팩터 0.75를 사용한다. 저장된 엔트리가 임계값을 넘으면 용량을 2배로 늘리고 기존 엔트리를 다시 배치한다.
데이터가 10만 개라면 기본 설정에서는 용량이 16 → 32 → 64 → ... → 131,072 → 262,144로 여러 차례 증가할 수 있다. 용량 131,072의 임계값은 98,304이므로 10만 개를 저장하려면 한 번 더 확장된다. 예상 크기를 알고 있다면 초기 용량을 여유 있게 지정해 불필요한 재해싱 비용을 줄일 수 있다.
// 데이터 약 10만 개를 저장할 예정이라면 로드 팩터를 고려해 여유 있게 지정한다.
Map<String, Integer> map = new HashMap<>(135_000);Note
초기 용량을 지나치게 크게 잡으면 메모리를 낭비할 수 있다. 입력 규모가 작거나 불확실하다면 기본 생성자로도 충분하다.
5.2 getOrDefault()로 빈도 카운팅하기
코딩테스트에서 가장 자주 등장하는 해시 패턴은 값의 등장 횟수를 세는 것이다. 키가 없을 때는 기본값 0을 사용하고, 있으면 기존 값에 1을 더한다.
map.put("사과", map.getOrDefault("사과", 0) + 1);5.3 computeIfAbsent()로 복합 자료구조 관리하기
Map<String, List<Integer>>처럼 Value 자리에 리스트나 집합이 들어가는 구조에 유용하다. 키가 없을 때만 새 값을 만들고, 이미 있으면 기존 값을 가져온다.
Map<String, List<Integer>> groups = new HashMap<>();
groups.computeIfAbsent("GroupA", key -> new ArrayList<>()).add(10);5.4 Key로 불변 타입 사용하기
키에는 내부 값이 변하지 않는 String, Integer, Long 같은 불변 타입을 우선 사용한다.
6. HashSet 활용 예제
값에 대응하는 추가 정보가 필요 없다면 HashMap<T, Boolean>보다 HashSet<T>이 의도를 더 잘 드러낸다.
int[] numbers = {3, 1, 4, 1};
Set<Integer> seen = new HashSet<>();
for (int number : numbers) {
if (!seen.add(number)) {
System.out.println("중복: " + number);
}
}Set.add()는 새 값이면 true, 이미 존재하면 false를 반환한다.
7. 해시보다 다른 자료구조가 적합한 경우
| 상황 | 추천 자료구조 | 이유 |
|---|---|---|
키가 0, 1, 2... 처럼 작고 연속적인 숫자일 때 | 배열 (Array) | 굳이 해시를 안 써도 배열 인덱스가 가장 빠르고 단순함 |
| 데이터의 **정렬 순서(크기순)**가 필요할 때 | TreeMap 또는 정렬(Sort) | 일반 HashMap은 순서를 보장하지 않음 |
| 데이터를 넣은 순서 그대로 유지해야 할 때 | LinkedHashMap | 입력된 순서대로 사물함이 연결됨 |
| 최솟값 / 최댓값을 계속 반복해서 꺼내야 할 때 | 우선순위 큐 (PriorityQueue) | 힙(Heap) 구조가 최솟값/최댓값 탐색에 특화됨 |
8. 대표 문제 해결 패턴
| 패턴 | 저장 구조 | 핵심 | 대표 활용 |
|---|---|---|---|
| 빈도 카운팅 | Map<값, 횟수> | 각 값이 몇 번 나왔는가? | 구성 비교, 재료 확인, 최빈값, 경우의 수 |
| 존재·중복 확인 | Set<값> | 이 값을 이전에 본 적이 있는가? | 중복 탐지, 공통 원소, 방문 처리, 연속 수열 |
| 보완값 찾기 | Map 또는 Set | 현재 값과 짝이 되는 값이 저장되어 있는가? | target - x 조회, O(N²)을 평균 O(N)으로 개선 |
| 그룹화 | Map<그룹 키, 목록> | 같은 특성을 어떤 키로 표현할 것인가? | 애너그램, 카테고리별 묶기 |
| 두 개의 빈도 맵 | 값 → 횟수, 횟수 → 값의 개수 | 특정 횟수를 가진 값이 존재하는가? | 빈도 조회가 반복되는 문제 |
패턴 선택 기준
문제를 읽고 먼저 Key에 무엇을 저장할지, Value가 필요한지, 조회와 저장 중 무엇을 먼저 할지를 정한다. 그룹화 키는 같은 그룹이면 반드시 같아야 하며, 두 개의 빈도 맵을 사용할 때는 이전 횟수와 새 횟수를 모두 갱신한다.
9. 자주 하는 실수
HashMap의 순회 순서에 의존한다.get()이null일 때 키가 없는 경우와null값이 저장된 경우를 구분하지 않는다.- 사용자 정의 키의
equals()와hashCode()규칙이 일치하지 않는다. - 키로 사용한 가변 객체를 저장 후 변경한다.
- 빈도 감소 후 값이 0이 된 엔트리를 그대로 두어 후속 존재 여부 판단을 잘못한다.
- 해시를 사용했다는 이유만으로 무조건 최악
O(1)이라고 설명한다. - 키의 범위가 매우 작음에도 불필요하게
HashMap을 사용해 코드를 복잡하게 만든다.
10. 대표 문제
10.1 LeetCode
- Two Sum — 보완값 조회의 기본
- Valid Anagram — 문자 빈도 비교
- Group Anagrams — 정규화한 키로 그룹화
- Longest Consecutive Sequence —
HashSet과 시작점 판별
10.2 HackerRank
- Hash Tables: Ransom Note — 단어 빈도 차감
- Two Strings — 공통 문자의 존재 여부
- Frequency Queries — 값의 빈도와 빈도의 빈도를 함께 관리
Note
문제를 풀기 전에는 “키와 값에 무엇을 저장할지”, “조회 시점과 저장 시점 중 어느 것이 먼저인지”, “평균 및 최악 시간복잡도는 무엇인지”를 먼저 적어 본다. 실제 문제의 전체 정답 코드는 이 문서에 기록하지 않는다.