해시(HashMap) 자료구조 완벽 가이드: 코딩테스트 단골 무기

코딩테스트에서 "이거 O(n)으로 줄일 수 있나?" 싶을 때 가장 먼저 떠올려야 할 무기가 **해시맵(HashMap)**입니다. 탐색·삽입·삭제를 평균 O(1)에 처리하기 때문이죠. 원리와 빈출 패턴을 정리합니다.

해시맵은 어떻게 O(1)이 될까?

해시맵은 키(key)를 해시 함수에 넣어 나온 숫자를 배열의 인덱스로 사용합니다. 키 → 해시값 → 배열 위치로 바로 점프하기 때문에 전체를 훑지 않고도 값을 찾습니다.

• 키: 해시 함수의 입력 (문자열, 숫자 등)
• 해시 함수: 키를 정수 인덱스로 변환
• 버킷(bucket): 실제 값이 저장되는 배열 칸

이 덕분에 평균 조회·삽입이 **O(1)**입니다. 단, 어디까지나 "평균"입니다.

해시 충돌과 처리 방법

서로 다른 키가 같은 인덱스로 매핑되는 것을 **충돌(collision)**이라고 합니다. 대표 해결책 두 가지입니다.

• 체이닝(chaining): 같은 버킷에 연결 리스트로 값들을 매닮
• 개방 주소법(open addressing): 충돌 시 다음 빈 칸을 찾아 저장

충돌이 심해지면 한 버킷에 값이 몰려 최악 조회가 **O(n)**까지 나빠질 수 있습니다. 그래서 실제 구현은 적재율이 높아지면 배열을 키우는 **리사이징(rehashing)**을 합니다.

연산	평균	최악
탐색	O(1)	O(n)
삽입	O(1)	O(n)
삭제	O(1)	O(n)

빈출 패턴 1: Two Sum

"합이 target이 되는 두 수의 인덱스"를 찾는 고전 문제입니다. 이중 반복문이면 O(n²)이지만, 해시맵으로 "필요한 짝"을 기록하면 **한 번의 순회 O(n)**으로 끝납니다.

def two_sum(nums, target):
    seen = {}                 # 값 -> 인덱스
    for i, n in enumerate(nums):
        if target - n in seen:    # 짝이 이미 있으면
            return [seen[target - n], i]
        seen[n] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

빈출 패턴 2: 빈도수 세기

원소별 등장 횟수는 해시맵으로 한 번에 셉니다. 자바스크립트의 Map을 활용한 예시입니다.

function countFreq(arr) {
  const freq = new Map();
  for (const x of arr) {
    freq.set(x, (freq.get(x) || 0) + 1);
  }
  return freq;
}

console.log(countFreq(["a", "b", "a", "c", "b", "a"]));
// Map(3) { 'a' => 3, 'b' => 2, 'c' => 1 }

팁: 파이썬은 collections.Counter, defaultdict(int)를 쓰면 빈도수 코드를 더 짧게 짤 수 있습니다. 단순 존재 여부만 필요하면 set이 메모리·속도 면에서 더 낫습니다.

마무리 체크리스트

• 평균 O(1) 조회 → "있나 없나/몇 개냐/짝이 있나" 문제의 1순위 도구
• 충돌 때문에 **최악 O(n)**일 수 있음을 면접에서 언급하면 가점
• 존재 여부만 필요하면 set, 키-값 매핑이 필요하면 map
• 키는 변하지 않는(불변) 값이어야 함 — 리스트는 키로 못 쓰고 튜플은 가능

"완전탐색이 시간 초과면 해시맵을 떠올린다"를 습관으로 만드세요.