Unit 3.1 — 해시의 탄생 배경

F-LAB JAVA · 3주차 · Phase 3 · 해시(Hash)의 원리
🚀 Phase 3 시작 — HashMap 의 "왜 O(1)?" 메커니즘 정복

---

📌 학습 목표

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

• 데이터 검색의 시간 복잡도가 왜 O(n) → O(log n) → O(1) 로 진화했나?
• 순차 검색 의 한계는 무엇인가?
• 이진 검색 이 O(log n) 인 메커니즘과 그 제약은?
• 해시 함수 의 정의와 3가지 좋은 조건 은?
• 해시 검색이 어떻게 O(1) 에 도달하나?
• 자바의 hashCode() 메서드 동작은?
• 자바의 주요 클래스 (String, Integer 등) 의 hashCode 구현은?
• 해시 함수의 분포 가 왜 중요한가?
• HashMap 의 hash & (table.length - 1) 이 무엇을 의미하나?

---

🎯 핵심 한 문장

해시는 "키를 정수 인덱스로 매핑하는 함수" 다.
순차 검색의 O(n) 한계를 깨고, 이진 검색의 O(log n) 도 넘어, 단 한 번의 계산으로 위치를 찾는 O(1) 을 가능하게 한다.
그 비결은 수학적 변환 — 키를 숫자로 바꾸고, 그 숫자를 배열 인덱스로 활용한다.
자바의 hashCode() 메서드와 HashMap 의 hash & (table.length - 1) 연산이 모두 이 원리 위에서 동작한다.

비유 — 도서관의 진화

도서관 1.0 (배열):
  책장에 책이 무작위로 꽂혀있음.
  특정 책을 찾으려면 처음부터 차례대로 확인.
  10000권 중에서 평균 5000번 확인 (O(n)).

도서관 2.0 (정렬된 배열):
  책장에 ABC 순으로 정렬.
  중간부터 확인 → 위/아래 결정 → 다시 중간.
  10000권 중에서 약 13번 확인 (O(log n)).

도서관 3.0 (해시 시스템):
  ISBN 으로 책장 번호를 계산.
  "이 책의 ISBN 은 1234567 → 번호 7번 책장".
  10000권이든 100만 권이든 단 1번의 계산 (O(1)).

→ 해시는 검색 방식의 패러다임 전환.

---

🧭 9개 섹션 로드맵

1. 검색의 시간 복잡도 — O(n) → O(log n) → O(1) 진화
2. 순차 검색의 한계
3. 이진 검색의 도약과 제약
4. 해시 함수의 정의와 3가지 좋은 조건
5. 해시가 O(1) 인 메커니즘
6. 자바의 hashCode() 메서드
7. 자바 표준 클래스의 hashCode 구현
8. 해시 함수의 분포와 HashMap 의 비트 연산
9. 면접 + 자기 점검

---

1️⃣ 검색의 시간 복잡도 — O(n) → O(log n) → O(1) 진화

1.1 검색 문제의 본질

검색 문제:
  컬렉션 C 와 키 k 가 주어졌을 때,
  C 안에 k 가 있는지 확인 (또는 그 위치 반환).

성능 지표:
  - 시간 복잡도 (T)
  - 공간 복잡도 (S)
  - 평균 vs 최악

자료구조에 따른 변화:
  - 정렬되지 않은 배열: O(n)
  - 정렬된 배열: O(log n)
  - 해시 테이블: O(1) 평균
  - 트리 (BST): O(log n)
  - B-Tree: O(log n) (디스크 친화)

1.2 검색 알고리즘의 역사

1950년대:
  순차 검색 (Linear Search)
  - 컴퓨터 메모리가 비싸 단순 배열만 활용
  - O(n)

1960년대:
  이진 검색 (Binary Search) 정착
  - 정렬된 배열에서 절반씩 탐색
  - O(log n)
  - 단점: 정렬 비용 + 정적 데이터만

1953년 (Hans Peter Luhn):
  해시 테이블 (Hash Table) 제안
  - IBM 의 텍스트 검색 시스템
  - O(1) 평균
  - 핵심 아이디어: "키를 직접 주소로"

1960~70년대:
  해시 함수 발전
  - 충돌 해결법 (체이닝, 오픈 어드레싱)
  - 다양한 해시 함수 알고리즘

1990년대~:
  자바, 파이썬 등 언어 표준에 포함
  - HashMap, Dictionary, dict
  - 모든 현대 언어의 핵심 자료구조

1.3 시간 복잡도 비교

자료구조	평균 검색	최악 검색	삽입	정렬	메모리
정렬 X 배열	O(n)	O(n)	O(1)	❌	O(n)
정렬된 배열	O(log n)	O(log n)	O(n)	✓	O(n)
BST (균형)	O(log n)	O(log n)	O(log n)	✓	O(n)
해시 테이블	O(1)	O(n)	O(1)	❌	O(n)
Java 8 HashMap	O(1)	O(log n)	O(1)	❌	O(n)

핵심:

• 해시 테이블은 평균 O(1) — 압도적
• 최악 O(n) 은 해시 함수가 나쁠 때
• Java 8+ 는 트리 변환으로 최악 O(log n) 보장

1.4 데이터 크기에 따른 차이

n = 1,000 (1천)
  순차 검색:  평균 500 번
  이진 검색:  약 10 번
  해시 검색:  1 번

