Hashing

devK08·2026년 1월 5일

hashCode()

Hashing이 필요한 이유

실생활 예시

만약, 내가 도서관에서 "아낌없이 주는 나무"라는 책을 찾으려 한다면?

방법 1. (배열/리스트 방식)
처음부터 끝까지 "아낌없이 주는 나무"라는 제목을 가진 책이 있는지 계속 검증해야한다.
이는 엄청나게 오랜 시간이 걸리게 된다.

방법 2. (Hashing 방식)
도서관 컴퓨터에게 "아낌없이 주는 나무"를 검색한다.
도서관 컴퓨터가 "813.6번"이라고 답하면,
해당 주소로 가서 손쉽게 "아낌없이 주는 나무"를 획득할 수 있다.

이를 컴퓨터 입장에서 생각해보자.

방법 1. (배열/리스트 방식)으로 한다면,
검색시간은 O(n)이 걸릴 것이다.
이는 데이터가 늘어나면 늘어날수록 비효율적이다.

방법 2. (Hashing 방식)으로 한다면,
검색시간은 O(1)이 걸릴 것이다.
이는 데이터가 늘어남과 관계없이 1번만으로 조회가 가능하기 때문에 효율적이다.

Hashing의 3요소

Hashing의 플로우는 다음과 같다.

Key (ex: 아낌없이 주는 나무)
↓
Hash Function
↓
Hash Code
↓
Hash Table
↓
Value (ex: 813.6)

그래서, Hash Function, Hash Code, Hash Table에 대해 깊게 알아보기로 하였다.

Hash Function

정의: Hash Function은 임의의 크기를 가진 데이터를 고정된 크기의 값으로 변환하는 함수이다.

핵심 원리: 같은 입력이 주어지면 항상 같은 출력을 한다.

좋은 Hash Function 조건

1. 균등 분포

Hash Function을 거쳤을 때 결과값이 균등하게 분포되어야 한다.

2. 빠른 계산

Hash 계산이 느리면 O(1)의 의미가 없다.

3. 충돌 최소화

완벽한 충돌은 불가능하므로 여러 필드를 조합하여, 충돌확률을 최소화해야 한다.

예시

SHA-256 (Secure Hash Algorithm)
256bit 고정 길이 출력 (64자리 16진수)
한 글자만 달라도 완전히 다른 해시값
단방향 (역계산 불가능)
Argon2
CPU + 메모리 모두 사용 (GPU/ASIC 공격 방어)
의도적으로 매우 느림 (brute force 방어)
Salt 자동 생성 (같은 비밀번호도 다른 해시)
bcrypt
비밀번호 전용 해시
의도적으로 느림 (brute force 방어)
Salt 자동 생성 (같은 비밀번호도 다른 해시)
강도 조절 가능 (rounds)

Hash Code

정의: Hash Function의 출력값
역할: 데이터를 어디에 조회/저장할지 계산함

갑자기 생긴 궁금증

Hash Code가 int 범위(-21억 ~ 21억)인데, 저장되는 공간도 그만큼 커야 하나?

답: 아니다!
Hash Code는 나머지 연산(%)으로 작은 배열 크기에 맞춘다.

// 나머지 연산의 특성
10 % 3 = 1  // 0, 1, 2 중 하나
25 % 3 = 1  // 0, 1, 2 중 하나
99 % 3 = 0  // 0, 1, 2 중 하나

// 어떤 큰 수든 → 0 ~ (n-1) 범위로!

즉, 변환 방법: index = hashCode % tableSize(Hash Table 크기)

Hash Table

정의: Hash Code를 Index로 사용하는 배열

왜 배열인가?
배열은 Index만 알면 직접 접근이 가능하다 → O(1)

int[] arr = new int[16];
arr[10] = 100;      // O(1) 저장
int value = arr[10]; // O(1) 조회
// Hash Table도 동일한 원리를 사용한다.
table[10] = new TreeNode("Apple", 1000);  // O(1) 저장
TreeNode node = table[10];                 // O(1) 조회

구조

TreeNode<K,V>[] table;  // Bucket Array

static class TreeNode<K, V> {
    final int hash;        // Hash Code
    final K key;           // Key
    V value;               // Value
    TreeNode<K,V> parent;  // Red-Black Tree 구조
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    boolean red;
}

필드	역할
hash	Hash Code
key	원본 Key (Collision 시 비교용)
value	실제 저장 데이터
parent, left, right	Red-Black Tree 구조
red	Red-Black Tree 색상 (균형 유지)

ㅤ

Java 8+ 변화:

Java 7 이전에는 충돌처리를 next 포인터로 LinkedList를 사용했다.

