3주차 Unit 3.4 — 충돌 해결법 2: 오픈 어드레싱 (Open Addressing)

Psj·2026년 5월 19일

F-lab

목록 보기
87/240

Unit 3.4 — 충돌 해결법 2: 오픈 어드레싱 (Open Addressing)

F-LAB JAVA · 3주차 · Phase 3 · 해시(Hash)의 원리
🎯 마스터 프롬프트 깊이 Unit — 🏆 Phase 3 완주

📌 학습 목표

이 Unit을 끝내면 다음을 답할 수 있어야 한다.

  • 오픈 어드레싱 의 정확한 메커니즘과 체이닝과의 차이는?
  • 선형 탐사 (Linear Probing) 의 동작과 클러스터링 문제는?
  • 이차 탐사 (Quadratic Probing) 가 선형 탐사를 어떻게 개선하나?
  • 이중 해싱 (Double Hashing) 의 메커니즘은?
  • Robin Hood Hashing 의 영리한 발상은?
  • 삭제의 함정 (Tombstone) 이 무엇이고 왜 발생하나?
  • 클러스터링 (Clustering) 의 1차 vs 2차 차이는?
  • Python dict, 자바 EnumMap, IdentityHashMap, ThreadLocalMap 의 구현은?
  • 오픈 어드레싱 HashMap 을 처음부터 구현할 수 있나?
  • 체이닝 vs 오픈 어드레싱 의 결정적 선택 기준은?

🎯 핵심 한 문장

오픈 어드레싱은 "충돌 시 다른 빈 버킷을 찾아 저장" 하는 해결법이다.
Node 객체 없이 배열만 사용해 메모리 효율과 캐시 효율이 뛰어나지만,
클러스터링과 삭제의 복잡성 이라는 대가가 있다.
Python, Ruby, Rust 의 dict/HashMap 은 모두 오픈 어드레싱을 채택했고,
자바도 EnumMap, IdentityHashMap, ThreadLocalMap 에서 이 방식을 사용한다.

비유 — 만석 식당의 자리 찾기

체이닝 (한 테이블에 여러 명):
  좌석 5번 가족 도착 → 좌석 5번 합석
  좌석 5번에 또 다른 가족 → 또 합석
  → 좌석 5번이 점점 붐빔

오픈 어드레싱 (다음 빈 테이블로):
  좌석 5번 가족 → 좌석 5번 차있음 → 좌석 6번 시도
  좌석 6번도 차있음 → 좌석 7번 시도
  좌석 7번 비어있음 → 거기 앉음
  → 모든 좌석이 골고루

→ 오픈 어드레싱: 공간 효율 + 캐시 친화 + 클러스터링 위험.

🧭 9개 섹션 로드맵

1. 오픈 어드레싱의 정의와 기본 원리
2. 선형 탐사 (Linear Probing)
3. 이차 탐사 (Quadratic Probing)
4. 이중 해싱 (Double Hashing)
5. Robin Hood Hashing — 영리한 변형
6. 삭제의 함정 — Tombstone
7. 자바와 다른 언어의 실제 구현
8. 직접 구현하는 OpenAddressingMap
9. 체이닝 vs 오픈 어드레싱 + Phase 3 완주

1️⃣ 오픈 어드레싱의 정의와 기본 원리

1.1 오픈 어드레싱의 정의

오픈 어드레싱 (Open Addressing):
  
  충돌 발생 시, 다른 자료구조 (연결 리스트 등) 없이
  배열 내의 다른 빈 슬롯을 찾아 저장하는 방법.

영어 별칭:
  - Open Addressing
  - Closed Hashing
  (혼란스러운 용어 — 체이닝과 반대)

핵심 아이디어:
  "한 슬롯만 차지" — 보조 자료구조 없이 배열만 사용

1.2 탐사 (Probing) 의 개념

탐사 (Probing):
  
  충돌 발생 시 다음 위치를 결정하는 알고리즘.

탐사 시퀀스 (Probe Sequence):
  h₀(k), h₁(k), h₂(k), ...
  
  h_i(k) = (h(k) + f(i)) mod m
  
  - h(k): 기본 해시값
  - f(i): 탐사 함수 (i 번째 시도의 오프셋)
  - m: 테이블 크기

종류:
  1. 선형 탐사: f(i) = i
  2. 이차 탐사: f(i) = i²  
  3. 이중 해싱: f(i) = i × h₂(k)

1.3 체이닝과의 시각적 비교

체이닝:
  table[5]: Node("A") → Node("B") → Node("C") → null
  table[6]: null
  table[7]: null
  
  → 한 슬롯에 여러 노드, 별도 자료구조

오픈 어드레싱:
  table[5]: "A"
  table[6]: "B"  (h("B") = 5, 충돌 → 다음으로)
  table[7]: "C"  (h("C") = 5, 충돌 → 또 다음으로)
  
  → 모든 슬롯에 단일 키-값

1.4 LoadFactor 의 다른 의미

체이닝:
  LoadFactor = n / m
  - 한 슬롯에 평균 노드 수
  - 1.0 이상도 가능
  - 0.75 가 일반적

오픈 어드레싱:
  LoadFactor = n / m
  - "사용 중인 슬롯의 비율"
  - 0.5 ~ 0.75 권장
  - 0.9 이상이면 성능 급락
  - 1.0 이면 빈 슬롯 없음 → 무한 루프!

1.5 오픈 어드레싱의 4가지 강점

1. 메모리 효율
   - Node 객체 없음
   - 배열만 사용
   - 약 30-50% 메모리 절약

2. 캐시 효율 ↑
   - 연속 메모리 접근
   - CPU 캐시 라인 활용
   - 작은 데이터에서 매우 빠름

3. 단순한 구조
   - 배열 + 인덱스만
   - 포인터 추적 없음
   - 분기 예측 잘됨

4. 빠른 순회
   - 배열 순회 = 매우 빠름
   - 연결 리스트보다 효율

1.6 오픈 어드레싱의 4가지 약점

1. 클러스터링 (Clustering)
   - 충돌이 누적되면 같은 영역에 집중
   - 새 탐사가 더 길어짐
   - 선형 탐사의 큰 문제

2. 삭제의 복잡성
   - 단순 삭제 시 탐사 체인 깨짐
   - Tombstone (삭제 마커) 필요
   - 또는 재해싱

3. LoadFactor 제약
   - 0.75 이상 권장 안 함
   - 더 많은 메모리 필요

4. 트리 변환 어려움
   - 연결 리스트 없으므로 트리 만들 위치 없음
   - 다른 방법으로 최악 대응

1.7 자바와 다른 언어의 채택

오픈 어드레싱 채택:
  - Python: dict (선형 탐사 변형)
  - Ruby: Hash (Ruby 2.4+)
  - Rust: HashMap (Robin Hood, SwissTable)
  - Go: map (변형된 오픈 어드레싱)
  - C# .NET: Dictionary (chaining 이지만 일부 오픈 어드레싱)
  - 자바 EnumMap, IdentityHashMap, ThreadLocal.ThreadLocalMap

체이닝 채택:
  - 자바 HashMap, HashSet
  - C++ std::unordered_map (대부분 구현)
  - 자바 Hashtable, ConcurrentHashMap

1.8 자기 점검 답변

오픈 어드레싱이 체이닝과 결정적으로 다른 점 3가지는?

답:
1. 노드 객체 없음 — 배열만 사용
2. 탐사 (Probing) — 충돌 시 다른 슬롯 찾기
3. LoadFactor 제약 — 1.0 이상 불가, 0.5~0.75 권장

추가:

  • 캐시 효율 ↑
  • 클러스터링 위험
  • 삭제 시 tombstone 필요

2️⃣ 선형 탐사 (Linear Probing)

2.1 선형 탐사의 정의

선형 탐사 (Linear Probing):

  충돌 시 한 칸씩 다음 슬롯으로 이동하며 빈 곳 찾기.