n = 1,000,000 (1백만)
  순차 검색:  평균 500,000 번
  이진 검색:  약 20 번
  해시 검색:  1 번

n = 1,000,000,000 (10억)
  순차 검색:  평균 500,000,000 번
  이진 검색:  약 30 번
  해시 검색:  1 번

해시 검색의 강점:

• 데이터 크기와 무관
• 항상 같은 시간
• 빅데이터 시대의 핵심 도구

1.5 자기 점검 답변

해시 검색이 O(1) 인 의미는?

답:
1. 데이터 양과 무관 — n 이 1천이든 1억이든 같은 시간
2. 한 번의 계산 — 해시 함수 적용 + 배열 인덱스 접근
3. 평균적으로 O(1) — 충돌 시 약간의 추가 비용
4. 검색의 패러다임 전환 — "순회" 에서 "직접 접근" 으로

---

2️⃣ 순차 검색의 한계

2.1 순차 검색의 정의

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;   // 찾음
        }
    }
    return -1;   // 못 찾음
}

특징:

• 처음부터 끝까지 순회
• 데이터 정렬 무관
• 가장 단순한 알고리즘

2.2 시간 복잡도 분석

최선의 경우:
  찾는 요소가 첫 번째 위치
  → O(1)

평균의 경우:
  찾는 요소가 중간쯤
  → n/2 회 비교 → O(n)

최악의 경우:
  찾는 요소가 마지막 또는 없음
  → n 회 비교 → O(n)

총평: O(n)

2.3 순차 검색의 장점

1. 단순 구현
   - 5줄 코드
   - 정렬 불필요

2. 작은 데이터에 효율적
   - n < 100 정도면 충분히 빠름
   - 캐시 효율 ↑ (연속 메모리)

3. 자료구조 무관
   - 배열, LinkedList, Stream 모두 동일 패턴
   - 어떤 컬렉션이든 작동

4. 안정적
   - 동일 요소 여러 개면 첫 번째 반환
   - 예측 가능

2.4 순차 검색의 한계

1. n 에 비례하는 시간
   - 1만 → 평균 5천
   - 100만 → 평균 50만
   - 데이터 증가 → 시간 증가

2. 정렬되지 않은 데이터에 대한 유일한 방법
   - 정렬 안 된 데이터는 더 빠른 방법 없음

3. 빈번한 검색에 불리
   - 매번 O(n)
   - 캐시도 큰 도움 안 됨 (랜덤 접근)

4. 분산 시스템에 부적합
   - 데이터 분할 시 모든 노드 검색 필요

2.5 자바의 순차 검색

// List.indexOf 는 순차 검색
List<String> list = new ArrayList<>();
// ... 데이터
int idx = list.indexOf("target");   // O(n)

// List.contains 도 순차 검색
boolean has = list.contains("target");   // O(n)

// Stream 의 anyMatch 도 순차 검색
boolean has = list.stream().anyMatch(s -> s.equals("target"));   // O(n)

// 비교: HashSet 의 contains
Set<String> set = new HashSet<>(list);
boolean has = set.contains("target");   // O(1)

→ List.contains 가 빈번하면 Set 으로 변환해서 O(n) → O(1).

2.6 순차 검색이 유리한 경우

1. 작은 데이터 (n < 50)
   - 해시 오버헤드보다 빠름
   - 캐시 효율 ★

2. 한 번만 검색
   - HashSet 변환 비용 > 검색 비용

3. 정렬 비용이 비싼 경우
   - 한 번 검색하면 끝

4. 순서가 의미 있는 경우
   - "처음 매칭된 것" 찾기

5. 메모리 제약
   - HashSet 의 LoadFactor 0.75 → 메모리 30%↑

2.7 자기 점검 답변

List.contains 와 HashSet.contains 의 차이는?

답:

• List.contains: O(n) — 순차 검색
  • ArrayList: O(n)
  • LinkedList: O(n)
• HashSet.contains: O(1) 평균 — 해시 검색

선택 기준:

• 데이터 작음 (< 100) + 단 한 번 검색 → List
• 데이터 큼 또는 빈번 검색 → Set 으로 변환

---

3️⃣ 이진 검색의 도약과 제약

3.1 이진 검색의 핵심 아이디어

"정렬된 배열에서 중간 부터 확인"

매 단계마다 검색 범위 절반으로 축소:
  처음: n
  1단계: n/2
  2단계: n/4
  3단계: n/8
  ...
  k단계: n / 2^k
  
  n / 2^k = 1 일 때 멈춤
  → k = log₂(n)
  
  → O(log n)

3.2 이진 검색 구현

