[자료구조] 해시 테이블

📌 해시 테이블(Hash Table) 개념

해시 테이블(Hash Table) 은 키(Key)와 값(Value)을 매핑하여 저장하는 자료구조.

즉, 특정 데이터를 빠르게 찾고, 삽입하고, 삭제하는 데 최적화된 구조.

---

✅ 1. 해시 테이블의 개념

1) 키(Key)와 값(Value)

• Key(키): 데이터를 찾기 위한 고유한 식별자 (예: 이름, ID, 해시값)
• Value(값): 키에 대응하는 저장된 데이터

 

📌 예시: 학생 성적 저장

cpp
복사편집
hash_table["Alice"] = 95;
hash_table["Bob"] = 88;
hash_table["Charlie"] = 72;

 

Key Value

Alice	95
Bob	88
Charlie	72

---

2) 해시 함수(Hash Function)

• 해시 함수는 Key를 특정한 인덱스(Index)로 변환하는 함수.
• 변환된 값은 해시 값(Hash Value) 이고, 이 값은 해시 테이블의 인덱스로 사용됨.

 

📌 예시: 해시 함수 적용

plaintext
복사편집
hash("Alice")  → 2
hash("Bob")    → 4
hash("Charlie") → 1

plaintext
복사편집
Index:  0    1     2      3    4
Data:  []  [72]  [95]   []  [88]

---

 

✅ 2. 해시 테이블의 시간복잡도

연산 평균 시간복잡도 최악 시간복잡도 (충돌 발생 시)

탐색(Search)	O(1)	O(N)
삽입(Insert)	O(1)	O(N)
삭제(Delete)	O(1)	O(N)

📌 해시 테이블의 핵심 강점

✅ 일반적으로 O(1)의 빠른 탐색 속도를 제공!

✅ 하지만 충돌이 많이 발생하면 O(N)까지 성능 저하 가능

---

 

✅ 3. 해시 충돌(Hash Collision)

두 개 이상의 키가 같은 해시 값(인덱스)을 가지는 경우 발생.

충돌을 해결하는 방법으로는 개방 주소법(Open Addressing)과 체이닝(Chaining)이 있음.

 

📌 충돌 예시

plaintext
복사편집
hash("Alice")  → 2
hash("Eve")    → 2  (충돌 발생!)

 

📌 충돌 해결 방법

방법 설명

개방 주소법(Open Addressing)	충돌 발생 시, 테이블 내 다른 빈 공간을 찾아 저장
체이닝(Chaining)	충돌이 발생하면 연결 리스트로 추가 데이터 저장

---

 

✅ 4. 해시 테이블의 활용 사례

분야 활용 예시

데이터베이스(DBMS)	인덱스(Hash Index) 관리
운영체제(OS)	페이지 테이블, 캐시 관리
네트워크	DNS 조회, 패킷 필터링
보안(Security)	비밀번호 저장(SHA, MD5 해시)
게임 개발	빠른 오브젝트 검색 (NPC 위치, 아이템 저장)

---

 

✅ 5. 해시 테이블을 언제 사용할까?

✅ 데이터 검색, 삽입, 삭제가 많고 빠른 처리가 필요할 때!

✅ 빠른 키-값 매핑이 필요한 경우 (예: 캐시, 딕셔너리, 룩업 테이블)

✅ 메모리가 충분하고, 해시 충돌을 최소화할 수 있을 때

📌 하지만 해시 충돌이 많으면 O(N)까지 성능이 저하될 수 있음.

---

 

✅ 6. 결론

📌 해시 테이블은 O(1) 탐색 속도를 제공하는 강력한 자료구조

📌 충돌 문제를 해결해야 안정적인 성능을 유지할 수 있음.

📌 캐싱, 데이터베이스, 네트워크, 보안 등 다양한 분야에서 활용

 

 

📌 해시 함수(Hash Function)의 종류

해시 함수는 입력값(키)을 고정된 크기의 해시 값으로 변환하는 함수.