탐사 시퀀스:
  h₀(k) = h(k) mod m
  h_i(k) = (h(k) + i) mod m  for i = 0, 1, 2, ...

코드:
  int idx = hash(key) % m;
  while (table[idx] != null && !table[idx].key.equals(key)) {
      idx = (idx + 1) % m;
  }

2.2 선형 탐사 동작 시각화

초기 상태: capacity 16

put("A"): h("A") = 5
  table[5] 비어있음 → 저장
  table[5]: ("A", 1)

put("B"): h("B") = 5 (충돌!)
  table[5] 차있음 → table[6] 시도
  table[6] 비어있음 → 저장
  table[6]: ("B", 2)

put("C"): h("C") = 5 (또 충돌!)
  table[5] 차있음 → table[6] 시도
  table[6] 차있음 → table[7] 시도
  table[7] 비어있음 → 저장
  table[7]: ("C", 3)

put("D"): h("D") = 7 (인덱스 충돌!)
  table[7] 차있음 → table[8] 시도
  table[8] 비어있음 → 저장
  table[8]: ("D", 4)

결과:
  table[5]: ("A", 1)
  table[6]: ("B", 2)  ← 원래 5 였음
  table[7]: ("C", 3)  ← 원래 5 였음
  table[8]: ("D", 4)  ← 원래 7 이었음
  
  → 연속 4 칸 사용 = "1차 클러스터"

2.3 검색 동작

get("B"):
  h("B") = 5
  table[5] 확인: 키 "A" → 다음
  table[6] 확인: 키 "B" → 매칭!
  → 반환 ("B", 2)

get("Z"):
  h("Z") = 5
  table[5] → "A" 다름
  table[6] → "B" 다름
  table[7] → "C" 다름
  table[8] → "D" 다름
  table[9] → null
  → 빈 슬롯 도달 → 없음, null 반환

핵심:
  null 슬롯 만날 때까지 또는 매칭 발견까지 순회
  → 클러스터가 크면 검색이 느림

2.4 1차 클러스터링 (Primary Clustering)

1차 클러스터:
  연속된 슬롯들이 사용 중인 영역.
  
  table[5], table[6], table[7], table[8] 모두 사용 중
  → 4칸 클러스터

문제:
  새로운 키도 이 영역에 합류 가능성 ↑
  → h(key) = 5, 6, 7, 8 중 하나면 추가
  → 클러스터가 점점 커짐 (눈덩이 효과)

성능 영향:
  클러스터 크기 c 일 때:
  - 평균 탐사 거리 ≈ c/2
  - 클러스터가 길어질수록 탐사 비용 ↑

2.5 선형 탐사의 성능 (Knuth 분석)

Donald Knuth 의 분석 (1963):

평균 탐사 횟수:
  - 검색 성공: (1/2) × (1 + 1/(1-α))
  - 검색 실패: (1/2) × (1 + 1/(1-α)²)

여기서 α = LoadFactor

α = 0.5:
  - 성공: 1.5
  - 실패: 2.5

α = 0.75:
  - 성공: 2.5
  - 실패: 8.5  ← 급증

α = 0.9:
  - 성공: 5.5
  - 실패: 50.5  ← 매우 느림

α = 0.95:
  - 성공: 10.5
  - 실패: 200.5  ← 거의 사용 불가

→ LoadFactor 0.75 이하 유지 필수.
→ 그래서 자바의 EnumMap 도 빈 슬롯 충분히 확보.

2.6 선형 탐사의 강점

1. 매우 단순
   - "다음 칸으로" 단일 규칙
   - 코드 간결

2. 캐시 친화적 ★
   - 연속 메모리 접근
   - CPU 캐시 라인 (64 bytes) 활용
   - 다른 탐사 방법보다 빠름

3. 메모리 효율
   - 추가 자료구조 없음
   - 배열만

4. 구현 단순

2.7 선형 탐사의 약점

1. 1차 클러스터링 ★★★
   - 가장 큰 문제
   - 충돌이 누적되면 성능 급락

2. 삭제 복잡
   - 삭제 시 탐사 체인 깨짐
   - Tombstone 필요 (섹션 6)

3. LoadFactor 민감
   - 0.5 이상에서 성능 저하 가속

2.8 캐시 친화적 이유

CPU 캐시 라인 (보통 64 bytes):
  
  배열 슬롯이 4 bytes 라면:
  한 캐시 라인에 16 슬롯
  
  선형 탐사:
    table[5] 접근 → 캐시에 [0..15] 로드
    table[6], [7], [8] 모두 캐시 히트 ★
  
  체이닝:
    table[5] 접근 → 캐시에 일부 로드
    Node 의 next 따라가기 → 다른 메모리 영역 → 캐시 미스

→ 작은 데이터셋에서 선형 탐사가 체이닝보다 매우 빠른 이유.

2.9 자기 점검 답변

선형 탐사의 가장 큰 문제와 그 해결 방향은?

답:

  • 가장 큰 문제: 1차 클러스터링

    • 연속 슬롯이 사용되면 새 키도 합류
    • 클러스터 크기가 눈덩이로 늘어남
    • LoadFactor 0.75 에서도 평균 탐사 2.5회

  • 해결 방향:

    • 이차 탐사 (탐사 거리를 i² 로)
    • 이중 해싱 (탐사 거리를 다른 해시로)
    • Robin Hood Hashing (탐사 우선순위 조정)
    • 또는 단순히 LoadFactor 낮게 유지 (< 0.5)

3️⃣ 이차 탐사 (Quadratic Probing)

3.1 이차 탐사의 정의

이차 탐사 (Quadratic Probing):

  탐사 거리를 i² (또는 i² + i 등) 로 늘리는 방법.

탐사 시퀀스:
  h_i(k) = (h(k) + c₁·i + c₂·i²) mod m
  
  단순화: h_i(k) = (h(k) + i²) mod m
  for i = 0, 1, 2, 3, ...

이차 함수의 효과:
  i = 0: +0
  i = 1: +1
  i = 2: +4
  i = 3: +9
  i = 4: +16
  i = 5: +25
  ...
  → 점점 멀리 점프

3.2 이차 탐사 동작 시각화

초기: capacity 16

put("A"): h("A") = 5
  table[5] 비어있음 → 저장

put("B"): h("B") = 5 (충돌!)
  i = 1: (5 + 1²) % 16 = 6
  table[6] 비어있음 → 저장

put("C"): h("C") = 5 (충돌!)
  i = 1: (5 + 1) = 6, 차있음
  i = 2: (5 + 4) = 9
  table[9] 비어있음 → 저장

put("D"): h("D") = 5 (또 충돌!)
  i = 1: (5 + 1) = 6, 차있음
  i = 2: (5 + 4) = 9, 차있음
  i = 3: (5 + 9) = 14
  table[14] 비어있음 → 저장

결과:
  table[5]: "A"
  table[6]: "B"
  table[9]: "C"  ← 멀리 점프
  table[14]: "D" ← 더 멀리
  
  → 연속 4 칸이 아니라 분산
  → 1차 클러스터링 회피

3.3 이차 탐사의 강점

1. 1차 클러스터링 회피 ★
   - 점프 거리가 점점 늘어남
   - 충돌이 누적되어도 분산

2. 캐시 효율은 약간 떨어짐
   - 연속 접근 아닌 점프
   - 하지만 체이닝보다는 좋음

3. 구현 비교적 단순
   - 산술 연산만 추가

3.4 이차 탐사의 약점

1. 2차 클러스터링 (Secondary Clustering) ★
   - 같은 h(k) 인 키들은 같은 탐사 시퀀스
   - h("Aa") = h("BB") = 5 면 둘 다:
     5 → 6 → 9 → 14 → ...
   - 같은 패턴으로 충돌
   - 1차보다 약하지만 여전히 클러스터

