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 비교

항목	Tombstone	Backshift
메모리	추가 마커	추가 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 Hashing	ordinal()
Java IdentityHashMap	배열	선형 탐사 + ==	identity
Java ThreadLocalMap	배열	선형 탐사 + WeakRef	GC 친화
Python dict	배열	Perturbation	순서 보존
Rust HashMap	배열	SwissTable	SIMD 최적화
Go map	bucket 그룹	하이브리드	캐시 친화

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 두 방법의 종합 비교

항목	체이닝	오픈 어드레싱
자료구조	배열 + 연결 리스트/트리	배열만
충돌 처리	같은 버킷에 노드 추가	다른 슬롯 탐사
LoadFactor	0.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 필요

트리 변환 가능:
- 체이닝: 한 버킷의 노드들을 Red-Black Tree 로
- 오픈: 트리 만들 위치가 명확하지 않음
- HashDoS 방어의 핵심
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 완주 — 해시 마스터 달성

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

댓글