contents

🔑 코딩 테스트를 위한 해싱(Hashing) 알고리즘 가이드 & 예제

해싱은 코딩 테스트나 알고리즘 문제 풀이에서 매우 중요한 주제입니다.
"빠른 조회", "중복 제거", "빈도 계산"과 같은 문제 풀이 트릭의 핵심에 있습니다.

1. 해싱(Hashing) 이란?

해싱은 정수, 문자열 등 입력 데이터를 **해시 함수(Hash Function)**를 이용해 고정 크기의 해시 코드로 변환하여, 빠른 검색/저장을 가능하게 하는 기법입니다.

• 해시 함수(Hash Function): 입력 데이터를 고정 크기(대개 정수)의 해시 코드로 변환
• 해시 테이블/셋(Hash Table/Set): 해시코드를 인덱스로 사용하여 검색·삽입·삭제 평균 O(1) 성능
• 충돌(Collision): 서로 다른 입력이 같은 해시코드를 가질 때 발생
  • 해결법: 체이닝(Chaining), 오픈 어드레싱(Open Addressing) 등

2. 주요 해시 자료구조

a. HashMap / HashSet (Java), Dictionary (Python)

• 빠른 추가, 검색, 삭제 지원
• 빈도 카운트, 존재 여부 체크, 중복 처리에 필수

Java 예시 – 숫자 빈도 카운트

int[] arr = {3, 5, 4, 3, 4, 3};
Map<Integer, Integer> map = new HashMap<>();
for (int num : arr)
    map.put(num, map.getOrDefault(num, 0) + 1);

if (map.containsKey(5)) { /* 존재 여부 확인 */ }

Java 예시 – 존재 여부만 체크

Set<Integer> set = new HashSet<>();
for (int num : arr) set.add(num);

boolean isPresent = set.contains(4);

b. 문자열의 빈도 카운트

String s = "programming";
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray())
    freq.put(c, freq.getOrDefault(c, 0) + 1);

👉 아나그램 검증, 중복 탐지, 슬라이딩 윈도우 등에 활용

3. 해싱 응용 예시

a. 중복 탐지

Set<Integer> seen = new HashSet<>();
for (int num : arr) {
    if (seen.contains(num)) { /* 중복 발견 */ }
    seen.add(num);
}

b. Two Sum 문제

Map<Integer, Integer> map = new HashMap<>();
for (int num : arr) {
    if (map.containsKey(target - num)) {
        // num과 target - num이 한 쌍
    }
    map.put(num, 1);
}

c. 부분합 = K 문제

• 누적합을 Key, 등장 횟수를 Value로 해시맵에 저장해 O(n) 풀이 가능

4. 해시 함수 설계 팁

직접 구현 시:

• 문자열: 다항 해싱(Polynomial Rolling Hash) 자주 사용

  hash = Σ (s[i] * p^i) mod M
  

• 튜플/배열: 요소 해시값 결합

int hash(String s) {
    int hash = 0, p = 31, M = 1_000_000_007;
    for (int i = 0; i < s.length(); i++)
        hash = (hash + s.charAt(i) * pow(p, i)) % M;
    return hash;
}

⚠️ 보통 Java/Python의 내장 HashMap/HashSet은 이미 안전한 해시 함수를 사용

5. 코딩 테스트에서 해싱이 자주 쓰이는 패턴

6. 충돌(Collision) 처리 방식

• 체이닝(Chaining): 같은 해시코드의 데이터를 연결리스트로 관리
• 오픈 어드레싱(Open Addressing): 충돌 시 다음 인덱스 탐색(선형/이차 탐사)
• 로드 팩터(Load Factor): 일정 비율 이상 차면 해시 테이블 크기를 재조정(Rehash)

Java, Python의 표준 해시 자료구조는 이런 과정을 자동 처리

7. 실수/주의사항 & 팁

• 해시코드만 비교로 동등성 판단 ❌ → 값 자체 비교 필수
• 변경 가능한 객체는 Key로 사용하지 말 것 (예: List 대신 Tuple/불변 객체)
• 복합 키는 구분자를 넣거나 Tuple로 저장
• Java에서는 .equals()와 .hashCode() 함께 재정의

8. 대표 해시 활용 문제 (코딩 테스트 빈출)

• 문자열에서 첫 번째로 중복되지 않는 문자 찾기
• 아나그램 그룹핑 (정렬된 문자열을 Key로)
• 부분합이 K인 부분배열 개수
• 가장 긴 연속 수열 찾기
• Two Sum
• 행복한 수(Happy Number) – Set으로 무한 루프 감지

9. 정리 표

💡 Tip:
대표 해시 패턴(중복 체크, 빈도수 계산, Two Sum, 부분합, 아나그램)을 반드시 손코딩으로 연습하세요.
Python dict/set, Java HashMap/HashSet API 사용법도 익숙해져야 합니다.

🗝️ 해시 테이블 충돌 처리(Collision Handling) – 심층 가이드 & 주요 기법