2. 모든 슬롯을 다 못 찾을 수 있음
   - capacity 가 2의 거듭제곱이면
   - i² 패턴이 같은 슬롯 반복
   - 일부 빈 슬롯에 도달 못 함

3. 적절한 capacity 선택 필요
   - 소수 (prime) capacity 권장
   - 또는 c₁·i + c₂·i² 의 c 값 조정

3.5 2차 클러스터링 시각화

h("Aa") = h("BB") = h("AaBB") = 5

put("Aa"):
  5 → 비어있음, 저장

put("BB"):
  i=1: (5+1) = 6, 비어있음, 저장

put("AaBB"):
  i=1: 6, 차있음
  i=2: 9, 비어있음, 저장

put("BBAa"):
  i=1: 6, 차있음
  i=2: 9, 차있음
  i=3: 14, 비어있음, 저장

→ 모두 같은 시퀀스 (6, 9, 14, ...) 로 충돌
→ 2차 클러스터

→ 1차 클러스터링은 회피하지만 2차 클러스터링 발생.

3.6 슬롯 도달 가능성 문제

capacity 가 2의 거듭제곱일 때 문제:

capacity = 8 가정:
  h = 0 부터 i² 시퀀스:
    0, 1, 4, 9 % 8 = 1, 16 % 8 = 0, 25 % 8 = 1, ...
  → {0, 1, 4} 만 도달 가능
  → 다른 슬롯 못 찾음

해결 1: capacity 를 소수로
  capacity = 7:
    0, 1, 4, 9%7=2, 16%7=2, 25%7=4, ...
    여전히 일부 문제

해결 2: c₁·i + c₂·i² 형식
  공식적으로 모든 슬롯 도달 보장

해결 3: 이중 해싱 (다음 섹션)

3.7 자바의 이차 탐사 — Triangle Numbers

자바의 ThreadLocal.ThreadLocalMap 은 비슷한 변형 사용:

// 또는 다른 라이브러리에서 본 패턴
private static int nextIndex(int i, int len) {
    return ((i + 1 < len) ? i + 1 : 0);
}

// 또는 triangle number
private static int probe(int i, int hash, int capacity) {
    return (hash + (i * (i + 1)) / 2) & (capacity - 1);
}

i × (i+1) / 2 = triangle number:

  • 0, 1, 3, 6, 10, 15, 21, ...
  • capacity 가 2의 거듭제곱이어도 모든 슬롯 도달 보장

3.8 자기 점검 답변

이차 탐사가 선형 탐사보다 좋은 점과 한계는?

답:

  • 좋은 점:

    • 1차 클러스터링 회피
    • 점프 거리 증가로 분산
    • 같은 영역에 충돌 누적 안 됨

  • 한계:

    • 2차 클러스터링 (같은 hash 면 같은 시퀀스)
    • 모든 슬롯 도달 보장 안 됨
    • capacity 선택 신중 필요
    • 캐시 효율 선형 탐사보다 약간 ↓

→ 클러스터링은 줄지만 완전 해결 X.

4️⃣ 이중 해싱 (Double Hashing)

4.1 이중 해싱의 정의

이중 해싱 (Double Hashing):

  두 개의 해시 함수 사용.
  두 번째 해시 함수로 탐사 거리 결정.

탐사 시퀀스:
  h_i(k) = (h₁(k) + i × h₂(k)) mod m
  
  - h₁(k): 기본 해시 (첫 위치)
  - h₂(k): 보조 해시 (탐사 간격)
  - i: 탐사 횟수

4.2 이중 해싱 동작

가정:
  h₁("A") = 5, h₂("A") = 3
  h₁("B") = 5, h₂("B") = 7

put("A"):
  i = 0: (5 + 0 × 3) % 16 = 5
  table[5] 비어있음 → 저장

put("B"):
  i = 0: (5 + 0 × 7) % 16 = 5, 차있음
  i = 1: (5 + 1 × 7) % 16 = 12
  table[12] 비어있음 → 저장

put("C"): h₁("C") = 5, h₂("C") = 11
  i = 0: 5, 차있음
  i = 1: (5 + 1 × 11) % 16 = 0
  table[0] 비어있음 → 저장

put("D"): h₁("D") = 5, h₂("D") = 3
  i = 0: 5, 차있음
  i = 1: (5 + 3) = 8
  table[8] 비어있음 → 저장

결과:
  table[0]: "C"
  table[5]: "A"
  table[8]: "D"
  table[12]: "B"
  
  → 매우 분산된 결과

4.3 이중 해싱의 강점

1. 1차 + 2차 클러스터링 모두 회피 ★★★
   - 키마다 다른 탐사 시퀀스
   - h₂(k) 가 키마다 다르므로
   - 분산이 매우 좋음

2. 균등한 슬롯 사용
   - 모든 슬롯이 비슷한 확률로 사용
   - LoadFactor 높아도 성능 유지

3. 이론적으로 최적
   - 균등 분포에 가장 가까움

4.4 이중 해싱의 약점

1. 두 해시 함수 계산
   - 두 번 계산 비용
   - 작은 데이터엔 비효율

2. 캐시 효율 ↓↓
   - 점프 거리가 매우 큼
   - 캐시 미스 빈번

3. h₂(k) 의 조건
   - 0 이 되면 안 됨 (무한 루프)
   - capacity 와 서로소 (coprime) 권장

4.5 h₂(k) 의 조건

요구 조건:

1. h₂(k) ≠ 0
   - 0 이면 같은 슬롯 반복 → 무한 루프

2. h₂(k) 와 capacity 가 서로소
   - gcd(h₂(k), m) = 1
   - 모든 슬롯 도달 보장

3. 일반적 구현:
   capacity 가 소수 m 일 때:
     h₂(k) = q - (k mod q)
     (q < m 인 소수)

   capacity 가 2^k 일 때:
     h₂(k) = (k mod (m-1)) | 1   ← 홀수 보장

4.6 세 가지 탐사 비교

선형 탐사:
  h_i(k) = h(k) + i
  단순, 캐시 친화적, 1차 클러스터링

이차 탐사:
  h_i(k) = h(k) + i²
  1차 회피, 2차 클러스터링, 슬롯 도달 문제

이중 해싱:
  h_i(k) = h₁(k) + i × h₂(k)
  최고 분산, 캐시 효율 ↓, 비용 ↑

4.7 성능 비교 (LoadFactor α)

α = 0.5:
  선형:     평균 1.5
  이차:     평균 1.44
  이중:     평균 1.39

α = 0.75:
  선형:     평균 2.5
  이차:     평균 1.85
  이중:     평균 1.66

α = 0.9:
  선형:     평균 5.5
  이차:     평균 2.85
  이중:     평균 2.55

→ LoadFactor 가 높을수록 이중 해싱이 더 유리
→ 그러나 작은 α 에선 선형이 빠를 수도 (캐시 효율)

4.8 실제 사용

이중 해싱 사용:
  - 일부 데이터베이스 인덱스
  - 분산 시스템의 consistent hashing
  - 학술적으로 가장 우수

실제 라이브러리:
  - Python dict: 변형된 선형 탐사 + 추가 해시
  - Rust HashMap: Robin Hood + SipHash
  - Go map: 변형된 오픈 어드레싱

4.9 자기 점검 답변

세 가지 탐사 방법의 트레이드오프는?

답:
| 항목 | 선형 | 이차 | 이중 |
|---|---|---|---|
| 1차 클러스터링 | 발생 | 회피 | 회피 |
| 2차 클러스터링 | 발생 | 발생 | 회피 |
| 캐시 효율 | ★★★ | ★★ | ★ |
| 구현 복잡도 | 낮음 | 중간 | 높음 |
| LoadFactor 한계 | 0.5 | 0.7 | 0.9 |
| 평균 탐사 (α=0.75) | 2.5 | 1.85 | 1.66 |