// Java 7 이전
static class Node<K, V> {
    final K key;
    V value;
    Node<K,V> next;  // LinkedList로 연결
}

Java 8부터는 성능 개선을 위해 Red-Black Tree를 사용한다.

// Java 8+
static class TreeNode<K, V> {
    final K key;
    V value;
    TreeNode<K,V> parent, left, right;  // Tree 구조
    boolean red;
}

바꾼 이유

LinkedList: O(n)
Red-Black Tree: O(log n)
충돌 많아도 성능 보장

이 부분은 나중에 충돌 부분에서 더 자세히 다뤄보겠다.

Collision

의미: 서로 다른 Key → 같은 Index로 계산되는 현상

해결방법

Separate Chaining (분리 연결법)

정의: 같은 Index에 충돌 발생 시, 해당 위치에 여러 Node를 연결하여 저장

동작방식:

// Index 10에 충돌 발생
table[10] → Node1 → Node2 → Node3
            Apple   Zebra   Cat

구조:
ㅤCollision 적을 때: LinkedList로 연결 (next 포인터)
ㅤCollision 많을 때: Red-Black Tree로 변환 (left, right 포인터)

저장 과정:
ㅤ1. Index 계산 (예: 10)
ㅤ2. table[10] 확인
ㅤ3. 비어있으면 → 첫 Node 저장
ㅤ4. 이미 있으면 → LinkedList/Tree에 추가

조회 과정:
ㅤ1. Index 계산 (예: 10)
ㅤ2. table[10]부터 탐색 시작
ㅤ3. key.equals()로 실제 Key 비교
ㅤ4. 일치하는 Node 찾으면 value 반환

시간 복잡도:
ㅤ평균: O(1)
ㅤ최악: O(log n) (Java 8+ Red-Black Tree)

Open Addressing (개방 주소법)

정의: 충돌 발생 시, 다른 빈 칸을 찾아서 저장

동작방식:

// Index 10에 충돌 발생
table[10] = 이미 차 있음!

// 다음 빈 칸 찾기
table[11] = 비어있음! → 여기에 저장

구조:
ㅤ한 칸에 하나의 데이터만 저장
ㅤ충돌 시 정해진 규칙으로 다음 위치 탐색

탐색 방법:
ㅤLinear Probing(선형 조사법)
ㅤㅤ규칙: 충돌 시 1칸씩 순차적으로 이동
ㅤㅤ장점:
ㅤㅤㅤ구현이 가장 간단함
ㅤㅤㅤ캐시 효율 좋음 (연속된 메모리 접근)
ㅤㅤㅤ계산 비용 낮음 (단순 덧셈)
ㅤㅤ단점:
ㅤㅤㅤPrimary Clustering (1차 군집화 심각)

ㅤQuadratic Probing(이중 조사법)
ㅤㅤ규칙: 충돌 시 제곱수만큼 이동
ㅤㅤ장점:
ㅤㅤㅤPrimary Clustering 감소
ㅤㅤ단점:
ㅤㅤㅤSecondary Clustering (2차 군집화 심각)

ㅤDouble Hashing(이중 해싱)
ㅤㅤ규칙: 두 번째 Hash Function 사용
ㅤㅤ장점:
ㅤㅤㅤPrimary/Secondary Clustering 모두 최소화
ㅤㅤㅤ가장 균등한 분산
ㅤㅤㅤ같은 hash1이어도 hash2가 다르면 탐사 순서 다름
ㅤㅤ단점:
ㅤㅤㅤ구현 복잡 (Hash Function 2개 필요)
ㅤㅤㅤ계산 비용 높음 (2번 해싱)
ㅤㅤㅤ캐시 효율 낮음 (불규칙한 메모리 접근)

Rehashing 전략

정의: Hash Table이 꽉 차가기 전에 더 큰 배열로 확장하는 과정

문제:

// 초기 상태: 16칸 배열
table = new Node[16];

// 12개 저장 (75% 차있음)
table[0] = data1
table[3] = data2
table[5] = data3
...
table[15] = data12

// 문제: Collision 급격히 증가!
// 성능 저하 O(1) → O(n) or O(log n)

Trigger Strategy(When)

Load Factor 기반 방식

Load Factor = size(실제 저장된 개수) / capacity(배열 크기)
Load Factor가 특정 비율을 넘어가면, Rehashing을 하는 전략

Resize Strategy(How Grow)

배열을 얼마나 확장할 것인가?
방법 1: 2배 증가 (Double)
현재 크기의 2배로 확장
장점:
ㅤAmortized O(1) 보장
ㅤ구현 간단 (비트 연산)
ㅤRehashing 횟수 최소
ㅤ예측 가능 (크기 패턴 명확)
단점:
ㅤ메모리 순간 2배 급증