public static int binarySearch(int[] sorted, int target) {
    int low = 0;
    int high = sorted.length - 1;
    
    while (low <= high) {
        int mid = (low + high) >>> 1;   // 오버플로우 방지
        
        if (sorted[mid] == target) {
            return mid;
        } else if (sorted[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    return -1;
}

>>> 1 의 의미:

• 부호 없는 우측 시프트 (= 2 로 나눔)
• (low + high) / 2 와 비슷하지만 오버플로우 안전
• low + (high - low) / 2 와 동일 효과

3.3 이진 검색의 진행 시각화

정렬된 배열: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 13

Step 1:
  low=0, high=9, mid=4
  arr[4] = 9 < 13 → low = mid+1 = 5

Step 2:
  low=5, high=9, mid=7
  arr[7] = 15 > 13 → high = mid-1 = 6

Step 3:
  low=5, high=6, mid=5
  arr[5] = 11 < 13 → low = mid+1 = 6

Step 4:
  low=6, high=6, mid=6
  arr[6] = 13 == 13 ✓ 반환 6

총 4번의 비교 (vs 순차 검색 7번)

3.4 시간 복잡도 비교

n 개 데이터 검색:

n = 1,000:      log₂(1000) ≈ 10
n = 1,000,000:  log₂(1M) ≈ 20
n = 1,000,000,000: log₂(1B) ≈ 30

→ n 이 10배 늘어도 비교 횟수는 3-4 회 증가
→ 매우 효율적

3.5 이진 검색의 제약

1. 정렬된 데이터에만 사용 가능
   - 정렬 비용 O(n log n) 필요
   - 데이터 변경 시 재정렬

2. 인덱스 접근이 빠른 자료구조에만 효율적
   - 배열, ArrayList: O(1) 접근 → 이진 검색 O(log n)
   - LinkedList: O(n) 접근 → 이진 검색 O(n log n) → 무의미

3. 정적 데이터에 유리
   - 빈번한 삽입/삭제 → 정렬 유지 비용 ↑
   - 동적 데이터엔 BST 또는 해시 권장

4. 메모리 캐시 효율
   - 점프하는 접근 패턴 → 캐시 미스 가능
   - 작은 데이터엔 순차 검색이 더 빠를 수도

3.6 자바의 이진 검색

// 정렬된 배열
int[] sorted = {1, 3, 5, 7, 9};
int idx = Arrays.binarySearch(sorted, 7);   // 3

// 정렬된 List
List<Integer> list = List.of(1, 3, 5, 7, 9);
int idx = Collections.binarySearch(list, 7);   // 3

// 못 찾으면 음수 반환:
//   -(삽입 위치) - 1
int idx = Arrays.binarySearch(sorted, 4);   // -3 (= 인덱스 2 에 삽입)

Arrays.binarySearch 의 반환:

• 찾음 → 양수 인덱스
• 못 찾음 → 음수 (-삽입_위치 - 1)
• 음수에서 삽입 위치 추출: -result - 1

3.7 이진 검색 vs 해시 검색

항목	이진 검색	해시 검색
평균 시간	O(log n)	O(1)
최악 시간	O(log n)	O(n) (또는 O(log n) Java 8+)
정렬 필요	✓	❌
삽입 비용	O(n)	O(1)
범위 검색	✓ (강점)	❌
정렬 순회	✓	❌
메모리	O(n)	O(n) × 1.33 (LoadFactor)

선택:

• 자주 검색 + 자주 변경 → 해시 (HashMap)
• 정렬된 순회 또는 범위 검색 → 이진 검색 또는 TreeMap

3.8 자기 점검 답변

이진 검색이 LinkedList 에선 의미 없는 이유는?

답:

• LinkedList 의 get(i) 는 O(n) (Node 사슬 따라가기)
• 이진 검색은 매 단계마다 인덱스 접근 → O(n) × log n = O(n log n)
• 순차 검색 (O(n)) 보다 더 느림
• ArrayList 처럼 O(1) 인덱스 접근 이 가능한 자료구조여야 의미 있음

→ RandomAccess 마커 인터페이스가 있는 자료구조만.

---

4️⃣ 해시 함수의 정의와 3가지 좋은 조건

4.1 해시 함수의 정의

해시 함수 (Hash Function):
  
  h: K → ℤ
  
  키 (K) 를 정수 (ℤ) 로 매핑하는 함수.
  보통은 0 이상의 정수 또는 큰 정수 범위.

자바의 해시 함수:
  
  Object.hashCode(): K → int
  
  객체를 32비트 정수로 매핑.

4.2 해시 함수의 동작 흐름

1. 키 입력:
   String key = "BL-001";

2. 해시 함수 적용:
   int hash = key.hashCode();
   // 예: 1234567890

3. 배열 인덱스 변환:
   int index = hash & (table.length - 1);
   // 예: 1234567890 & 15 = 2

4. 배열 인덱스 접근:
   table[2] → 저장된 값

→ "키 → 정수 → 인덱스" 의 3단계.

4.3 좋은 해시 함수의 3가지 조건

[조건 1] 결정적 (Deterministic)
  같은 입력 → 항상 같은 출력
  
  예:
    "BL-001".hashCode()  → 12345 (항상)
    "BL-001".hashCode()  → 12345 (같음)
  
  위반 시:
    검색 불가능 (저장 위치를 못 찾음)

[조건 2] 균등 분포 (Uniform Distribution)
  다양한 입력 → 결과가 균등하게 분포
  
  나쁨:
    h("A") = 1, h("B") = 1, h("C") = 1  
    → 모두 같은 버킷 → 충돌 빈번 → O(n)
  
  좋음:
    h("A") = 1, h("B") = 17, h("C") = 42
    → 분산 → O(1)

[조건 3] 빠른 계산 (Fast Computation)
  해시 계산 자체가 비싸지 않아야
  
  나쁨:
    SHA-256 같은 암호학적 해시 (느림)
    → 검색마다 수백 사이클
  
  좋음:
    간단한 산술 + 비트 연산
    → 수십 사이클

추가 조건 (덜 중요):

• 확산성 (Avalanche): 입력 1비트 변경 시 출력 절반 비트 변경
• 충돌 저항성: 다른 입력이 같은 해시값 가질 확률 낮음

4.4 나쁜 해시 함수의 예

// 예시 1 — 너무 단순
public int badHash1(String s) {
    return s.length();
    // 길이만으로 → 충돌 빈번
    // "abc", "xyz" 모두 3
}

// 예시 2 — 너무 비싸
public int badHash2(String s) {
    int sum = 0;
    for (int i = 0; i < 1000; i++) {
        sum += s.hashCode();   // 의미 없는 반복
    }
    return sum;
    // 느림
}

// 예시 3 — 비결정적
public int badHash3(String s) {
    return s.hashCode() + new Random().nextInt();
    // 매번 다른 결과 → 검색 불가
}

// 예시 4 — 분포 나쁨
public int badHash4(String s) {
    return s.charAt(0);
    // 첫 글자만 사용
    // "BL-001", "BL-002", "BL-003" → 모두 같은 해시
}

4.5 좋은 해시 함수의 예 — DJB2

// DJB2 — 단순하지만 분포 좋음
unsigned long djb2(unsigned char *str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c;  // hash * 33 + c
    }
    return hash;
}

특징:

• 매 글자마다 hash × 33 + 글자
• 33 은 경험적으로 좋은 배수
• 빠름 + 균등 분포

4.6 자바 String 의 hashCode — 좋은 예

// String 의 hashCode 구현
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char[] val = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;   // 캐싱
    }
    return h;
}