선택 가이드:

  • 작은 데이터, 캐시 중요 → 선형
  • 균형 → 이차
  • 큰 데이터, 분산 중요 → 이중

5️⃣ Robin Hood Hashing — 영리한 변형

5.1 Robin Hood Hashing 의 발상

일반 오픈 어드레싱:
  먼저 도착한 키가 자기 위치를 차지
  뒤에 온 키는 멀리 가야 함
  → "부자는 가까이, 가난한 자는 멀리"

Robin Hood Hashing (1986):
  "부자에게서 빼앗아 가난한 자에게"
  
  탐사 거리가 짧은 키 > 탐사 거리가 긴 키
  
  → 탐사 거리를 균등하게 분배
  → 최악 탐사 거리 ↓

5.2 알고리즘

put(key):
  1. 기본 위치 h(key) 계산
  2. 탐사 시작 (선형 탐사)
  3. 빈 슬롯 도달 → 저장
  4. 기존 슬롯 도달 시:
     - 내 탐사 거리 vs 기존 키의 탐사 거리 비교
     - 내가 더 멀리 왔으면 (가난):
       - 기존 키를 빼앗음
       - 내가 그 자리 차지
       - 기존 키는 새 자리 찾으러 다음 슬롯으로
     - 내가 덜 왔으면:
       - 다음 슬롯으로 (일반 탐사)

5.3 동작 시각화

초기 상태:
  table[5]: "A" (탐사 거리 0)
  table[6]: "B" (탐사 거리 1, 원래 5 였음)
  table[7]: "C" (탐사 거리 2, 원래 5 였음)
  
put("D"): h("D") = 6 (즉, table[6] 이 기본 위치)
  
  Step 1: table[6] 확인
    내 탐사 거리: 0
    "B" 의 탐사 거리: 1
    → 내가 더 가까움 (0 < 1)
    → 일반 탐사: 다음으로

  Step 2: table[7] 확인
    내 탐사 거리: 1
    "C" 의 탐사 거리: 2
    → 내가 더 가까움 (1 < 2)
    → 다음으로

  Step 3: table[8] 비어있음
    내 탐사 거리: 2
    → 저장

put("E"): h("E") = 5 (table[5] 이 기본 위치)

  Step 1: table[5] 확인
    내 탐사 거리: 0
    "A" 의 탐사 거리: 0
    → 둘 다 같음, 일반 탐사

  Step 2: table[6] 확인
    내 탐사 거리: 1
    "B" 의 탐사 거리: 1
    → 같음, 다음으로

  ... 계속 ...

5.4 Robin Hood 의 핵심 효과

일반 선형 탐사:
  탐사 거리 분산:
  [0, 0, 0, 1, 2, 5, 8, 15]
  최악 15 회

Robin Hood:
  탐사 거리 균등화:
  [0, 1, 2, 2, 3, 3, 4, 4]
  최악 4 회

→ 평균은 비슷, 최악이 크게 개선
→ 분산이 매우 균등

5.5 검색 최적화 — Backshift Deletion

Robin Hood 의 또 다른 강점:
  
  검색 시 "내 탐사 거리 > 현재 슬롯 키의 탐사 거리" 이면
  → 더 이상 탐사 안 함 (없다고 확정)

이유:
  Robin Hood 의 불변식:
    모든 키의 탐사 거리는 정렬되어 있음
    (단조 비증가 또는 단조 증가)
  
  → 빠른 종료 가능

5.6 삭제 — Backshift

Robin Hood 의 삭제 (Backshift Deletion):
  
  1. 삭제할 슬롯 찾기 (탐사)
  2. 슬롯을 null 로 표시
  3. 다음 슬롯 확인:
     - null 이거나 탐사 거리 0 → 종료
     - 아니면: 그 키를 한 칸 앞으로 이동 (탐사 거리 -1)
  4. 반복

→ Tombstone 불필요!
→ 삭제 후에도 자료구조 정상

5.7 Robin Hood Hashing 의 구현

public class RobinHoodMap<K, V> {
    
    static class Entry<K, V> {
        K key;
        V value;
        int probeDistance;   // 탐사 거리
        
        Entry(K key, V value, int probeDistance) {
            this.key = key;
            this.value = value;
            this.probeDistance = probeDistance;
        }
    }
    
    private Entry<K, V>[] table;
    private int size;
    private static final float LOAD_FACTOR = 0.75f;
    
    @SuppressWarnings("unchecked")
    public RobinHoodMap(int capacity) {
        this.table = (Entry<K, V>[]) new Entry[capacity];
    }
    
    public void put(K key, V value) {
        int hash = hash(key);
        int idx = hash & (table.length - 1);
        
        Entry<K, V> newEntry = new Entry<>(key, value, 0);
        
        while (true) {
            if (table[idx] == null) {
                // 빈 슬롯 → 저장
                table[idx] = newEntry;
                size++;
                return;
            }
            
            if (table[idx].key.equals(newEntry.key)) {
                // 같은 키 → 덮어쓰기
                table[idx].value = newEntry.value;
                return;
            }
            
            // Robin Hood: 더 멀리 온 키가 자리 차지
            if (newEntry.probeDistance > table[idx].probeDistance) {
                // 빼앗기
                Entry<K, V> tmp = table[idx];
                table[idx] = newEntry;
                newEntry = tmp;
            }
            
            // 다음 슬롯
            idx = (idx + 1) & (table.length - 1);
            newEntry.probeDistance++;
        }
    }
    
    public V get(K key) {
        int hash = hash(key);
        int idx = hash & (table.length - 1);
        int distance = 0;
        
        while (table[idx] != null) {
            if (table[idx].key.equals(key)) {
                return table[idx].value;
            }
            
            // Robin Hood 빠른 종료:
            // 내가 더 멀리 왔는데 못 찾음 → 없음
            if (distance > table[idx].probeDistance) {
                return null;
            }
            
            idx = (idx + 1) & (table.length - 1);
            distance++;
        }
        return null;
    }
    
    static int hash(Object key) {
        if (key == null) return 0;
        int h = key.hashCode();
        return h ^ (h >>> 16);
    }
}

5.8 Robin Hood 의 실제 사용

실제 채택:
  - Rust HashMap (이전 버전)
  - 일부 게임 엔진
  - 일부 데이터베이스

장점:
  - 매우 균등한 탐사 거리
  - 캐시 친화적 (선형 탐사 기반)
  - tombstone 불필요

단점:
  - put 시 추가 비교 비용
  - 구현 복잡
  - 최신 SwissTable 등에 비해 조금 느림

5.9 자기 점검 답변

Robin Hood Hashing 의 핵심 발상은?

답:

  • 일반 오픈 어드레싱: "먼저 온 자가 자기 위치 차지"
  • Robin Hood: "탐사 거리 짧은 자에게서 빼앗아 긴 자에게"
  • 결과:
    • 평균 탐사 거리는 비슷
    • 최악 탐사 거리 크게 개선
    • 빠른 종료 가능
    • Tombstone 불필요

→ 이름 그대로 "부자에게서 빼앗아 가난한 자에게".

6️⃣ 삭제의 함정 — Tombstone

6.1 단순 삭제의 문제

초기 상태:
  table[5]: "A"
  table[6]: "B" (원래 h("B") = 5 였음)
  table[7]: "C" (원래 h("C") = 5 였음)

단순 삭제 — table[6] 의 "B" 제거:
  table[5]: "A"
  table[6]: null
  table[7]: "C"

검색 get("C"):
  h("C") = 5
  table[5]: "A" 다름 → 다음
  table[6]: null → 없음 반환 (!)
  
  → "C" 가 있는데 못 찾음 !
  → 자료구조 깨짐

6.2 Tombstone (삭제 마커)

