[CS] 해시 테이블

해시 테이블(Hash Table)은 효율적인 데이터 저장 및 검색을 제공하는 데이터 구조입니다. 키-값(Key-Value) 쌍을 저장하며, 해시 함수를 통해 키를 특정 위치(인덱스)로 매핑합니다.

1. 해시 테이블의 정의

해시 테이블은 키(Key)와 값(Value) 쌍을 저장하며, 데이터를 빠르게 검색, 삽입, 삭제할 수 있는 데이터 구조입니다.
핵심은 해시 함수를 사용해 키를 고유한 인덱스로 변환하여 데이터를 배열처럼 관리한다는 점입니다.

2. 해시 함수의 역할

해시 함수는 입력된 키를 고정된 크기의 숫자(해시값)로 변환하는 함수입니다.

• 특징:
  • 입력값이 같으면 항상 같은 해시값을 반환해야 함(결정론적).
  • 해시값은 고르게 분포되어야 충돌을 줄일 수 있음.
• 예제:
  문자열을 숫자로 변환하는 간단한 해시 함수

def simple_hash(key, table_size):
    return sum(ord(char) for char in key) % table_size

3. 충돌(Collision)과 해결 방법

해시 함수가 다른 키에 대해 같은 해시값을 반환하면 충돌이 발생합니다.
이를 해결하기 위해 다음과 같은 방법을 사용합니다.

충돌 해결 방법	설명
체이닝(Chaining)	같은 인덱스에 여러 값을 저장하기 위해 링크드 리스트를 사용.
개방 주소법(Open Addressing)	충돌이 발생하면 다른 빈 공간을 찾아 데이터를 저장. 탐사 방법: 선형, 이차, 이중 해싱.

체이닝 예시:

• 인덱스 3번 위치에서 키 충돌이 발생하면, 링크드 리스트로 연결합니다.

개방 주소법 예시:

• 충돌 시 다음 빈 공간을 찾음.
  • 예: 키 % 테이블 크기 = 3 → 인덱스 3이 차 있으면 4, 5, ...를 순차적으로 탐사.
    
    

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

연산	평균 시간 복잡도	최악 시간 복잡도
검색(Search)	O(1)	O(n)
삽입(Insertion)	O(1)	O(n)
삭제(Deletion)	O(1)	O(n)

- 평균 시간 복잡도는 해시 함수가 데이터를 균일하게 분포시킬 경우입니다. - 최악 시간 복잡도는 모든 키가 같은 해시값을 가지는 경우로, 이 경우 선형 탐색이 필요합니다.

5. 해시 테이블의 장단점

장점	단점
빠른 데이터 접근(O(1)의 평균 성능)	충돌 발생 가능성
키-값 저장 방식으로 직관적인 데이터 관리 가능	해시 함수가 비효율적이면 성능 저하 발생
데이터베이스, 캐시 등 다양한 응용 분야에서 사용 가능	테이블 크기 조정(리사이징)이 비용이 큼

6. 활용 사례

• 캐싱(Cache): 최근 사용 데이터를 빠르게 저장 및 검색.
  • 웹 브라우저, 데이터베이스 인덱싱 등에서 사용.
• 키-값 저장소(Key-Value Store): Redis, Memcached와 같은 분산 데이터 저장.
• 데이터베이스 인덱싱: 빠른 검색을 위한 해시 기반 인덱스.
• 중복 검사: 해시 테이블을 사용해 데이터 중복 여부를 빠르게 확인.
  
  

7. Python으로 간단한 해시 테이블 구현

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash_function(self, key):
        return sum(ord(char) for char in key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        # 동일한 키 처리
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value
                return
        # 새 키 추가
        self.table[index].append([key, value])

    def search(self, key):
        index = self.hash_function(key)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        return None

    def delete(self, key):
        index = self.hash_function(key)
        for i, pair in enumerate(self.table[index]):
            if pair[0] == key:
                self.table[index].pop(i)
                return True
        return False

# 해시 테이블 사용 예시
hash_table = HashTable(10)
hash_table.insert("apple", 100)
hash_table.insert("banana", 200)
print(hash_table.search("apple"))  # 출력: 100
hash_table.delete("apple")
print(hash_table.search("apple"))  # 출력: None