해시 테이블에서 효율적인 키 매핑과 충돌 최소화를 위해 다양한 해시 함수가 사용됨.

해시 함수는 사용 목적에 따라 크게 3가지로 나눌 수 있음

1. 일반 해시 함수 (Hash Table 용)
2. 암호화 해시 함수 (Cryptographic Hash)
3. 특수 목적 해시 함수 (Checksum, Consistent Hashing 등)

---

 

✅ 1. 일반 해시 함수 (Hash Table 용)

해시 테이블에서 충돌을 줄이고, 키를 균등하게 분포시키는 것이 목표.

주로 데이터 구조에서 키를 빠르게 매핑하는 데 사용됨.

1) 나눗셈 방법 (Modulo Division)

• hash(key) = key % table_size
• 특징: 간단하고 빠름, 하지만 나쁜 소수(Prime) 선택 시 클러스터링 발생 가능.

cpp
복사편집
int hashFunction(int key, int tableSize) {
    return key % tableSize;
}

 

📌 예시

plaintext
복사편집
key = 35, table_size = 7
hash(35) = 35 % 7 = 0

---

2) 곱셈 방법 (Multiplication Hashing)

• hash(key) = floor(table_size * (key * A % 1))
• A는 0과 1 사이의 특정 상수 (예: 0.6180339887 ≈ 황금비)
• 특징: 나눗셈 방식보다 균등하게 분포됨.

cpp
복사편집
int hashFunction(int key, int tableSize) {
    const double A = 0.6180339887; // 황금비
    return floor(tableSize * (key * A - floor(key * A)));
}

 

📌 예시

plaintext
복사편집
key = 35, table_size = 7
hash(35) = floor(7 * (35 * 0.6180339887 % 1))

---

3) 폴리노미얼 해시 (Polynomial Hash)

• 주로 문자열 해싱에서 사용됨.
• hash(s) = (s[0] * p^0 + s[1] * p^1 + ... + s[n-1] * p^(n-1)) % M
• p는 보통 31 또는 37, M은 소수(예: 1e9 + 9).
• 특징: 문자열 해싱에 강력함.

cpp
복사편집
unsigned long long polynomialHash(const string &s, int p = 31, int m = 1e9 + 9) {
    unsigned long long hashValue = 0, power = 1;
    for (char c : s) {
        hashValue = (hashValue + (c - 'a' + 1) * power) % m;
        power = (power * p) % m;
    }
    return hashValue;
}

 

📌 예시

plaintext
복사편집
"hello" → hash("hello") = 21045389

---

 

✅ 2. 암호화 해시 함수 (Cryptographic Hash)

보안이 중요한 데이터(비밀번호, 디지털 서명 등)에 사용됨.

암호화 해시 함수는 역산이 불가능해야 하고, 충돌이 없어야 함.

1) MD5 (Message Digest Algorithm 5)

• 128비트(16바이트) 해시 출력.
• 빠르지만 보안 취약(충돌 발생 가능).

 

📌 예시

plaintext
복사편집
MD5("hello") = 5d41402abc4b2a76b9719d911017c592

---

2) SHA (Secure Hash Algorithm)

• SHA-1 (160비트, 보안 취약)
• SHA-256 (256비트, 강력한 보안)
• SHA-512 (512비트, 강력한 보안)

 

📌 예시

plaintext
복사편집
SHA-256("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

---

3) BLAKE2 / Argon2

• 최신 암호화 해시 함수, 빠르고 안전함.
• Argon2는 비밀번호 해싱(PBKDF2 대체) 에 사용됨.

---

 

✅ 3. 특수 목적 해시 함수

1) CRC (Cyclic Redundancy Check)

• 데이터 오류 검출 용도로 사용됨.
• 네트워크 패킷, 파일 저장 시 무결성 확인.

plaintext
복사편집
CRC32("hello") = 3610A686

---

2) MurmurHash