Tombstone:
  삭제된 슬롯에 특별한 마커 (DELETED, 또는 -1) 표시.
  - null 과 다름
  - 검색 시 통과
  - 새 키 삽입 시 재사용 가능

상태 3가지:
  - EMPTY (null): 한 번도 사용 안 됨
  - OCCUPIED: 사용 중
  - DELETED (tombstone): 삭제됨

검색 동작:
  - EMPTY 만나면 종료
  - DELETED 만나면 통과
  - OCCUPIED + 매칭이면 반환

6.3 Tombstone 동작 시각화

초기 상태:
  table[5]: "A"
  table[6]: "B"
  table[7]: "C"

remove("B"):
  table[5]: "A"
  table[6]: DELETED  ← tombstone
  table[7]: "C"

get("C"):
  h("C") = 5
  table[5]: "A" 다름 → 다음
  table[6]: DELETED → 통과
  table[7]: "C" 매칭 → 반환 ★

put("D"): h("D") = 6
  table[6] DELETED → 재사용 가능
  table[6]: "D"

6.4 Tombstone 의 문제

1. 탐사 시간 증가
   - Tombstone 도 탐사해야 함
   - 삭제 많으면 탐사 길어짐

2. 메모리 누수
   - Tombstone 이 누적되면
   - LoadFactor 가 false 로 작아 보임
   - 실제 사용 슬롯 + tombstone = 가용 슬롯

3. 재해싱 필요
   - Tombstone 너무 많아지면 재해싱
   - 또는 주기적 cleanup

6.5 Tombstone 비율 관리

일반적 전략:

LoadFactor 계산:
  used = OCCUPIED 수
  total_used = OCCUPIED + DELETED
  load = total_used / capacity

규칙:
  - load > 0.75: 재해싱
  - 모든 tombstone 제거 + 노드 재배치
  - 이후 LoadFactor 정상

또는:
  - 매 N 회 삭제마다 cleanup
  - 또는 GC 시 정리

6.6 Robin Hood Hashing 의 우회

Robin Hood 는 Tombstone 불필요!

Backshift Deletion:
  
  remove("B") 동작:
    1. table[6] = null (일단)
    2. table[7] 확인:
       - "C" 의 탐사 거리 > 0 (원래 5 였음)
       - 한 칸 앞으로 이동
       - table[6] = "C" (탐사 거리 -1)
       - table[7] = null
    3. table[8] 확인:
       - null 이거나 탐사 거리 0 → 종료

결과:
  table[5]: "A" (거리 0)
  table[6]: "C" (거리 1, 이동됨)
  table[7]: null
  
  → Tombstone 없이 자료구조 정상!

6.7 다른 오픈 어드레싱의 처리

Python dict:
  - Tombstone (-1, dummy entry)
  - 재해싱 시 cleanup

Rust HashMap (SwissTable):
  - 16개 슬롯을 한 묶음 (그룹)으로
  - SIMD 명령으로 그룹 단위 검사
  - tombstone 비슷한 마커

자바 IdentityHashMap:
  - 단순 선형 탐사
  - tombstone 사용

자바 EnumMap:
  - 비트벡터 (다음 섹션)
  - tombstone 불필요 (모든 슬롯이 정해진 enum)

6.8 Tombstone vs Backshift 비교

항목TombstoneBackshift
메모리추가 마커추가 X
삭제 비용O(1)O(클러스터 크기)
검색 영향tombstone 통과변화 없음
누적 영향재해싱 필요누적 X
구현단순Robin Hood 와 결합

6.9 자기 점검 답변

단순 삭제가 안 되는 이유와 Tombstone 의 역할은?

답:

  • 단순 삭제의 문제:

    • 삭제한 슬롯이 null 이 됨
    • 검색 시 null 만나면 "없음" 종료
    • 같은 시퀀스의 뒤 키들을 못 찾음
    • 자료구조 깨짐

  • Tombstone 역할:

    • 삭제된 슬롯에 특별 마커
    • 검색 시 통과 (계속 탐사)
    • 새 키 삽입 시 재사용
    • 탐사 체인 유지

  • 단점:

    • 누적되면 검색 느려짐
    • 주기적 재해싱 필요

→ Robin Hood 의 Backshift 가 더 우아한 대안.

7️⃣ 자바와 다른 언어의 실제 구현

7.1 자바 EnumMap

// EnumMap 내부 (간략화)
public class EnumMap<K extends Enum<K>, V> ... {
    
    private final Class<K> keyType;
    private final K[] keyUniverse;        // 모든 Enum 값
    private Object[] vals;                // 값 배열
    private int size = 0;
    
    public EnumMap(Class<K> keyType) {
        this.keyType = keyType;
        keyUniverse = getKeyUniverse(keyType);  // 모든 Enum 상수
        vals = new Object[keyUniverse.length];  // Enum 값 수만큼
    }
    
    public V put(K key, V value) {
        int index = key.ordinal();   // ★ Enum 의 ordinal() 을 직접 인덱스로
        Object oldValue = vals[index];
        vals[index] = maskNull(value);
        if (oldValue == null) size++;
        return unmaskNull(oldValue);
    }
    
    public V get(Object key) {
        if (!isValidKey(key)) return null;
        return unmaskNull(vals[((Enum<?>) key).ordinal()]);
    }
}

핵심:

  • Perfect Hashing 의 일종
  • Enum 의 ordinal() = 직접 인덱스
  • 충돌 없음 (모든 Enum 이 다른 ordinal)
  • 매우 빠름 (배열 직접 접근)

7.2 자바 IdentityHashMap

// IdentityHashMap 내부 (간략화)
public class IdentityHashMap<K, V> ... {
    
    transient Object[] table;       // 키-값 쌍이 한 배열에
    int size = 0;
    
    public V put(K key, V value) {
        final Object k = maskNull(key);
        
        retryAfterResize: for (;;) {
            final Object[] tab = table;
            final int len = tab.length;
            int i = hash(k, len);   // 인덱스
            
            for (Object item; (item = tab[i]) != null;
                 i = nextKeyIndex(i, len)) {     // 선형 탐사
                if (item == k) {                  // ★ == 비교 (identity)
                    V oldValue = (V) tab[i + 1];
                    tab[i + 1] = value;
                    return oldValue;
                }
            }
            
            // 빈 슬롯 발견
            tab[i] = k;
            tab[i + 1] = value;
            size++;
            // ... resize 검사
            return null;
        }
    }
    
    private static int nextKeyIndex(int i, int len) {
        return (i + 2 < len ? i + 2 : 0);    // 2씩 증가 (key, value 쌍)
    }
}

특징:

  • == 로 비교 (identity, equals 아님)
  • 키 + 값을 한 배열에 쌍으로 (table[i]=key, table[i+1]=value)
  • 선형 탐사
  • 캐시 효율 ★★★

7.3 자바 ThreadLocalMap

// ThreadLocal.ThreadLocalMap 내부 (간략화)
static class ThreadLocalMap {
    
    static class Entry extends WeakReference<ThreadLocal<?>> {
        Object value;
        
        Entry(ThreadLocal<?> k, Object v) {
            super(k);
            value = v;
        }
    }
    
    private Entry[] table;
    
    private void set(ThreadLocal<?> key, Object value) {
        int i = key.threadLocalHashCode & (table.length - 1);
        
        for (Entry e = table[i]; e != null; e = table[i = nextIndex(i, table.length)]) {
            ThreadLocal<?> k = e.get();
            
            if (k == key) {
                e.value = value;
                return;
            }
            
            if (k == null) {
                // 약한 참조로 인해 GC 된 키 → 자리 청소
                replaceStaleEntry(key, value, i);
                return;
            }
        }
        
        // 빈 슬롯 발견
        table[i] = new Entry(key, value);
        size++;
        // ... 정리 + resize
    }
    
    private static int nextIndex(int i, int len) {
        return ((i + 1 < len) ? i + 1 : 0);   // 선형 탐사
    }
}

