배열을 처음부터 훑으면 O(n)이지만, 해시는 키로 위치를 바로 계산해 평균 O(1)에 찾아가요. 코테에서 "느린 탐색"을 "즉시 조회"로 바꿔주는 강력한 무기, Map과 Set을 익혀요.
배열에서 어떤 값을 찾으려면 보통 처음부터 하나씩 비교해야 해요 → O(n). 해시는 다르게 접근해요. 키(key)를 해시 함수에 넣어 저장 위치(버킷)를 계산하고, 그 위치로 곧장 가요. 그래서 평균적으로 조회·삽입·삭제가 O(1)이에요.
Map·Set으로 보여드려요. 자바로 치면 각각 HashMap·HashSet에 대응해요. 논리는 언어가 달라도 똑같이 통해요.해시맵(Map)은 키(key)와 값(value)을 짝지어 저장하는 자료구조예요. 키로 값을 바로 꺼낼 수 있어요. 대표 메서드는 set(key, val) · get(key) · has(key)예요.
const scores = new Map();
scores.set("철수", 90); // 키 "철수" → 값 90 저장
scores.set("영희", 85); // 키 "영희" → 값 85 저장
scores.get("철수"); // 90 (키로 값을 바로 꺼냄)
scores.has("영희"); // true (키가 있나?)
scores.has("민수"); // false
scores.size; // 2 (저장된 쌍의 개수)get·set·has 모두 평균 O(1)이에요. 키만 알면 값이 어디 있든 한 번에 접근해요.
💡 없는 키를 get하면 undefined가 나와요. 그래서 값을 꺼내기 전에 has로 확인하거나, 기본값을 함께 처리하는 패턴을 자주 써요.
셋(Set)은 중복을 허용하지 않는 값들의 모음이에요. 값 자체를 키처럼 쓰는 셈이라, "이 값이 있나?"를 O(1)에 확인할 수 있어요. 메서드는 add · has · delete예요.
const s = new Set();
s.add(1);
s.add(2);
s.add(2); // 이미 있는 값 → 무시됨 (중복 저장 안 함)
s.add(3);
s.size; // 3 (1, 2, 3 — 2는 하나만!)
s.has(2); // true
s.delete(2); // 2 제거
s.has(2); // falseadd해도 하나만 들어가요. 그래서 위에서 size는 4가 아니라 3이에요.
💡 "고유한 값만 모으고 싶다", "이미 본 값인지 확인하고 싶다"면 Set이 정답이에요.
function countFreq(arr) {
const freq = new Map();
for (const x of arr) {
// 이미 있으면 +1, 없으면 0에서 시작해 +1
freq.set(x, (freq.get(x) || 0) + 1);
}
return freq;
}
// ["a","b","a"] → Map { "a" => 2, "b" => 1 }const arr = [1, 2, 2, 3, 3, 3];
const unique = [...new Set(arr)]; // [1, 2, 3]Set에 넣으면 중복이 저절로 사라져요. 다시 배열이 필요하면 [...set]으로 펼쳐요.
// two sum: 합이 target인 두 수가 있나?
function hasPair(arr, target) {
const seen = new Set();
for (const x of arr) {
// 짝(target - x)을 이미 봤다면 성공!
if (seen.has(target - x)) return true;
seen.add(x);
}
return false;
}has로 확인하면 전체가 O(n)이 돼요.
💡 핵심 감각 — "배열을 뒤지는 O(n) 탐색"이 보이면, "Map/Set의 O(1) 조회"로 바꿀 수 있는지 먼저 떠올려보세요. 코테의 단골 패턴이에요.
충돌(collision)은 서로 다른 키가 해시 함수 계산 결과 같은 위치(버킷)로 가는 상황이에요. 사물함 비유로 치면, 이름은 다른데 같은 번호가 나오는 경우죠.
set·get·has.add·has·delete. 같은 값은 하나만.