• 빠른 해싱을 위해 설계된 해시 함수, 충돌 방지.
• 데이터베이스 및 게임 엔진에서 많이 사용됨.

cpp
복사편집
uint32_t MurmurHash2(const void *key, int len, uint32_t seed = 0x9747b28c);

---

3) Consistent Hashing

• 분산 시스템(예: 로드 밸런서, 캐시 서버)에서 노드 추가/제거 시 영향 최소화.
• h(key) = (hash(key) % num_servers)

 

📌 예시

plaintext
복사편집
서버 3개: { A, B, C }
hash(유저1) → A
hash(유저2) → B
서버 추가 시 최소한의 키만 이동!

---

 

✅ 4. 해시 함수 비교

해시 함수 목적 강점 약점

나눗셈 해싱	해시 테이블	간단하고 빠름	충돌 발생 가능
곱셈 해싱	해시 테이블	충돌 방지	계산량 증가
폴리노미얼 해시	문자열	균등한 분포	소수 선택 중요
MD5	보안	빠름	보안 취약
SHA-256	보안	강력한 보안	느림
CRC	오류 검출	빠름	보안 X
MurmurHash	일반 해시	빠르고 충돌 적음	보안 취약
Consistent Hashing	분산 시스템	서버 확장 가능	구현 복잡

---

 

✅ 5. 결론

📌 해시 함수는 용도에 따라 선택해야 한다.

✅ 해시 테이블 → 나눗셈 해싱, 곱셈 해싱, MurmurHash

✅ 보안 → SHA-256, Argon2

✅ 데이터 무결성 → CRC

✅ 분산 시스템 → Consistent Hashing

 

 

📌 해시 테이블의 종류

---

✅ 1. 해시 테이블의 주요 종류

해시 테이블은 충돌 해결 방식에 따라 크게 두 가지로 나뉨.

1) 개방 주소법(Open Addressing) → 하나의 배열로 해결

• 해시 충돌이 발생하면 빈 공간을 찾아 데이터를 저장.
• 추가적인 연결 리스트가 필요 없음 → 메모리 사용량이 적음.
• 대표적인 방식: 선형 탐색(Linear Probing), 이차 탐색(Quadratic Probing), 이중 해싱(Double Hashing).

2) 체이닝(Chaining) → 연결 리스트 활용

• 해시 충돌이 발생하면 같은 해시값을 가진 데이터들을 연결 리스트(Linked List)로 관리.
• 추가적인 메모리 공간(리스트)이 필요하지만 충돌 해결이 효과적.
• 대표적인 방식: 단순 체이닝(Separate Chaining), 확장 해싱(Extendible Hashing).

---

 

✅ 2. 개방 주소법(Open Addressing) 방식

해시 테이블 내부의 배열 안에서 충돌을 해결하는 방식.

1) 선형 탐색 (Linear Probing)

• 충돌이 발생하면 다음 빈 슬롯을 찾을 때 한 칸씩 이동.
• h(key) = (hash(key) + i) % table_size
• 장점: 구현이 간단하고 메모리 효율적.
• 단점: 클러스터링(Clustering, 데이터가 몰림) 문제 발생 → 성능 저하.

cpp
복사편집
index = (hash(key) + 1) % table_size;  // 한 칸씩 이동

 

 

📌 예시:

plaintext
복사편집
해시 함수 결과:   [10] → 2
해시 충돌 발생 → [10] 다음 빈 슬롯(3)에 저장

plaintext
복사편집
Index:  0   1   2   3   4   5   6
Data:  []  []  [5]  [10]  []  []  []

---

2) 이차 탐색 (Quadratic Probing)

• 선형 탐색의 문제를 개선하기 위해, 충돌이 발생하면 i² (1, 4, 9, 16...)만큼 이동.
• h(key) = (hash(key) + i²) % table_size
• 장점: 클러스터링 문제 완화.
• 단점: 특정 테이블 크기에서 빈 슬롯을 찾지 못하는 문제가 있음.

