[알고리즘 & 문제 해결 패턴] 해시 테이블(Hash Table) 개념과 활용 사례

[알고리즘] 해시 테이블(Hash Table) 개념과 활용 사례

1. 해시 테이블(Hash Table)이란?

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

키를 특정한 함수(해시 함수)를 사용하여 특정한 인덱스로 변환하고,

이를 기반으로 값을 저장하거나 검색하는 방식입니다.

2. 해시 테이블의 구조

해시 테이블의 핵심 요소:

• ✔ 해시 함수(Hash Function): 키를 해시값(인덱스)으로 변환하는 함수
• ✔ 해시 충돌(Collision): 서로 다른 키가 동일한 해시값을 가질 때 발생
• ✔ 충돌 해결 방법: 체이닝(Chaining), 개방 주소법(Open Addressing) 등

---

3. 해시 테이블 기본 구현 (Java 예제)

🔹 **1. 기본적인 HashMap 사용**

import java.util.HashMap;

public class HashTableExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        
        // 데이터 삽입
        map.put("apple", 100);
        map.put("banana", 200);
        map.put("cherry", 300);
        
        // 데이터 조회
        System.out.println("apple 가격: " + map.get("apple")); // 100 출력
        
        // 데이터 삭제
        map.remove("banana");
        
        // 키 존재 여부 확인
        System.out.println("cherry 존재 여부: " + map.containsKey("cherry"));
    }
}

✅ 특징:

- `put()` 메서드로 키-값 추가

- `get()` 메서드로 키를 통해 값 조회

- `remove()` 메서드로 데이터 삭제 가능

- `containsKey()`로 특정 키가 존재하는지 확인 가능 

4. 해시 충돌(Collision) 해결 방법

해시 충돌이란,

서로 다른 두 개의 키가 **같은 해시 값**을 가지는 경우입니다.

이를 해결하는 대표적인 방법 2가지를 살펴보겠습니다.

✔ 1) 체이닝(Chaining) 방식

체이닝은 **해시 충돌이 발생하면 같은 인덱스의 연결 리스트(Linked List)에 저장하는 방식**입니다.

// Java의 HashMap은 기본적으로 체이닝 방식으로 충돌을 해결함
HashMap<String, Integer> map = new HashMap<>();

 

✅ 장점:

- 간단한 구현

- 충돌이 발생해도 유연한 처리 가능

 

✅ 단점: - 여러 개의 데이터가 충돌할 경우 검색 속도가 느려짐 

✔ 2) 개방 주소법(Open Addressing) 방식

개방 주소법은 **해시 충돌이 발생하면, 빈 공간을 찾아 데이터를 저장하는 방식**입니다.

대표적인 기법으로

선형 탐색(Linear Probing),

이차 탐색(Quadratic Probing),

이중 해싱(Double Hashing) 이 있습니다.

import java.util.Hashtable;

public class OpenAddressingExample {
    public static void main(String[] args) {
        Hashtable<String, Integer> table = new Hashtable<>();
        
        table.put("apple", 100);
        table.put("banana", 200);
        table.put("cherry", 300);
        
        System.out.println("apple 가격: " + table.get("apple"));
    }
}

 

✅ 장점:

- 충돌이 적으면 검색 속도가 빠름

 

✅ 단점:

- 충돌이 많을 경우 저장 공간 낭비 발생 가능 

5. 해시 테이블의 시간 복잡도

연산	평균 시간 복잡도	최악의 시간 복잡도
삽입 (Insert)	O(1)	O(N) (충돌이 많을 경우)
검색 (Search)	O(1)	O(N) (충돌이 많을 경우)
삭제 (Delete)	O(1)	O(N) (충돌이 많을 경우)

✅ 결론:

- 해시 테이블은 **평균적으로 O(1)의 시간 복잡도를 가짐**

- 하지만 충돌이 많을 경우 **최악의 경우 O(N)**까지 증가할 수 있음 

6. 해시 테이블 활용 사례

• ✔ **캐싱 (Caching)**: 빠른 데이터 조회를 위해 사용
• ✔ **데이터베이스 인덱싱**: 해시 인덱스를 통해 빠른 검색
• ✔ **중복 검사 (Duplicate Detection)**: 해시 테이블을 이용하여 빠른 중복 확인
• ✔ **암호화 (Hashing Algorithms)**: 비밀번호 저장 등에 활용

---

📌 정리

• ✔ 해시 테이블은 **키-값(Key-Value) 형태로 데이터를 저장하는 자료구조**
• ✔ 해시 함수(Hash Function)를 이용해 빠른 검색이 가능
• ✔ 충돌 해결 방식으로 **체이닝(Chaining), 개방 주소법(Open Addressing)** 등이 존재
• ✔ 평균 시간 복잡도 O(1), 최악의 경우 O(N)까지 증가 가능
• ✔ 데이터베이스 인덱싱, 캐싱, 중복 검사 등에 널리 사용됨

---

🔗 다른 알고리즘 & 문제 해결 관련 글도 함께 확인해보세요!

트라이(Trie) 자료구조 개념과 활용 사례