해시맵·해시셋: 빠른 조회

한 줄 정의

키를 해시해 버킷에 넣어, 평균적으로 넣기·찾기·삭제가 O(1)인 자료구조입니다.
JS Map/Set, Python dict/set이 이에 해당합니다.

왜 배열 선형 탐색을 대체하나

arr.includes(x) / x in list는 O(n)입니다.
같은 질문을 n번 하면 O(n²)이 됩니다. 해시로 바꾸면 O(n)으로 내려갑니다.

패턴 1: 빈도

const freq = new Map();
for (const ch of s) {
  freq.set(ch, (freq.get(ch) || 0) + 1);
}

from collections import Counter
freq = Counter(s)

애너그램, 다수 원소, “k번 등장” 문제에 기본입니다.

패턴 2: 보완수 (Two Sum)

function twoSum(nums, target) {
  const seen = new Map(); // value → index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
}

한 번 훑으며 “예전에 본 보완수”를 찾습니다. O(n) 시간·O(n) 공간.

패턴 3: 방문·유일

seen = set()
for x in xs:
    if x in seen:
        return True  # 중복
    seen.add(x)

object vs Map (JS)

• 키에 __proto__ 같은 문자열이 올 수 있으면 Map이 안전
• 삽입 순서·.size가 필요하면 Map
• 단순 식별자 키면 plain object도 가능

함정

1. 해시 가능한 키 · Python에서 list는 dict 키가 될 수 없음 → tuple로
2. 평균 O(1) · 이론상 최악은 더 나쁠 수 있으나 테스트에서는 보통 평균을 가정
3. 순서 · 해시셋/맵에 순서 가정을 두지 말 것 (JS Set/Map은 삽입 순서를 지키지만, 알고리즘적으로 정렬과는 다름)
4. 공간 · 메모리를 시간으로 바꾼 대가

복잡도 표

투포인터와 선택

• 정렬해도 되고 공간 O(1)이 중요하면 투포인터
• 정렬 비용이 싫거나 인덱스가 필요하면 해시

둘 다 되는 문제가 많습니다. 제약(메모리·이미 정렬됨)을 보세요.