핵심:

• 31 의 활용 (h × 31 + char)
• 31 은 소수 + 31 * x 는 (x << 5) - x 로 최적화 가능
• 결정적 + 균등 분포 + 빠른 계산
• 결과 캐싱 (불변 객체이므로 안전)

4.7 자기 점검 답변

좋은 해시 함수의 3가지 조건은?

답:
1. 결정적 (Deterministic) — 같은 입력 → 같은 출력
2. 균등 분포 (Uniform Distribution) — 출력이 골고루
3. 빠른 계산 (Fast Computation) — 계산 자체 비용 ↓

3가지 모두 만족해야 해시 검색의 O(1) 가능.

---

5️⃣ 해시가 O(1) 인 메커니즘

5.1 단계별 추적

요구: HashMap 에서 "BL-001" 키의 값 조회

Step 1: 해시 계산
  "BL-001".hashCode()
  → 약 1234567890 (32비트 int)
  비용: O(1) — 문자열 길이에 비례 (실제로는 매우 빠름)

Step 2: 인덱스 변환
  int index = hash & (table.length - 1);
  → 약 1234567890 & 15 = 2 (table.length = 16 이라면)
  비용: O(1) — 단일 비트 연산

Step 3: 버킷 접근
  Node node = table[2];
  비용: O(1) — 배열 인덱스 접근

Step 4: 버킷 내 검색
  Case A: 버킷이 null → 없음
  Case B: 버킷의 첫 노드 = 키 매칭 → 반환
  Case C: 체이닝 → 노드들 순회 (충돌)
  
  평균 비용: O(1) — 버킷당 노드 수 ≈ LoadFactor (0.75)
  최악 비용: O(n) (Java 7) 또는 O(log n) (Java 8+ 트리)

총 비용: O(1) 평균

5.2 핵심 통찰

해시의 마법:
  
  "키 → 정수 → 인덱스 → 직접 접근"
  
  배열의 인덱스 접근 (O(1)) 을 키 기반 검색에 활용.
  
  순차 검색이 "전체 순회" 라면
  해시 검색은 "수학적 위치 계산".

5.3 LoadFactor 와 평균 충돌

LoadFactor = size / capacity

기본: 0.75 (HashMap)

의미:
  capacity 16, LoadFactor 0.75
  → size 12 까지 채우고 확장 시작
  → 평균 버킷당 12/16 = 0.75 개

확장 후:
  capacity 32, size 13
  → 평균 13/32 = 0.4 개 (확장 후 줄어듦)
  → 다시 24 까지 차면 확장

평균 버킷당 노드 수가 1 미만 → 충돌 적음 → O(1) 유지.

5.4 데이터 양에 따른 성능

n = 1,000:
  표준 HashMap: capacity 약 1365, 평균 버킷 < 1 노드
  검색 시간: ~ 50 ns

n = 1,000,000:
  표준 HashMap: capacity 약 1,365,000, 평균 버킷 < 1 노드
  검색 시간: ~ 50 ns
  (수확 capacity 확장 작업이 누적 비용)

n = 1,000,000,000:
  표준 HashMap: capacity 약 1.36B, 평균 버킷 < 1 노드
  검색 시간: ~ 100 ns (캐시 미스 가능)

→ 데이터가 1000배 늘어도 검색 시간은 거의 동일.

5.5 해시 검색의 빠른 이유 종합

1. 수학적 변환 (해시 함수)
   - 키를 정수로 즉시 변환
   - 비교 없이 위치 계산

2. 배열의 O(1) 인덱스 접근
   - 메모리 주소 직접 계산
   - 하드웨어 친화적

3. 작은 평균 충돌
   - LoadFactor 0.75 → 버킷당 < 1 노드
   - 추가 비교 거의 없음

4. 비교 횟수 최소
   - 평균 0~1 회의 equals 호출
   - 키 매칭이 빠르게 종료

5.6 해시의 트레이드오프