cpp
복사편집
index = (hash(key) + i * i) % table_size;  // i^2 만큼 이동

 

📌 예시:

plaintext
복사편집
해시 충돌 발생 → 1² = 1칸 이동 → 4² = 16칸 이동

---

3) 이중 해싱 (Double Hashing)

• 두 개의 서로 다른 해시 함수를 사용하여 충돌이 발생하면 두 번째 해시 함수 값만큼 이동.
• h(key) = (hash1(key) + i * hash2(key)) % table_size
• 장점: 클러스터링을 줄이고, 성능이 우수함.
• 단점: 해시 함수를 잘 설계해야 함.

cpp
복사편집
index = (hash1(key) + i * hash2(key)) % table_size;

 

📌 예시:

plaintext
복사편집
hash1(key) = key % table_size
hash2(key) = 7 - (key % 7)  // 두 번째 해시 값 계산

---

 

✅ 3. 체이닝(Chaining) 방식

체이닝 방식은 배열의 각 인덱스가 연결 리스트를 가지도록 구현하여 충돌을 해결해.

1) 단순 체이닝(Separate Chaining)

• 같은 해시값을 가진 요소들은 연결 리스트(Linked List)로 저장.
• 충돌이 발생하면 리스트에 추가하는 방식.
• 장점: 충돌이 많아도 동작 가능, 확장성이 좋음.
• 단점: 연결 리스트 사용으로 추가적인 메모리 사용.

cpp
복사편집
hash_table[hash(key)].push_back(key);

 

📌 예시:

plaintext
복사편집
해시값 2: [10, 22, 32] (연결 리스트로 저장)

plaintext
복사편집
Index:   0      1      2         3     4
Data:   []     []   [10 → 22 → 32]   []   []

---

2) 확장 해싱 (Extendible Hashing)

• 데이터를 버킷(Bucket) 단위로 관리하고, 충돌이 발생하면 버킷을 확장.
• 데이터베이스(DBMS)에서 많이 사용됨.
• 장점: 해시 테이블 크기를 자동 조절하여 공간 낭비 최소화.
• 단점: 구현이 복잡함.

plaintext
복사편집
해시 충돌 발생 → 새로운 버킷을 생성하여 데이터 이동

---

 

✅ 4. 해시 테이블 종류별 비교

방식 충돌 해결 방법 탐색 속도 (평균) 메모리 사용 추가 설명

선형 탐색 (Linear Probing)	다음 빈 슬롯으로 이동	O(1)	적음	클러스터링 문제 발생
이차 탐색 (Quadratic Probing)	i² 만큼 이동	O(1)	적음	일부 테이블 크기에서 충돌 문제
이중 해싱 (Double Hashing)	두 개의 해시 함수 사용	O(1)	적음	충돌 확률 낮음
체이닝 (Chaining)	연결 리스트 사용	O(1)	많음	확장성이 좋음
확장 해싱 (Extendible Hashing)	버킷 확장	O(1)	보통	DB에서 많이 사용

---

 

✅ 5. 해시 테이블의 응용 사례

응용 분야 해시 테이블 사용 예시

데이터베이스(DBMS)	인덱스(Hash Index), 캐싱
컴파일러	심볼 테이블(Symbol Table) 저장
운영체제(OS)	페이지 테이블, 캐시 관리
네트워크	DNS 조회, 패킷 필터링
게임 개발	빠른 오브젝트 검색(스폰 위치, NPC 데이터)
암호화(Security)	비밀번호 저장(SHA, MD5 해시)

---

 

✅ 6. 결론

📌 언제 어떤 해시 테이블을 사용할까?

• 메모리가 적을 때 → 개방 주소법(Open Addressing) 방식이 적합.
• 충돌이 많은 경우 → 체이닝(Chaining) 방식이 더 안정적.
• 검색/삭제 속도가 중요한 경우 → 이중 해싱(Double Hashing).
• 대량의 데이터를 저장하고 확장성을 고려할 때 → 확장 해싱(Extendible Hashing).