특징:

  • 선형 탐사
  • 키는 WeakReference (메모리 누수 방지)
  • threadLocalHashCode 사용 (특수 해시)
  • 자바의 오픈 어드레싱 채택 사례

7.4 Python dict 의 구현

// CPython 의 dict 구현 (간략화)
// dictobject.c

typedef struct {
    Py_hash_t me_hash;       // 해시 (캐싱)
    PyObject *me_key;
    PyObject *me_value;
} PyDictKeyEntry;

// 오픈 어드레싱 + 변형된 탐사
static Py_ssize_t lookdict(PyDictObject *mp, PyObject *key,
                            Py_hash_t hash, PyObject **value_addr) {
    size_t i, mask = DK_MASK(mp->ma_keys);
    Py_ssize_t ix;
    size_t perturb = hash;
    
    i = (size_t)hash & mask;
    
    for (;;) {
        ix = dk_get_index(mp->ma_keys, i);
        
        if (ix == DKIX_EMPTY) {
            *value_addr = NULL;
            return DKIX_EMPTY;
        }
        
        if (ix >= 0) {
            PyDictKeyEntry *ep = &mp->ma_keys->dk_entries[ix];
            if (ep->me_key == key) {
                *value_addr = ep->me_value;
                return ix;
            }
            
            if (ep->me_hash == hash) {
                int cmp = PyObject_RichCompareBool(ep->me_key, key, Py_EQ);
                if (cmp > 0) {
                    *value_addr = ep->me_value;
                    return ix;
                }
            }
        }
        
        // Python 의 탐사 방식 — perturbation
        perturb >>= PERTURB_SHIFT;   // 5
        i = (i * 5 + perturb + 1) & mask;
    }
}

특징:

  • Perturbation 방식: 해시 자체를 시프트하며 다음 인덱스 결정
  • 선형 탐사보다 분산 좋음
  • 캐시 효율은 약간 떨어짐
  • Python 3.7+ 부터는 삽입 순서 보존 (별도 메커니즘)

7.5 Rust HashMap (SwissTable)

SwissTable 알고리즘 (Google 의 abseil 에서):

핵심 아이디어:
  16개 슬롯을 한 그룹 (Group) 으로
  각 슬롯에 1바이트 메타데이터 + 키-값
  
메타데이터:
  - 1바이트로 슬롯 상태 표시
  - 비어있음, 사용 중, 삭제됨
  - 또한 hash 의 상위 7비트 저장
  
검색 동작:
  1. 그룹 위치 계산 (hash & mask)
  2. SIMD 로 그룹 16개 메타 동시 비교
  3. hash 의 상위 7비트 매칭 후보 찾기
  4. 후보들과 키 비교
  
→ CPU SIMD 활용으로 매우 빠름
→ 캐시 효율 극대화 (16 슬롯 = 한 캐시 라인)

7.6 Go map 의 구현

Go map 의 구조:

bucket 단위로 묶기:
  - 8개 키-값을 한 bucket 으로
  - bucket 내부는 선형 탐사 비슷
  - bucket 사이는 오픈 어드레싱

특징:
  - 하이브리드 (체이닝 + 오픈 어드레싱)
  - 캐시 친화적
  - LoadFactor 6.5 / 8 = 0.8125

7.7 비교 표 — 언어별 구현

언어자료구조방식특징
Java HashMap체이닝 + Tree체이닝트리 변환
Java EnumMap배열Perfect Hashingordinal()
Java IdentityHashMap배열선형 탐사 + ==identity
Java ThreadLocalMap배열선형 탐사 + WeakRefGC 친화
Python dict배열Perturbation순서 보존
Rust HashMap배열SwissTableSIMD 최적화
Go mapbucket 그룹하이브리드캐시 친화

7.8 자기 점검 답변

자바에서 오픈 어드레싱을 사용하는 4가지 자료구조는?

답:
1. EnumMap — Perfect Hashing (ordinal()), Enum 키 전용
2. IdentityHashMap — 선형 탐사 + == 비교
3. ThreadLocal.ThreadLocalMap — 선형 탐사 + WeakReference
4. EnumSet (관련) — 비트벡터, EnumMap 과 비슷

이들 모두 특수 목적 자료구조:

  • Enum 키
  • 참조 동일성
  • 스레드 로컬 저장

→ 일반적 HashMap 은 여전히 체이닝.

8️⃣ 직접 구현하는 OpenAddressingMap

8.1 구현 목표

구현 기능:
  - put, get, remove, size, containsKey
  - 선형 탐사
  - Tombstone 방식 삭제
  - resize (2배 확장)

제외 기능:
  - 이차 탐사, 이중 해싱, Robin Hood (개념만)
  - Iterator
  - 멀티스레드 안전성

8.2 Entry 클래스와 상태

public class OpenAddressingMap<K, V> {
    
    static class Entry<K, V> {
        K key;
        V value;
        boolean deleted;   // tombstone 표시
        
        Entry(K key, V value) {
            this.key = key;
            this.value = value;
            this.deleted = false;
        }
    }
    
    private Entry<K, V>[] table;
    private int size;
    private int tombstones;  // tombstone 카운트
    private static final float LOAD_FACTOR = 0.5f;   // 오픈 어드레싱은 낮게
    private static final int DEFAULT_CAPACITY = 16;
    
    @SuppressWarnings("unchecked")
    public OpenAddressingMap() {
        this.table = (Entry<K, V>[]) new Entry[DEFAULT_CAPACITY];
    }
    
    static int hash(Object key) {
        if (key == null) return 0;
        int h = key.hashCode();
        return h ^ (h >>> 16);
    }
}

8.3 put 메서드

public V put(K key, V value) {
    if ((size + tombstones) >= table.length * LOAD_FACTOR) {
        resize();
    }
    
    int idx = hash(key) & (table.length - 1);
    int firstTombstone = -1;   // 첫 tombstone 위치 기억
    
    while (true) {
        if (table[idx] == null) {
            // 빈 슬롯
            int targetIdx = (firstTombstone != -1) ? firstTombstone : idx;
            table[targetIdx] = new Entry<>(key, value);
            if (firstTombstone == -1) {
                size++;
            } else {
                size++;
                tombstones--;
            }
            return null;
        }
        
        if (table[idx].deleted) {
            // Tombstone - 위치 기억하고 계속 탐사
            if (firstTombstone == -1) firstTombstone = idx;
        } else if (table[idx].key.equals(key)) {
            // 같은 키 - 덮어쓰기
            V oldValue = table[idx].value;
            table[idx].value = value;
            return oldValue;
        }
        
        // 다음 슬롯 (선형 탐사)
        idx = (idx + 1) & (table.length - 1);
    }
}

8.4 get 메서드

public V get(K key) {
    int idx = hash(key) & (table.length - 1);
    
    while (table[idx] != null) {
        if (!table[idx].deleted && table[idx].key.equals(key)) {
            return table[idx].value;
        }
        // tombstone 이면 통과 (계속 탐사)
        idx = (idx + 1) & (table.length - 1);
    }
    
    return null;   // null 슬롯 도달 = 없음
}

public boolean containsKey(K key) {
    return getEntry(key) != null;
}

private Entry<K, V> getEntry(K key) {
    int idx = hash(key) & (table.length - 1);
    
    while (table[idx] != null) {
        if (!table[idx].deleted && table[idx].key.equals(key)) {
            return table[idx];
        }
        idx = (idx + 1) & (table.length - 1);
    }
    return null;
}

8.5 remove 메서드