장점:
  ✓ O(1) 평균 검색
  ✓ 삽입도 O(1)
  ✓ 데이터 크기 무관
  ✓ 캐시 자료구조의 표준

단점:
  ✗ 순서 없음
  ✗ 범위 검색 불가
  ✗ 메모리 ~ 33% 초과 사용
  ✗ 해시 함수 품질에 의존
  ✗ 최악의 경우 O(n)

5.7 자기 점검 답변

해시 테이블이 O(1) 인 진짜 이유는?

답:
1. 해시 함수가 키를 정수로 매핑 (O(1) 계산)
2. 정수를 배열 인덱스로 변환 (비트 연산 O(1))
3. 배열의 직접 접근 (O(1) 메모리 주소 계산)
4. 버킷 내 충돌 적음 (LoadFactor 로 평균 < 1 노드)

→ 4단계가 모두 O(1) → 전체 O(1).

---

6️⃣ 자바의 hashCode() 메서드

6.1 hashCode() 메서드 정의

public class Object {
    public native int hashCode();
    // 모든 클래스의 부모
    // 기본은 객체의 메모리 주소 기반 (identityHashCode)
}

특징:

• 모든 객체 에 hashCode() 메서드 보유
• 기본 구현은 객체 식별 (참조 기반)
• 사용자가 오버라이드 가능

6.2 hashCode() 와 equals() 의 계약

Object 클래스의 명세:

1. 일관성:
   객체 상태 안 바뀌면 hashCode 도 안 바뀌어야

2. equals 와의 일관성:
   x.equals(y) == true 이면 x.hashCode() == y.hashCode()
   (반대는 성립 안 해도 됨)

3. 위반 시:
   HashMap, HashSet 동작 깨짐
   Set 에 추가 후 contains false
   Map.get 결과 null

6.3 hashCode() 의 기본 구현

// Object 의 기본 hashCode (Hotspot JVM)
// → identityHashCode
// → 객체의 메모리 주소 기반 (실제로는 더 복잡한 계산)

Shipment s1 = new Shipment(1L);
Shipment s2 = new Shipment(1L);

s1.hashCode();   // 예: 1854731488
s2.hashCode();   // 예: 1252585652
// 다름! (다른 객체)

s1.equals(s2);   // false (기본 equals 도 참조 비교)

→ 기본 구현은 객체별로 다른 값 (참조 동일성).

6.4 hashCode() 오버라이드 필요성

// equals 오버라이드 (id 기반)
public class Shipment {
    private Long id;
    
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Shipment)) return false;
        return id.equals(((Shipment) o).id);
    }
    
    // ❌ hashCode 안 오버라이드
}

Set<Shipment> set = new HashSet<>();
Shipment s1 = new Shipment(1L);
Shipment s2 = new Shipment(1L);

s1.equals(s2);   // true (오버라이드한 equals)
s1.hashCode() == s2.hashCode();   // false (기본 hashCode)

set.add(s1);
set.contains(s2);   // false! 못 찾음

문제:

• equals 로 같다고 했지만 hashCode 다름
• HashMap 이 다른 버킷에 저장
• contains 시 다른 버킷 검색 → 못 찾음

해결: equals + hashCode 둘 다 오버라이드.

6.5 올바른 hashCode() 구현 패턴

// 패턴 1: Objects.hash (Java 7+)
public class Shipment {
    private Long id;
    private String blNo;
    
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Shipment)) return false;
        return Objects.equals(id, ((Shipment) o).id);
    }
}

// 패턴 2: 수동 (성능 최적화)
public class Shipment {
    private Long id;
    private String blNo;
    
    @Override
    public int hashCode() {
        int result = 1;
        result = 31 * result + (id == null ? 0 : id.hashCode());
        return result;
    }
}

// 패턴 3: Lombok
@EqualsAndHashCode(of = "id")
public class Shipment {
    private Long id;
    private String blNo;
}

// 패턴 4: Record (Java 14+)
public record Shipment(Long id, String blNo) {
    // equals + hashCode 자동 생성 (모든 필드 기반)
}

6.6 Objects.hash 의 내부

public final class Objects {
    public static int hash(Object... values) {
        return Arrays.hashCode(values);
    }
}

public final class Arrays {
    public static int hashCode(Object[] a) {
        if (a == null) return 0;
        int result = 1;
        for (Object element : a) {
            result = 31 * result + (element == null ? 0 : element.hashCode());
        }
        return result;
    }
}

핵심:

• 매개변수 가변 길이 (varargs)
• 31 의 배수 계산
• null 안전 (element == null ? 0 : ...)

6.7 hashCode 와 메모리 비용

가변 객체에 hashCode 매번 계산하면 비용 ↑

해결책:
  - 불변 객체 + 캐싱

예: String 의 hashCode
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        // ... 계산
        hash = h;   // 캐싱
    }
    return h;
}

String 은 불변이라 캐싱 안전.
사용자 정의 클래스도 불변이면 캐싱 권장.

6.8 hashCode 가 모든 클래스에 필요한 이유

hashCode 가 필요한 곳:
  - HashMap 의 키
  - HashSet 의 요소
  - LinkedHashMap, LinkedHashSet
  - ConcurrentHashMap
  - Hashtable
  - WeakHashMap, IdentityHashMap
  - Caffeine, Guava 등 캐시 라이브러리

→ 자바의 거의 모든 해시 기반 자료구조.