Migration Strategy(How Move)

데이터를 어떻게 새 배열로 이동시킬 것인가?

All-at-once (한 번에 전체 이동)

Rehashing 시 모든 데이터를 즉시 이동
동작 과정:

1. 새 배열 생성 (32칸)
2. 기존 데이터 모두 이동 (16칸 → 32칸)
3. 기존 배열 제거
4. 완료!

Old (16칸):  [0][1][2]...[15]
              ↓  ↓  ↓     ↓
            모두 즉시 이동!
              ↓  ↓  ↓     ↓
New (32칸):  [0][1][2]...[31]

장점:
ㅤ구현 간단
ㅤ즉시 완료
ㅤ메모리 관리 쉬움 (이동 후 즉시 해제)
ㅤ한 번의 배열만 유지
단점:
ㅤ대용량 데이터 시 수백 ms ~ 수 초 블로킹

Incremental (점진적 이동)

Rehashing을 여러 연산에 걸쳐 조금씩 진행
동작 과정:

매 연산마다 1개 버킷씩 이동

put("A"):  [0] 이동 (1/16 완료)
get("B"):  [1] 이동 (2/16 완료)
put("C"):  [2] 이동 (3/16 완료)
...
put("Z"):  [15] 이동 (16/16 완료!)

→ 16번의 연산에 걸쳐 완료

장점:
ㅤ응답 지연 분산 (한 번에 느려지지 않음)
ㅤ각 연산 시간 일정
ㅤ실시간 서비스에 적합
ㅤ예측 가능한 성능
단점:
ㅤ메모리 2배 오래 유지 (완료까지)

Java HashMap

public class HashMap<K, V> {
    Node<K,V>[] table;      // 저장 배열
    int size;               // 저장 개수
    int threshold;          // Rehashing 임계값 (capacity × 0.75)
    
    static class Node<K,V> {
        int hash;
        K key;
        V value;
        Node<K,V> next;
    }
}

put() 동작

Hash 계산
Index 계산
저장:
- 빈 칸 → 바로 저장
- Collision → LinkedList/Tree 추가
- 같은 Key → 덮어쓰기
확인: size > threshold → resize()

// 예시
map.put("Apple", 100);
// → hash 계산 → index 10 → table[10] 저장 → size 확인

get() 동작

Hash 계산
Index 계산
첫 노드 확인 → 일치하면 반환
아니면 LinkedList/Tree 탐색

시간 복잡도: 평균 O(1), 최악 O(log n)

resize() 동작

새 배열 생성 (2배)
모든 데이터 이동 (비트 연산)
교체

Salt

Salt는 해싱하기 전에 추가하는 랜덤 데이터입니다.
보통, 비밀번호와 같은 컬럼들에 고유한 Salt를 추가하여 보안을 강화합니다.

필요한 이유

Rainbow Table 공격 방어: 미리 계산된 해시값 테이블로는 Salt가 적용된 비밀번호를 역추적할 수 없습니다
동일 비밀번호의 다른 해시값: 같은 비밀번호를 사용하는 사용자들도 각자 다른 Salt로 인해 서로 다른 해시값을 가집니다
무차별 대입 공격(Brute Force) 비용 증가: 각 사용자마다 다른 Salt를 사용하므로 공격자는 각 계정을 개별적으로 공격해야 합니다

저장구조

Salt와 Hashing값을 함께 저장합니다.

Key Stretching

Key Stretching(키 스트레칭)은 해시 함수를 여러 번 반복 적용하여 비밀번호 해싱 속도를 의도적으로 느리게 만드는 기법입니다.

필요한 이유

무차별 대입 공격(Brute Force) 방어: 해싱이 느리면 공격자가 모든 비밀번호 조합을 시도하는 데 오랜 시간이 걸립니다
GPU/ASIC 공격 완화: 빠른 해시 함수(MD5, SHA-1)는 초당 수십억 번 계산 가능하지만, Key Stretching은 이를 수천~수만 배 느리게 만듭니다
약한 비밀번호 보호 강화: 사용자가 짧거나 단순한 비밀번호를 사용해도 추가 보호 제공

bcrypt

특징: 자동 Salt 생성, Cost Factor로 난이도 조절
Cost Factor: 2^n번 반복 (cost=10이면 1,024번, cost=12이면 4,096번)
장점: GPU 공격에 상대적으로 강함 (메모리 사용)

scrypt

특징: 메모리 집약적 (Memory-hard) 설계
장점: GPU/ASIC 공격에 매우 강함
단점: 서버 리소스 소모가 큼

Argon2

