8. Hashing

Hashing

• 데이터를 빠르게 탐색하기 위한 방법
• 특정 키(key)를 해시 함수(hash function) 에 넣어
  → 해시 값(hash value) 또는 주소(address) 를 계산하고,
  그 위치에 데이터를 저장하거나 찾아옴.

즉, “키 → 해시 함수 → 인덱스(주소)” 로 바로 접근 가능하기 때문에
평균 O(1) 의 접근 속도를 가짐.

 

- 기본 구조

key ─▶ hash function ─▶ hash value ─▶ hash table[index]

 

예시:

• key = “cat”
• hash("cat") = 3
• ⇒ 3번 인덱스에 “cat” 저장

 

- 해시 테이블(Hash Table)

• 배열(Array) 기반의 자료구조
• 각 원소는 (key, value) 쌍으로 저장됨
• 인덱스를 해시 함수로 계산해 접근

장점	단점
탐색, 삽입, 삭제 평균 시간복잡도: O(1) 대규모 데이터 검색에 매우 효율적	해시 충돌(Hash Collision) 발생 가능 해시 함수나 테이블 크기 설계가 중요

 

- 해시 충돌(Collision)

서로 다른 두 키가 같은 해시 값으로 계산되는 현상

 

예: hash("cat") = 3 // hash("dog") = 3

 

 충돌 해결 방법

방식	설명
Open Addressing	빈 공간을 찾아 재배치 (예: Linear / Quadratic probing)
Chaining	같은 인덱스에 연결 리스트로 여러 값 저장
Rehashing	새로운 해시 함수를 사용해 다시 해싱

---

Static Hashing (정적 해싱)

해시 테이블의 크기와 해시 함수가 고정된 방식

• 테이블이 꽉 차면 충돌이 증가하고, 비면 공간이 낭비됨.

즉, 한 번 구조가 만들어지면 크기나 함수가 변하지 않음.

 

작동 방식

• 해시 함수: h(K) = K mod M (M은 고정된 버킷 개수)
• 데이터가 증가하면 충돌이 많아지고,
  삭제가 많으면 공간이 낭비됨.

장점	단점
구현이 간단하고 빠름	데이터 크기 변화에 비효율적, 충돌 처리 필요

: 정해진 데이터 크기(고정 크기 파일 등)

 

---

Dynamic Hashing (동적 해싱)

데이터 양의 증가/감소에 따라 해시 테이블 크기를 동적으로 조정하는 방식

• 주로 Extendible Hashing, Linear Hashing 기법이 사용됨

즉, 테이블이 커지면 새로운 해시 함수나 버킷을 추가해 자동으로 확장하는 방식

 

- Linear Hashing (선형 해싱)

• 디렉토리 없이 버킷을 순차적으로 확장
• 테이블 전체를 한 번에 확장하지 않고, 매 삽입 시 조금씩 확장 (점진적 확장 방식)

== “확장이 필요할 때마다 한 버킷씩 순차적으로 나누는 방식.”

메모리 효율적이고, 시스템 과부하를 방지할 수 있음.

 

• 버킷을 순서대로 하나씩 분할(split)
• 해시 함수가 단계별로 조금씩 바뀜
• Rehashing 전체 불필요, 기존 데이터 유지

작동원리

Step 1) 초기상태	버킷 개수 = M (예: 4개)		해시 함수: h(key) = key mod M
Step 2) 버킷 분할 발생	데이터가 많아져서 하나의 버킷이 꽉 차면, 그 버킷만 분할(split) 하고 다음 해시 함수를 사용하기 시작함.
	처음 해시 함수: h0(key) = key mod 4		다음 단계 해시 함수: h1(key) = key mod 8
	이때 분할 포인터(split pointer) 가 어느 버킷을 분할해야 하는지 가리킴. 한 번에 모든 버킷을 확장하지 않고, 매번 삽입될 때마다 포인터가 한 칸씩 이동함.

 

예시

초기: M = 4 (버킷 0~3)
데이터 삽입 중 → 버킷 0이 꽉 참 → 버킷 0 분할 → 새 버킷 4 추가 → 포인터(split pointer)가 1로 이동

다음에 버킷 1이 꽉 차면
→ 버킷 1 분할 → 새 버킷 5 추가

이런 식으로 포인터가 0→1→2→3 순으로 순환하면서
점진적으로 확장함.

장점	단점
데이터 크기 변화에 유연, 전체 재해싱 불필요 평균 O(1) 유지, 점진적 확장으로 부하 분산	구조 복잡, 구현 어려움 (여러 단계 해시 함수 관리 필요)

- DB 인덱싱, 대규모 데이터 저장 시스템

 

- Extendible Hashing (확장형 해싱)

• 디렉토리(directory) 와 버킷(bucket) 개념 사용
• 해시 함수의 일부 비트(prefix) 를 사용하여 버킷 선택

 

• 해시값의 앞 2비트를 사용 (00, 01, 10, 11)
• 특정 버킷이 꽉 차면 → 그 버킷만 분할(split)
• 필요 시 디렉토리 전체를 2배로 확장

→ 전체 재해싱 없이 일부만 확장 가능

 

주요 구성 요소