오버라이드 안 하면:
  - 객체별로 다른 hashCode → 다른 객체로 취급
  - 의도와 다른 동작

6.9 자기 점검 답변

equals 와 hashCode 를 함께 오버라이드해야 하는 이유는?

답:
1. Object 클래스의 명세:

• x.equals(y) → x.hashCode() == y.hashCode()
• 한 쪽만 오버라이드하면 명세 위반

2. HashMap, HashSet 의 동작:

   • hashCode 로 버킷 위치 결정
   • equals 로 버킷 내 매칭 확인
   • 둘 다 일관되어야 정확한 동작

3. 흔한 버그 회피:

   • 추가 후 contains false
   • Map.get null
   • 디버깅 어려움

→ 항상 둘 다 함께 오버라이드.

---

7️⃣ 자바 표준 클래스의 hashCode 구현

7.1 String 의 hashCode

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char[] val = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

특징:

• 모든 문자 사용
• 31 의 배수 (홀수 소수)
• 결과 캐싱 (hash 필드)
• 첫 호출 후 재계산 안 함

왜 31?

• 소수 (다른 수와 합성수 안 됨)
• 홀수 (짝수면 시프트 시 정보 소실)
• 31 * x = (x << 5) - x 로 빠르게 계산

7.2 Integer 의 hashCode

public int hashCode() {
    return Integer.hashCode(value);
}

public static int hashCode(int value) {
    return value;
    // 자기 자신 반환
}

특징:

• 자기 자신 을 hashCode 로 사용
• 단순 + 빠름
• int 가 32비트이므로 hashCode 도 32비트 그대로

7.3 Long 의 hashCode

public int hashCode() {
    return Long.hashCode(value);
}

public static int hashCode(long value) {
    return (int)(value ^ (value >>> 32));
    // 상위 32비트 XOR 하위 32비트
}

특징:

• 64비트를 32비트로 압축
• XOR 로 정보 보존
• 상하 비트 골고루 사용

7.4 Double 의 hashCode

public int hashCode() {
    return Double.hashCode(value);
}

public static int hashCode(double value) {
    long bits = doubleToLongBits(value);
    return (int)(bits ^ (bits >>> 32));
}

특징:

• 비트 패턴을 long 으로 변환
• Long.hashCode 같은 패턴
• IEEE 754 표준 활용

7.5 Boolean 의 hashCode

public int hashCode() {
    return Boolean.hashCode(value);
}

public static int hashCode(boolean value) {
    return value ? 1231 : 1237;
}

특징:

• true → 1231
• false → 1237
• 의도적으로 큰 소수 사용 (다른 hashCode 와 충돌 회피)

7.6 LocalDate 의 hashCode

@Override
public int hashCode() {
    int yearValue = year;
    int monthValue = month;
    int dayValue = day;
    return (yearValue & 0xFFFFF800) ^ ((yearValue << 11) + (monthValue << 6) + dayValue);
}

특징:

• year, month, day 비트 시프트 결합
• 다양한 날짜에 대해 균등 분포
• 같은 날짜는 같은 hashCode

7.7 List 의 hashCode (List.hashCode())

// AbstractList 의 hashCode
public int hashCode() {
    int hashCode = 1;
    for (E e : this) {
        hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
    }
    return hashCode;
}

특징:

• 모든 요소의 hashCode 결합
• 순서 의미 (List 의 본질)
• 31 의 배수 패턴

7.8 Set 의 hashCode (Set.hashCode())

// AbstractSet 의 hashCode
public int hashCode() {
    int h = 0;
    Iterator<E> i = iterator();
    while (i.hasNext()) {
        E obj = i.next();
        if (obj != null)
            h += obj.hashCode();
    }
    return h;
}

특징:

• 모든 요소의 hashCode 합 (XOR 아님, 단순 합)
• 순서 무관 (Set 의 본질)
• 다른 순서여도 같은 hashCode

7.9 hashCode 표준 패턴

클래스	hashCode 패턴
String	모든 char × 31 의 누적
Integer	값 자체
Long	상위 32 XOR 하위 32
Double	비트 표현 → Long 패턴
Boolean	1231 또는 1237
LocalDate	y, m, d 시프트 + XOR
List	모든 요소 × 31
Set	모든 요소 합

→ 균등 분포 + 빠른 계산 의 다양한 패턴.

7.10 자기 점검 답변

Integer 의 hashCode 가 단순히 자기 자신을 반환하는 이유는?

답:
1. int 자체가 이미 32비트 정수 → hashCode 의 자연스러운 표현
2. 균등 분포 — 정수가 골고루 분포하면 hashCode 도 분포
3. 빠름 — 계산 없이 반환
4. 결정적 — 같은 int 는 같은 hashCode

추가:

• 0, 1, 2, ... 같은 작은 값이 자주 쓰임
• HashMap 의 hash & (length-1) 은 하위 비트만 사용
• 작은 정수들이 분포는 좋지 않을 수 있음
• HashMap 이 별도 hash() 함수로 추가 처리 (다음 섹션)

---

8️⃣ 해시 함수의 분포와 HashMap 의 비트 연산

8.1 HashMap 의 hash() 메서드

// HashMap 내부 (Java 8+)
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    //                          ↑                    ↑
    //                          hashCode 호출        상위 16 XOR 하위 16
}

