해시 테이블 동작 원리: O(1) 조회의 비밀

"Map은 왜 빠를까?" 답은 해시 테이블입니다. 키를 배열의 인덱스로 변환해, 평균 O(1)에 값을 찾습니다.

핵심 아이디어: 키 → 인덱스

배열에서 인덱스를 알면 즉시 접근할 수 있습니다. 해시 테이블은 해시 함수로 키를 인덱스로 바꿉니다.

hash("apple") = 5  -> table[5]에 저장
hash("banana") = 2 -> table[2]에 저장
조회: hash("apple") = 5 -> table[5] 즉시 반환 (O(1))

좋은 해시 함수는 빠르고, 값을 고르게 분산시켜야 합니다.

충돌(Collision): 같은 칸을 가리킬 때

다른 키가 같은 인덱스로 매핑되면 충돌입니다. 두 가지 해결법이 있습니다.

• 체이닝(Chaining): 각 칸에 연결 리스트를 두고 거기에 쌓는다
• 개방 주소법(Open Addressing): 비어 있는 다음 칸을 찾아 넣는다

table[5] -> ("apple", 1) -> ("grape", 9)   // 체이닝

충돌이 많아지면 한 칸에 여러 개가 몰려 조회가 O(n)에 가까워집니다.

리해싱과 부하율(Load Factor)

저장된 개수 / 버킷 수 = 부하율. 보통 0.7을 넘으면 배열을 키우고 **전부 다시 해싱(rehash)**합니다. 이 덕분에 평균 O(1)이 유지됩니다.

상황	시간복잡도
평균	O(1)
최악(충돌 폭주)	O(n)

실무 활용

// 배열 중복 제거: O(n)
const unique = [...new Set(arr)];

// 빈도수 세기: O(n)
const count = new Map();
for (const x of arr) count.set(x, (count.get(x) ?? 0) + 1);

// 두 수의 합 찾기: O(n) (이중 반복 O(n²) 대신)
const seen = new Set();
for (const x of arr) {
  if (seen.has(target - x)) return true;
  seen.add(x);
}

마무리 체크리스트

• 해시 테이블 = 키를 인덱스로 변환
• 충돌은 체이닝/개방주소법으로 해결
• 부하율 넘으면 리해싱으로 성능 유지
• 평균 O(1), 최악 O(n)
• 중복 제거·빈도수·존재 확인은 Set/Map으로

"이중 반복 대신 해시"는 코딩테스트 최적화의 기본 공식입니다.