특징: 2015 Password Hashing Competition 우승
최신 표준: 현재 가장 권장되는 알고리즘
장점: CPU와 메모리 모두 많이 사용하도록 설계

HashMap vs HashTable vs ConcurrentHashMap

HashMap

특징:

동기화 없음 (Non-synchronized)
Null 허용 (Key 1개, Value 여러 개)
Java 1.2

장점:
ㅤ가장 빠름 (동기화 오버헤드 없음)
ㅤ단순하고 효율적
ㅤNull 사용 가능

단점:
ㅤThread-Safe 아님
ㅤ멀티스레드 환경에서 데이터 손실/오류

사용:
ㅤ단일 스레드 환경
ㅤ로컬 변수

Map<String, User> map = new HashMap<>();

HashTable

특징:

ㅤ전체 동기화 (메서드에 synchronized)
ㅤNull 불허
ㅤJava 1.0 (레거시)

장점:
ㅤThread-Safe

단점:
ㅤ전체 락 → 매우 느림
ㅤ한 스레드만 접근 가능
ㅤNull 불허
ㅤ레거시

사용:
ㅤ사용 금지 (ConcurrentHashMap으로 대체)

Map<String, User> map = new Hashtable<>();

ConcurrentHashMap

특징:

세그먼트(버킷) 단위 동기화
Null 불허
Java 1.5

장점:
ㅤThread-Safe
ㅤ빠른 성능 (버킷별 락)
ㅤ여러 스레드 동시 접근 가능
ㅤ읽기는 락 없음

단점:
ㅤHashMap보다 약간 느림 (단일 스레드)
ㅤNull 불허

사용:
ㅤ멀티 스레드 환경
ㅤ공유 자원
ㅤSpringBoot 기본

Map<String, User> map = new ConcurrentHashMap<>();

비교표

특징	HashMap	Hashtable	ConcurrentHashMap
Thread-Safe	❌	✅	✅
동기화	없음	전체 락	세그먼트 락
Null	✅	❌	❌
성능 (단일)	가장 빠름	느림	빠름
성능 (멀티)	오류	매우 느림	가장 빠름
사용	단일 스레드	❌ 금지	멀티 스레드

성능 비교

단일 스레드 (100만 건):

HashMap:              145ms  ⭐
ConcurrentHashMap:    160ms
Hashtable:            287ms

멀티 스레드 (100만 건, 4개 스레드):

ConcurrentHashMap:    120ms  ⭐
HashMap:              오류
Hashtable:            890ms

선택 가이드

Thread-Safe 필요?
├─ NO  → HashMap
└─ YES → ConcurrentHashMap

로컬 변수 → HashMap
공유 자원 → ConcurrentHashMap
SpringBoot → ConcurrentHashMap

핵심 정리
===========================================
단일 스레드 HashMap
멀티 스레드 ConcurrentHashMap
레거시 코드 Hashtable → ConcurrentHashMap 교체

Spring 실무 활용

// 대략 1000명의 user들
List<User> lists = repo.findAll();

// Resizing 방지
Map<Long, User> userMap =
    new HashMap<>((int) (lists.size() / 0.75f) + 1);

for (User user : lists) {
    userMap.put(user.getId(), user);
}

만약, HashMap에 1000개 정도의 데이터가 온다면,
Resizing을 기본적으로 7번해야한다.
하지만, 처음부터 initialCapacity를 높인다면 Resizing작업을 하지 않아도 되므로 시스템이 최적화된다.

devK08

안녕하세요. 개발자 지망 고등학생입니다.

이전 포스트

Proxy in Java

다음 포스트

Hashing

Hashing이 필요한 이유

실생활 예시

Hashing의 3요소

Hash Function

좋은 Hash Function 조건

1. 균등 분포

2. 빠른 계산

3. 충돌 최소화

예시

Hash Code

갑자기 생긴 궁금증

Hash Table

Collision

해결방법

Separate Chaining (분리 연결법)

Open Addressing (개방 주소법)

Rehashing 전략

Trigger Strategy(When)

Load Factor 기반 방식

Resize Strategy(How Grow)

Migration Strategy(How Move)

All-at-once (한 번에 전체 이동)

Incremental (점진적 이동)

Java HashMap

put() 동작

get() 동작

resize() 동작

Salt

필요한 이유

저장구조

Key Stretching

필요한 이유

bcrypt

scrypt

Argon2

HashMap vs HashTable vs ConcurrentHashMap

HashMap

특징:

HashTable

특징:

ConcurrentHashMap

특징:

비교표

성능 비교

선택 가이드

Spring 실무 활용

Proxy in Java

Java Sorting

0개의 댓글