분석:
1. null 키 → 0 (HashMap 만 null 키 1개 허용)
2. hashCode() 호출
3. 상위 16 비트와 하위 16 비트 XOR

8.2 왜 상위 16 XOR?

문제:
  HashMap 의 인덱스 계산:
    index = hash & (table.length - 1)
  
  table.length 가 16 이면 length-1 = 15 = 0x0000000F
  → hash 의 하위 4비트만 사용
  
  hashCode 가 0x12345678 이라면:
  → 하위 4비트 (8) 만 사용
  → 상위 비트 정보 손실

해결:
  hash ^= hash >>> 16
  → 상위 16비트를 하위 16비트에 XOR
  → 상위 비트 정보도 활용
  → 분포 개선

시각화:

원래 hashCode: 0x12345678 = 0001 0010 0011 0100 0101 0110 0111 1000

>>> 16 후:    0x00001234 = 0000 0000 0000 0000 0001 0010 0011 0100

XOR 결과:     0x1234444C = 0001 0010 0011 0100 0100 0100 0100 1100

→ 하위 16비트가 상위 16비트 정보 포함
→ 작은 table.length 에서도 분포 양호

8.3 인덱스 계산

// HashMap 의 put 내부
int index = (n - 1) & hash;
//          ↑      ↑
//          length-1  앞서 계산한 hash

왜 & (n - 1)?

• n 이 2의 거듭제곱일 때, % n 과 동등
• 비트 연산이 모듈로 (%) 보다 빠름
• HashMap 의 capacity 는 항상 2의 거듭제곱 (16, 32, 64, 128, ...)

예시:

n = 16, n - 1 = 15 = 0b1111

hash = 0x1234444C = 0001 0010 0011 0100 0100 0100 0100 1100

hash & 15:
  0001 0010 0011 0100 0100 0100 0100 1100
& 0000 0000 0000 0000 0000 0000 0000 1111
─────────────────────────────────────────
  0000 0000 0000 0000 0000 0000 0000 1100 = 12

→ table[12] 에 저장

8.4 왜 capacity 가 2의 거듭제곱?

이유 1: 비트 연산
  - hash & (n-1) 로 빠른 모듈로
  - hash % n 보다 빠름

이유 2: 분포 균등
  - n 이 소수가 아니어도 됨 (위의 hash() 함수가 해결)
  - 단순한 비트 마스크

이유 3: 확장 효율
  - 2배 확장 시 비트 시프트만 (n << 1)
  - 재해싱 시 비트 검사로 위치 결정

8.5 충돌의 원인

충돌 = 다른 키가 같은 버킷에 도착

원인 1: hashCode 충돌
  서로 다른 키가 같은 hashCode
  → 별도 처리 불가

원인 2: 인덱스 충돌
  다른 hashCode 지만 인덱스 계산 후 같은 버킷
  hash1 & 15 == hash2 & 15
  → table.length 가 작으면 빈번

원인 3: 나쁜 hashCode
  hashCode 가 균등하게 분포 안 됨
  → 특정 버킷에 집중

8.6 HashMap 의 capacity 확장 과정

초기 capacity: 16

LoadFactor 0.75 → threshold = 12

크기 12 도달 시:
  1. 새 배열 생성 (capacity × 2 = 32)
  2. 모든 노드 재해싱
  3. 새 배열에 재배치
  
  재해싱:
    이전: hash & 15
    이후: hash & 31
    → 비트 1개 추가 → 위치 변경 가능

threshold 갱신: 24 (32 × 0.75)

8.7 Java 8+ 의 트리 변환

한 버킷에 노드 ≥ 8:
  → 연결 리스트 → Red-Black Tree
  → 그 버킷의 검색이 O(n) → O(log n)

한 버킷에 노드 < 6:
  → 트리 → 연결 리스트
  → 메모리 절약

조건:
  - capacity ≥ 64 일 때만 트리 변환
  - 작은 HashMap 은 확장이 더 효과적

8.8 분포 검증 코드

public class HashDistribution {
    public static void main(String[] args) {
        Map<Integer, Integer> distribution = new HashMap<>();
        int capacity = 16;
        
        for (int i = 0; i < 1000; i++) {
            String key = "BL-" + String.format("%04d", i);
            int hash = key.hashCode() ^ (key.hashCode() >>> 16);
            int index = hash & (capacity - 1);
            distribution.merge(index, 1, Integer::sum);
        }
        
        // 결과 출력
        distribution.entrySet().stream()
            .sorted(Map.Entry.comparingByKey())
            .forEach(e -> System.out.println("Bucket " + e.getKey() + ": " + e.getValue()));
    }
}

// 출력 예시 (capacity 16):
// Bucket 0: 62
// Bucket 1: 65
// Bucket 2: 60
// ...
// 평균 62.5 (1000 / 16)
// 균등 분포 확인

8.9 자기 점검 답변

HashMap 의 hash & (n-1) 가 hash % n 과 같은 이유는?

답:

• n 이 2의 거듭제곱 일 때만 같음
• 예: n = 16 = 2^4
• hash % 16 = hash & 15 (= hash & (16-1))
• 이유: n 의 이진수가 10000 → n-1 = 01111 → 하위 비트만 추출
• 비트 연산이 모듈로 연산보다 빠름

만약 n 이 2의 거듭제곱 아니면:

• hash & (n-1) 이 hash % n 과 다름
• 분포가 깨질 수 있음
• → 항상 2의 거듭제곱 유지