디렉토리 (Directory)	해시 값의 상위 몇 비트를 이용해 버킷을 가리키는 테이블
버킷 (Bucket)	실제 데이터가 저장되는 공간
전역 깊이 (Global Depth)	디렉토리가 사용하는 비트 수
지역 깊이 (Local Depth)	버킷이 구분되는 비트 수 (몇 비트까지 구분되어 있는지)

 

작동 원리

예를 들어 해시 함수 결과가 이진수로 나온다고 하자.
초기에는 1비트만 사용해 구분한다고 하면:

해시값(prefix)	버킷
0	B0
1	B1

• 전역 깊이(Global depth) = 1
• B0, B1 각각 여러 데이터 저장 가능

 *** Step 1: 버킷이 꽉 찼을 때

만약 B0이 꽉 찼다면,
→ 해당 버킷만 분할(split) 함.
→ local depth를 2로 늘리고
→ 2비트 구분이 필요하므로 디렉토리를 2배로 확장

해시 prefix	버킷
00	B0'
01	B0''
10	B1
11	B1

이렇게 되면 B0 관련 데이터만 재분배됨.
B1은 그대로 유지됨 → 전체 재해싱이 필요 X

예시

해시 함수: h(key) = key mod 8 → 3비트 사용

Key	Binary Hash	bits(앞 2비트)
5	101	10
6	110	11
2	010	01

1. 처음에는 1비트만 사용 (0, 1 구분)
2. 0번 버킷이 가득 차면 → 분할
3. 전역 깊이 +1, 디렉토리 2배로
4. 필요한 버킷만 다시 분배

장점	단점
전체 재해싱 불필요, 필요한 부분만 분할 동적 크기 조절 가능, 탐색 효율 O(1) 유지	디렉토리 메모리 사용 증가 구현 복잡

 

 

- Extendible vs Linear Hashing 비교

항목	Extendible Hashing	Linear Hashing
확장 방식	필요 시 디렉토리 2배 확장	버킷 하나씩 점진적 확장
관리 단위	디렉토리 기반 (prefix bits)	버킷 기반 (순차적 split)
공간 효율	디렉토리 메모리 사용 큼	메모리 효율적
구현 난이도	복잡하지만 구조적	구현 상대적으로 단순
사용 예	DB 인덱스, 파일 시스템	해시 인덱싱, 캐싱

---

 

정리하자면,

항목	Static Hashing	Dynamic Hashing
해시 함수	고정	확장 가능
테이블 크기	고정	자동 확장 / 축소
충돌 처리	필수적 (chaining 등)	분할로 완화
성능	일정하지만 크기 변화에 취약	안정적, 대용량에 적합
구현 난이도	쉬움	어려움
활용 예	간단한 캐시, 임시 해시맵	DB, 파일 시스템

---

해시 충돌(Collision)

: 서로 다른 두 키가 같은 해시 값으로 계산되는 현상.

 

예를 들어 해시 함수가 hash(x) = x mod 5 일 때,

Key	Hash
7	2
12	2

 

두 키가 같은 인덱스(2)에 저장됨 → 충돌 발생

 

 - 충돌 해결 방식

Chaining	같은 인덱스에 연결 리스트로 여러 데이터 저장	구조 단순
Open Addressing	충돌 시 빈 공간을 찾아 다른 위치에 저장	메모리 연속
Rehashing	새로운 해시 함수로 다시 해싱	확장성 높음

---

1. Chaining (체이닝)

같은 인덱스에 여러 개의 데이터를 연결 리스트(Linked List) 형태로 저장하는 방법.

Index 2 ─▶ [7] → [12] → [17]

 

장점	단점
충돌 발생해도 모든 데이터 저장 가능 구현 간단 데이터 삭제 용이	포인터(링크)로 인한 추가 메모리 사용 탐색 시 리스트 순회 필요 → 최악 O(n)

 

예시 코드)

struct Node {
    int key;
    struct Node* next;
};
struct Node* hashTable[M];

void insert(int key) {
    int idx = key % M;
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->key = key;
    newNode->next = hashTable[idx];
    hashTable[idx] = newNode;
}

---

2. Open Addressing (개방 주소법)

충돌이 나면 다른 빈 슬롯을 찾아서 저장하는 방식.
모든 데이터가 하나의 배열 안에 들어감.

Linear Probing	h(k, i) = (h(k) + i) mod M — 한 칸씩 순차 탐색
Quadratic Probing	h(k, i) = (h(k) + i²) mod M — 제곱 단위로 이동
Double Hashing	h(k, i) = (h1(k) + i * h2(k)) mod M — 두 번째 해시 함수 사용

 

장점	단점
추가 메모리 구조 필요 없음 (배열 내 저장) 캐시 효율 좋음	삭제 처리 복잡 (lazy deletion 필요) 클러스터링(연속 충돌) 가능

 

예시코드 (Linear Probing)

int hashTable[M];

void insert(int key) {
    int idx = key % M;
    while (hashTable[idx] != EMPTY)
        idx = (idx + 1) % M;   // 다음 인덱스로 이동
    hashTable[idx] = key;
}

---

3. Rehashing

해시 테이블이 너무 가득 차거나 충돌이 잦을 때, 더 큰 크기의 테이블로 전체를 다시 해싱하는 방법.

1. 테이블 크기를 2배로 확장
2. 기존 모든 데이터를 새 테이블에 재삽입

장점	단점
충돌 감소 검색 효율 유지	재해싱 시 시간 소모 큼 빈번한 확장은 비효율