public V remove(K key) {
    int idx = hash(key) & (table.length - 1);
    
    while (table[idx] != null) {
        if (!table[idx].deleted && table[idx].key.equals(key)) {
            // 찾음! Tombstone 처리
            V oldValue = table[idx].value;
            table[idx].deleted = true;
            table[idx].key = null;       // GC 도움
            table[idx].value = null;
            size--;
            tombstones++;
            
            // Tombstone 너무 많으면 재해싱
            if (tombstones > table.length / 4) {
                rehash();
            }
            
            return oldValue;
        }
        idx = (idx + 1) & (table.length - 1);
    }
    
    return null;
}

8.6 resize 와 rehash

@SuppressWarnings("unchecked")
private void resize() {
    Entry<K, V>[] oldTable = table;
    int newCapacity = oldTable.length * 2;
    table = (Entry<K, V>[]) new Entry[newCapacity];
    int oldSize = size;
    size = 0;
    tombstones = 0;
    
    // 모든 비-tombstone 노드 재배치
    for (Entry<K, V> entry : oldTable) {
        if (entry != null && !entry.deleted) {
            putInternal(entry.key, entry.value);
        }
    }
}

@SuppressWarnings("unchecked")
private void rehash() {
    // capacity 유지하면서 tombstone 만 정리
    Entry<K, V>[] oldTable = table;
    table = (Entry<K, V>[]) new Entry[oldTable.length];
    int oldSize = size;
    size = 0;
    tombstones = 0;
    
    for (Entry<K, V> entry : oldTable) {
        if (entry != null && !entry.deleted) {
            putInternal(entry.key, entry.value);
        }
    }
}

private void putInternal(K key, V value) {
    int idx = hash(key) & (table.length - 1);
    while (table[idx] != null) {
        idx = (idx + 1) & (table.length - 1);
    }
    table[idx] = new Entry<>(key, value);
    size++;
}

public int size() {
    return size;
}

8.7 사용 예시

public class OpenAddressingMapTest {
    public static void main(String[] args) {
        OpenAddressingMap<String, Integer> map = new OpenAddressingMap<>();
        
        // 기본 동작
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("cherry", 3);
        
        System.out.println(map.get("apple"));   // 1
        System.out.println(map.size());          // 3
        
        // 덮어쓰기
        Integer old = map.put("apple", 99);
        System.out.println(old);                 // 1
        
        // 삭제
        Integer removed = map.remove("banana");
        System.out.println(removed);              // 2
        System.out.println(map.size());           // 2
        
        // Tombstone 재사용
        map.put("banana", 200);
        System.out.println(map.get("banana"));    // 200
        
        // 충돌 강제
        map.put("Aa", 1);
        map.put("BB", 2);   // 같은 hashCode
        System.out.println(map.get("BB"));        // 2
        
        // 대량 데이터
        for (int i = 0; i < 1000; i++) {
            map.put("key" + i, i);
        }
        System.out.println(map.size());           // 1003
        System.out.println(map.get("key500"));    // 500
    }
}

8.8 체이닝 SimpleHashMap 과의 차이

체이닝 (Unit 3.3 의 SimpleHashMap):
  - Node 클래스 (next 포인터)
  - LoadFactor 0.75
  - 충돌 시 노드 추가
  - 삭제는 단순

오픈 어드레싱 (이 Unit):
  - Entry 클래스 (deleted 플래그)
  - LoadFactor 0.5
  - 충돌 시 다음 슬롯
  - 삭제는 tombstone

메모리:
  - 체이닝: n × 48 bytes (Node) + 배열
  - 오픈: capacity × 32 bytes (Entry)
  
  LoadFactor 0.5 라면:
  capacity = 2n
  → 2n × 32 = 64n bytes
  
  체이닝: 48n + 1.33n × 4 = ~53n
  오픈: 64n
  
  → 의외로 오픈이 더 메모리 사용
  → 단, Java 의 Node 객체 헤더 비용 때문

8.9 성능 비교 (가상 벤치마크)

10,000 키 작업:

put:
  체이닝: 5 ms
  오픈 어드레싱: 3 ms ★

get:
  체이닝: 4 ms  
  오픈 어드레싱: 2 ms ★

remove + put 반복:
  체이닝: 5 ms
  오픈 어드레싱: 10 ms (tombstone 누적)

큰 데이터 (1M):
  체이닝: 100 ms
  오픈 어드레싱: 200 ms (캐시 미스 ↑)

→ 작은 데이터엔 오픈 어드레싱이 빠름.
→ 큰 데이터엔 체이닝이 안정적.

8.10 더 깊은 학습 — 추가 가능 기능

1. Robin Hood Hashing
   - probeDistance 필드 추가
   - put 시 비교/교환
   - get 시 빠른 종료

2. 이차 탐사
   - i² 시퀀스로 탐사
   - 클러스터링 회피

3. 이중 해싱
   - 두 번째 해시 함수
   - 키마다 다른 시퀀스

4. SwissTable 스타일
   - 16 슬롯 그룹
   - 메타데이터 1 바이트
   - SIMD 최적화 (Java 에선 직접 어려움)

5. 동시성 지원
   - CAS 기반 lock-free
   - 또는 락 분할

8.11 자기 점검 답변

직접 구현한 OpenAddressingMap 에서 tombstone 처리의 핵심은?

답:
1. put: 첫 tombstone 위치 기억, 같은 키 없으면 거기 저장
2. get: tombstone 만나면 통과, null 만날 때까지
3. remove: 슬롯을 tombstone 으로 표시 (null 아님)
4. rehash: tombstone 너무 많아지면 정리

핵심:

  • tombstone 은 "한때 있었음" 표시
  • 검색 시 통과해야 자료구조 정상
  • 누적되면 성능 저하 → 주기적 정리

9️⃣ 체이닝 vs 오픈 어드레싱 + Phase 3 완주

9.1 두 방법의 종합 비교

항목체이닝오픈 어드레싱
자료구조배열 + 연결 리스트/트리배열만
충돌 처리같은 버킷에 노드 추가다른 슬롯 탐사
LoadFactor0.75 (또는 더 높이)0.5 ~ 0.75
메모리Node 객체 (오버헤드)배열만 (효율)
캐시 효율낮음높음 ★
삭제단순tombstone or backshift
클러스터링없음1차, 2차 클러스터
트리 변환가능 (Java 8+)어려움
최악 케이스O(log n) (트리)O(n) (대체로)
구현 복잡도중간변형 따라 다름

9.2 채택 사례 종합

체이닝:
  ✓ Java HashMap (전통적)
  ✓ Java HashSet (HashMap wrapper)
  ✓ Java ConcurrentHashMap
  ✓ Java Hashtable (legacy)
  ✓ C++ std::unordered_map (대부분)

오픈 어드레싱:
  ✓ Java EnumMap (Perfect Hashing)
  ✓ Java IdentityHashMap
  ✓ Java ThreadLocal.ThreadLocalMap
  ✓ Python dict (Perturbation)
  ✓ Ruby Hash (Ruby 2.4+)
  ✓ Rust HashMap (SwissTable)
  ✓ Go map (하이브리드)
  ✓ .NET Dictionary (일부)

9.3 선택 기준

체이닝 선택 시:
  - 큰 데이터셋 (100만 이상)
  - 잦은 삽입/삭제
  - 트리 변환 필요 (HashDoS 방어)
  - 일관성 있는 동작 (LoadFactor 변동)

오픈 어드레싱 선택 시:
  - 작은 데이터셋 (수만 이하)
  - 캐시 효율 중요
  - 메모리 제약
  - 정해진 키 집합 (EnumMap 등)
  - 정적 데이터

9.4 Phase 3 학습의 의미

Phase 3 4 Unit 의 종합:

Unit 3.1 — 해시의 탄생 배경
  → "왜 O(1)?"

Unit 3.2 — 해시 충돌
  → "왜 충돌은 불가피?"
  → 비둘기집, 생일 역설, HashDoS

Unit 3.3 — 체이닝 (마스터 깊이)
  → "자바 HashMap 은 어떻게?"
  → put/get/remove/resize 정밀
  → 직접 구현