해시 테이블에서는 충돌(Collision) — 서로 다른 키가 동일한 인덱스에 매핑되는 상황 — 이 필연적으로 발생합니다.
견고한 충돌 처리는 테이블이 가득 차더라도, 또는 해시 함수가 완벽하지 않더라도, 빠른 저장/조회/삭제 성능을 유지하는 데 필수입니다.
아래는 코딩 테스트 관점에서 충돌 처리 기법, 원리, 장단점을 상세히 정리한 내용입니다.

1. 분리 체이닝(Separate Chaining)

• 원리: 해시 테이블의 각 슬롯이 연결 리스트(혹은 균형 트리)를 가리키고, 같은 해시 인덱스에 해당하는 모든 (Key, Value) 쌍을 그 리스트 안에 저장
• 동작 방식: 충돌 시 해당 인덱스의 리스트에 새 요소를 추가
• 조회: 인덱스로 접근한 뒤 리스트를 순회하며 키 탐색
• 삭제: 리스트에서 해당 키 제거
• 장점: 구현이 쉽고, 삭제 편리
• 단점: 외부 포인터/리스트로 인한 추가 메모리 사용, 체인이 길어지면 조회 속도 감소

예: 테이블 크기가 N이고, 해시가 key % size라면, 7과 14는 동일한 해시 슬롯 0으로 이동.
슬롯 0에는 연결 리스트 [7 → 14] 저장.

2. 오픈 어드레싱(Open Addressing)

모든 키를 테이블 배열 안에 직접 저장하며, 충돌 시 일정한 규칙(프로빙 순서)에 따라 다음 빈 슬롯을 탐색해 삽입.

종류:

a. 선형 탐사(Linear Probing)

• 탐사 순서: 슬롯 h가 차 있으면 (h+1) % size, (h+2) % size, … 순서대로 탐색
• 장점: 구현과 개념 간단, 캐시 친화적
• 단점: 1차 군집화(Primary Clustering) 문제로 키들이 몰려 속도가 느려질 수 있음

b. 이차 탐사(Quadratic Probing)

• 탐사 순서: (h+1²), (h+2²) … (mod size)
• 장점: 선형 탐사에 비해 군집화 감소
• 단점: 2차 군집화(Secondary Clustering) 가능성, 테이블 크기 조건(소수 등) 따라 모든 슬롯 탐색 못 할 수 있음

c. 이중 해싱(Double Hashing)

• 탐사 순서: 두 번째 해시 함수를 사용해 보폭(step) 결정
  next = (h + i * hash2(key)) % size
• 장점: 군집화 최소화, 균등 분포
• 단점: 보조 해시 함수 설계 필요, 구현 복잡

오픈 어드레싱 특징:

• 키를 테이블 안에만 저장
• 조회/삽입 시 동일한 프로빙 순서 사용
• 삭제 시 주의 필요: 삭제 마커 사용 or 뒤 요소 재배치 필요
• **로드 팩터(load factor)**가 낮을 때(≤0.75) 성능이 좋음

3. 기타 충돌 처리 기법

로빈 후드 해싱(Robin Hood Hashing)

• 충돌 시, 현재 키와 새 키의 “이상적인 슬롯으로부터 거리(probe distance)”를 비교하여, 더 먼 키를 뒤로 밀고 근접한 키를 앞으로 배치해 전체 평균 탐사 거리를 균등하게 유지
• 장점: 성능 예측 용이
• 단점: 삽입 과정 복잡

쿠쿠 해싱(Cuckoo Hashing)

• 각 키가 가능한 슬롯 두 개(두 개의 해시 함수로 결정)를 가짐
• 두 슬롯 다 차 있으면 기존 키를 “쫓아내고(kick)” 다른 슬롯으로 재배치, 필요시 반복
• 장점: O(1) 조회 보장
• 단점: 삽입이 복잡하고, 테이블 재해싱 필요할 수 있음

홉스콧치 해싱(Hopscotch Hashing)

• 선형 탐사와 유사하나, 각 슬롯 주변의 “이웃 집합(neighborhood)” 내에서 키 재배치 가능
  → 캐시 효율과 탐사 성능 향상

4. 비교 표 & 팁

• 체이닝: 높은 로드 팩터 허용 가능, 삭제 많을 경우 유리
• 오픈 어드레싱: 메모리 효율 높음, 하지만 로드 팩터 상승 시 성능 저하 → 조기 리사이징 필요
• 좋은 해시 함수와 적절한 테이블 크기 조정이 충돌 최소화의 핵심
• 변경 가능한 객체는 해시 키로 사용 지양, 항상 값 자체 비교로 동등성 판단

5. Java/Python에서의 충돌 처리

• Java HashMap: 분리 체이닝 기반 (Java 8부터 체인 길이 커지면 트리로 변환)
• Python dict/set: 3.3 버전부터 개선된 오픈 어드레싱 방식 사용

✅ 코딩 테스트 팁:
직접 해시 테이블 구현 문제가 나오면, 분리 체이닝과 오픈 어드레싱(선형 탐사) 두 가지는 손코딩 가능해야 합니다.

references