---

9️⃣ 면접 + 자기 점검

9.1 면접 단골 질문 매핑

Q	핵심 답변
해시 검색이 O(1) 인 이유?	키 → 정수 → 인덱스 → 배열 직접 접근
좋은 해시 함수 3가지 조건?	결정적, 균등 분포, 빠른 계산
순차/이진/해시 비교?	O(n) / O(log n) / O(1)
이진 검색의 제약?	정렬 필요, 랜덤 액세스 필요
equals 와 hashCode 의 계약?	equals true → hashCode 같음
Object 의 기본 hashCode?	메모리 주소 기반 (identityHashCode)
String 의 hashCode?	모든 char × 31 누적, 캐싱
Integer 의 hashCode?	자기 자신
Long 의 hashCode?	상위 32 XOR 하위 32
HashMap 의 hash 메서드?	hashCode ^ (hashCode >>> 16)
왜 capacity 2의 거듭제곱?	& (n-1) 로 빠른 모듈로
왜 31 을 곱하나?	소수 + 홀수 + (x<<5)-x 최적화

9.2 자기 점검 체크리스트

기본 이해

• 검색 알고리즘 진화를 안다 (O(n) → O(log n) → O(1))
• 해시 함수의 정의와 3가지 조건을 안다
• 해시 검색의 4단계 (해시→인덱스→버킷→매칭) 를 안다
• 이진 검색의 제약 (정렬, 랜덤 액세스) 을 안다
• equals + hashCode 계약을 안다

hashCode 구현

• Object 의 기본 hashCode 의미를 안다
• String/Integer/Long 등의 hashCode 패턴을 안다
• Objects.hash 활용법을 안다
• Lombok @EqualsAndHashCode 활용
• Record 의 자동 hashCode 를 안다

HashMap 내부

• HashMap.hash() 의 비트 시프트 의미를 안다
• capacity 가 2의 거듭제곱인 이유를 안다
• hash & (n-1) 의 의미를 안다
• LoadFactor 0.75 의 영향을 안다
• Java 8+ 트리 변환 조건을 안다

면접 대비

• "왜 해시가 O(1)?" 5분 답변
• 좋은 해시 함수 3가지 조건
• String.hashCode 의 31 의미
• HashMap 의 비트 연산 설명
• equals + hashCode 위반 시 발생 문제

9.3 추가 심화 질문

Q1: hashCode 가 음수일 수 있는가?

"a".hashCode();   // 97
"z".hashCode();   // 122

// 긴 문자열은?
"some long string".hashCode();   // 가능 (계산 결과)

// int 범위: -2,147,483,648 ~ 2,147,483,647

답:

• hashCode 의 반환 타입은 int
• 음수 가능
• HashMap 은 hash & (n-1) 로 양수 인덱스 확보

Q2: 다른 객체가 같은 hashCode 가질 수 있는가?

답:

• 네, 충돌 가능 (Pigeonhole Principle, Unit 3.2 에서 자세히)
• 자바 int 범위: 약 42억
• 가능한 String 개수: 무한대
• 충돌 불가피
• 그래서 equals 와 같이 사용

Q3: 사용자 정의 hashCode 가 0 이면 문제?

답:

• HashMap 동작 자체엔 문제 없음
• 단, 모든 키가 같은 hashCode (0) → 모두 같은 버킷
• 최악의 경우 발생 → O(n) 검색
• 좋은 hashCode 구현 권장

Q4: hashCode 캐싱이 위험한 경우?

답:

• mutable 객체 가 캐싱하면 위험
• 객체 변경 시 hashCode 변경되어야 하는데 캐시 그대로
• String 이 캐싱하는 건 안전 (immutable)
• 사용자 정의 클래스 캐싱은 immutable 일 때만

---

🎯 핵심 요약 — 3줄 정리

1. 해시는 검색의 패러다임 전환

• 순차 O(n) → 이진 O(log n) → 해시 O(1)
• 키를 정수 인덱스로 매핑
• 단 한 번의 계산 + 배열 직접 접근

2. 좋은 해시 함수 3가지 조건

• 결정적 (같은 입력 → 같은 출력)
• 균등 분포 (출력이 골고루)
• 빠른 계산 (해시 자체 비용 ↓)

3. 자바 해시의 토대

• Object.hashCode() — 모든 클래스에
• HashMap.hash() — 비트 시프트로 분포 개선
• hash & (n-1) — 2의 거듭제곱 capacity 활용
• equals + hashCode 계약 — 항상 함께

---

📚 다음으로...

Unit 3.2 — 해시 충돌 (Hash Collision)

이번 Unit 에서 해시의 탄생 배경을 봤다면, 다음은 충돌의 발생 과 그 의미.

• 비둘기집 원리
• 충돌이 불가피한 이유
• Perfect Hashing 의 한계
• 충돌이 잦으면 성능 저하 (O(1) → O(n))
• 충돌 해결법의 두 갈래 (체이닝 vs 오픈 어드레싱)

Phase 3 진행 상황

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

3주차 누적 진행

✅ Phase 1 — Pass by Value (1.1 ~ 1.3 완주)
✅ Phase 2 — 컬렉션 프레임워크 (2.1 ~ 2.6 완주)
🚀 Phase 3 — 해시의 원리 (1/4 진행)

총: 10/43 Unit 작성 (약 23%)

---