Unit 3.4 — 오픈 어드레싱 (마스터 깊이)
  → "다른 언어는 어떻게?"
  → 선형/이차/이중/Robin Hood
  → 직접 구현

→ Phase 3 가 1주차 HashMap PPT 학습의 정점

9.5 자바 HashMap 의 진화

Java 1.0 (1996):
  - Hashtable
  - 체이닝 + synchronized

Java 1.2 (1998):
  - HashMap 도입
  - 체이닝 + 비동기
  - LoadFactor 0.75

Java 5 (2004):
  - 제네릭 추가
  - HashMap<K, V>

Java 7 (2011):
  - 일부 최적화
  - 여전히 체이닝 + 연결 리스트

Java 8 (2014):
  - 트리 변환 도입 ★
  - 비트 시프트 hash 메서드
  - resize 의 비트 트릭
  - HashDoS 방어 강화

Java 9+ :
  - 마이너 개선
  - immutable factory methods (Map.of)

9.6 면접 단골 종합 정리

Phase 3 의 면접 질문 종합:

1. HashMap 의 O(1) 이유?
2. hashCode + equals 계약?
3. 해시 충돌은?
4. HashMap 의 LoadFactor 0.75 의미?
5. Java 8+ 트리 변환 조건?
6. HashDoS 공격과 방어?
7. ConcurrentHashMap 의 락 단위?
8. 체이닝 vs 오픈 어드레싱?
9. HashMap 직접 구현?
10. Python dict 와 차이?

→ Phase 3 마스터 시 모두 답변 가능

9.7 Phase 3 졸업 시험 — 핵심 30 질문

해시의 본질:
1. 해시 함수의 정의?
2. 좋은 해시 함수 3가지 조건?
3. 해시 검색이 O(1) 인 이유?
4. 해시 vs 이진 검색?
5. Object.hashCode() 의 기본 구현?

충돌:
6. 비둘기집 원리?
7. 생일 역설?
8. Perfect Hashing 의 조건?
9. EnumMap 이 Perfect Hashing 인 이유?
10. String "Aa" vs "BB" 충돌 원인?

체이닝:
11. HashMap Node 의 4개 필드?
12. put 의 11단계?
13. get 의 빠른 종료 최적화?
14. resize 의 비트 트릭?
15. Java 8+ 트리 변환 조건?
16. TreeNode 와 일반 Node 차이?
17. 트리 → 리스트 역변환 조건?

오픈 어드레싱:
18. 선형/이차/이중 탐사 차이?
19. 1차 vs 2차 클러스터링?
20. Robin Hood Hashing 의 발상?
21. Tombstone 의 역할?
22. Backshift Deletion?
23. Python dict 의 Perturbation?
24. SwissTable 의 SIMD 활용?

자바 적용:
25. HashMap 의 hash() 비트 시프트?
26. ConcurrentHashMap 의 Java 7 vs 8?
27. EnumMap 의 ordinal() 활용?
28. IdentityHashMap 의 == 비교?
29. ThreadLocalMap 의 WeakReference?
30. HashDoS 방어 메커니즘?

9.8 자기 점검 답변

체이닝과 오픈 어드레싱 중 자바 HashMap 이 체이닝을 채택한 핵심 이유 3가지는?

답:
1. 삭제의 단순성:

  • 체이닝: 노드 제거 + 양쪽 연결
  • 오픈: tombstone 또는 backshift 필요

  1. 트리 변환 가능:

    • 체이닝: 한 버킷의 노드들을 Red-Black Tree 로
    • 오픈: 트리 만들 위치가 명확하지 않음
    • HashDoS 방어의 핵심

  2. LoadFactor 유연성:

    • 체이닝: 1.0 이상도 가능
    • 오픈: 0.75 이상이면 급락
    • HashMap 의 동적 데이터 친화

→ 자바의 우선순위 (일관성, 트리 변환, 유연성) 와 일치.

🎯 핵심 요약 — 3줄 정리

1. 오픈 어드레싱 = 다음 빈 슬롯 찾기

  • 선형 탐사: i 만큼 다음 (캐시 친화, 1차 클러스터)
  • 이차 탐사: i² 만큼 다음 (1차 회피, 2차 클러스터)
  • 이중 해싱: 다른 해시 함수 (최고 분산, 캐시 ↓)
  • Robin Hood: 탐사 거리 균등화

2. 삭제의 함정

  • 단순 삭제 → 탐사 체인 깨짐
  • Tombstone: 삭제 마커, 검색 시 통과
  • Backshift: Robin Hood 의 우회 (tombstone 불필요)

3. 채택 비교

  • 체이닝: Java HashMap, std::unordered_map, ConcurrentHashMap
  • 오픈: Python dict, Rust HashMap (SwissTable), Go map, Java EnumMap/IdentityHashMap/ThreadLocalMap

🏆 Phase 3 완주 — 해시 마스터 달성

🚀 Phase 3 — 해시(Hash)의 원리
  ✅ Unit 3.1 해시의 탄생 배경
  ✅ Unit 3.2 해시 충돌
  ✅ Unit 3.3 충돌 해결법 1: 체이닝 (마스터 깊이)
  ✅ Unit 3.4 충돌 해결법 2: 오픈 어드레싱 (마스터 깊이) ← 여기

→ 해시 자료구조의 모든 메커니즘 정복
→ HashMap 직접 구현 가능
→ 면접 단골 질문 모두 즉답

3주차 진행 상황

✅ Phase 1 — Pass by Value (1.1 ~ 1.3 완주)
✅ Phase 2 — 컬렉션 프레임워크 (2.1 ~ 2.6 완주)
✅ Phase 3 — 해시의 원리 (3.1 ~ 3.4 완주, 정점)
🚀 Phase 4 — 추상화의 두 도구 (다음)
⏭ Phase 5 — 제네릭과 와일드카드
⏭ Phase 6 — 객체 비교
⏭ Phase 7 — I/O 시스템 큰 그림
⏭ Phase 8 — Stream 실전
⏭ Phase 9 — I/O 강화
⏭ Phase 10 — 함수형 프로그래밍

3주차 누적 진행

작성한 학습 자료:
  Phase 1 (3개): Pass by Value 완주
  Phase 2 (6개): 컬렉션 프레임워크 완주
  Phase 3 (4개): 해시의 원리 완주 (정점)

총: 13/43 Unit 작성 (Phase 3 완주, 약 30%)

📚 다음으로...

Phase 4 — 추상화의 두 도구

다음 Phase 는 자바의 두 가지 추상화 도구를 정밀 분석.

Phase 4 — 추상화의 두 도구 (추상클래스 vs 인터페이스)

Unit 4.1 — 추상클래스의 특징
  → abstract 키워드의 의미
  → 추상 메서드 + 구현 메서드 혼재
  → 단일 상속 제약

Unit 4.2 — 인터페이스의 특징
  → 다중 상속 (구현)
  → public static final 자동
  → 생성자 없음

Unit 4.3 — Java 8 default & static 메서드
  → 인터페이스에 구현 추가
  → 등장 배경 (역사적 진화)
  → diamond problem 해결

Unit 4.4 — 추상클래스 vs 인터페이스 선택 기준
  → is-a 강한 관계 vs can-do 능력
  → Spring/JPA 의 선택
  → AbstractList + List 패턴

Phase 3 와의 연결:

  • Phase 2: 컬렉션의 인터페이스 (List, Set, Map)
  • Phase 3: 그 구현 (해시)
  • Phase 4: 인터페이스와 추상클래스의 본질
  • Phase 5: 제네릭 추가

🏆 Phase 3 완주 — 해시 마스터 달성

profile
Psj
Software Developer
이전 포스트

3주차 Unit 3.3 — 충돌 해결법 1: 체이닝 (Chaining)

다음 포스트

3주차 Unit 4.1 — 추상클래스의 특징

0개의 댓글