도서관에서 책 한 권을 찾을 때 첫 번째 서가부터 한 권씩 확인하는 사람은 없습니다. 책 제목을 정해진 규칙에 넣으면 "3층 D열 12번"이라는 자리가 바로 나오고, 그 자리로 곧장 갑니다. 책이 백 권이든 십만 권이든 자리를 계산하는 시간은 똑같습니다.
해시는 값 자체로부터 "그 값이 있어야 할 자리"를 계산해서, 찾는 일을 훑는 일이 아니라 계산 한 번으로 바꾸는 도구입니다.
배열에서 찾기: 앞에서부터 한 칸씩 확인 (원소가 많아지면 그만큼 느려짐)
해시에서 찾기: 자리를 계산 → 바로 확인 (원소가 많아져도 비슷한 시간)
[3, 5, 3, 7]에 중복이 있는지, "이미 본 값"을 적어 두는 수첩(Set) 하나로 확인해 봅니다.
단계
보는 값
수첩에 이미 있나
수첩 상태
시작
—
—
{}
1
3
없음
{3}
2
5
없음
{3, 5}
3
3
있음 → 중복 발견
{3, 5}
4
—
(여기서 종료)
—
핵심은 3단계입니다. 수첩이 없었다면 앞의 [3, 5]를 다시 훑어야 했지만, 수첩이 있으면 "있나?"를 한 번에 확인합니다. 원소를 한 번만 지나가므로 전체가 O(N)입니다.
해시 문제의 골격은 "빈 장부를 만들고 → 한 번 훑으며 기록하고 → 장부를 읽는다"입니다. 등장 횟수 세기로 따라가 봅니다.
빈 장부(Map)를 만듭니다 — 키는 세려는 대상, 값은 개수입니다.
const count = new Map<string, number>();
입력을 한 번 훑으며 기록합니다. 처음 보는 키는 개수가 undefined이므로 기본값 0을 반드시 깔아 줍니다.
for (const word of words) { count.set(word, (count.get(word) ?? 0) + 1);}
장부를 읽어 답을 만듭니다 — 가장 많이 나온 것, 한 번만 나온 것 등 질문에 맞게 훑습니다.
let best = "", bestCount = 0;for (const [word, c] of count) { if (c > bestCount) { best = word; bestCount = c; }}
전체 코드 — "가장 많이 등장한 단어와 그 횟수 구하기":
function solution(words: string[]): [string, number] { // 1단계: 장부 준비 const count = new Map<string, number>(); // 2단계: 한 번 훑으며 세기 for (const word of words) { count.set(word, (count.get(word) ?? 0) + 1); } // 3단계: 장부에서 답 뽑기 let best = "", bestCount = 0; for (const [word, c] of count) { if (c > bestCount) { best = word; bestCount = c; } } return [best, bestCount];}
TypeScript에서는 해시를 직접 구현할 일 없이 내장 자료구조를 씁니다.
도구
용도
핵심 메서드
Map<K, V>
키 → 값 (개수 세기, 인덱스 기억)
setgethasdelete
Set<T>
존재 여부만 (중복 검사, 방문 표시)
addhasdelete
객체 {}
문자열 키 한정 간이 Map
— 코테에선 Map 권장
다음 문장이 문제에 보이면 해시부터 떠올리세요.
"이미 나온 적 있는 값인지" → Set.has
"각 값이 몇 번 등장하는지" → Map으로 카운팅
"이 값과 짝이 되는 값 을 이전에 봤는지" → two-sum 패턴: 값→인덱스 Map
"두 배열/문자열이 같은 구성 인지" → 카운팅 후 비교 (애너그램)
O(N²) 이중 루프의 안쪽 루프가 "찾기"라면, 그 찾기를 해시로 바꿔 O(N)으로 만드는 것이 해시 문제의 본질입니다.
// 카운팅 — 등장 횟수 세기const count = new Map<string, number>();for (const word of words) { count.set(word, (count.get(word) ?? 0) + 1);}
// two-sum 패턴 — "짝을 이전에 봤는가"function twoSum(nums: number[], target: number): number[] { const seen = new Map<number, number>(); // 값 → 인덱스 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); } return [];}
// 그룹핑 — 정렬한 문자열을 키로 애너그램 묶기const groups = new Map<string, string[]>();for (const s of strs) { const key = [...s].sort().join(""); if (!groups.has(key)) groups.set(key, []); groups.get(key)!.push(s);}
count.get(k) + 1 — 키가 없으면 undefined + 1 = NaN. 반드시 ?? 0 기본값을 붙이세요
객체를 Map 대신 쓸 때 숫자 키가 문자열로 바뀌는 것을 잊음 (obj[1]과 obj["1"]은 같은 키)
Set에 배열/객체를 넣고 has([1,2])가 true이길 기대 — 참조 비교라 실패. JSON.stringify한 문자열을 키로
const seen = new Set<number[]>();seen.add([1, 2]);seen.has([1, 2]); // false — 다른 참조const seen2 = new Set<string>();seen2.add(JSON.stringify([1, 2]));seen2.has(JSON.stringify([1, 2])); // true
two-sum에서 자기 자신을 짝으로 셈 — "현재 값을 넣기 전에 먼저 찾는" 순서(위 코드)로 자연 해결
왜 평균 O(1)인가: 해시는 키를 해시 함수에 넣어 저장 위치를 즉시 계산합니다. 배열에서 값을 찾으려면 앞에서부터 뒤져야 하지만(O(N)), 해시는 "어디 있는지"를 계산으로 알아내므로 평균 O(1)에 넣고 찾고 지웁니다. 서로 다른 키가 같은 자리로 계산되는 충돌이 생기면 그 자리에 목록을 이어 붙이므로, 최악에는 O(N)까지 나빠질 수 있습니다.
Map vs 객체: Map은 삽입 순서를 보존하고 아무 타입이나 키로 쓸 수 있으며 size로 개수를 바로 얻습니다. 객체는 키가 항상 문자열로 강제되고 프로토타입 키(constructor 등)와 충돌할 여지가 있어 코테에서는 Map을 기본으로 두는 편이 안전합니다.
키 설계가 곧 풀이: 애너그램 그룹핑에서 "정렬한 문자열"을 키로 삼은 것처럼, 같아야 할 것들이 같은 키가 되도록 키를 만드는 순간 문제가 끝납니다. 좌표는 `${r},${c}`, 조합은 정렬 후 join이 흔한 키 설계입니다.
시각화로 "키 → 버킷" 흐름과 충돌 처리를 본 뒤, 중복 검사 → 카운팅 → two-sum 패턴 → 그룹핑 순으로 푸세요. 해시는 이 사이트에서 문제가 가장 많은 유형입니다 — 손에 완전히 익을 때까지.