해시 테이블(Hash Table)

개요

해시 테이블(Hash Table)은 키(Key)를 해시 함수(Hash Function)를 통해 고정된 인덱스로 변환하여 값을 저장하는 자료구조이다. 평균적으로 삽입, 삭제, 탐색 연산이 **O(1)**로 매우 빠르며, 파이썬의 dict, set, 자바의 HashMap, C++의 unordered_map 등 거의 모든 언어의 핵심 자료구조로 활용된다.

---

1. 개념 및 정의

항목	설명
키(Key)	값을 식별하기 위한 고유한 값
값(Value)	저장할 실제 데이터
해시 함수	키를 배열 인덱스로 변환하는 함수
버킷(Bucket)	해시 충돌이 발생할 수 있는 배열의 각 칸

해시 함수는 키를 숫자로 변환해 해시 테이블의 인덱스로 매핑한다.

---

2. 해시 함수와 충돌

• 해시 함수(Hash Function): hash(key) % table_size
• 충돌(Collision): 서로 다른 키가 같은 인덱스로 해시되는 현상
• 해결 방식:
  • 체이닝(Chaining): 같은 버킷에 여러 값을 연결 리스트로 저장
  • 개방 주소법(Open Addressing): 비어있는 다음 인덱스를 탐색해 저장 (선형 탐사, 이중 해싱 등)

---

3. 파이썬 딕셔너리 예시

hash_table = {}
hash_table['apple'] = 3
hash_table['banana'] = 5
print(hash_table['banana'])  # 출력: 5

# 키 존재 여부 확인
if 'apple' in hash_table:
    print('Exists!')

파이썬의 dict는 내부적으로 체이닝 기반 해시 테이블로 구현되어 있다.

---

4. 시간 및 공간 복잡도

연산	평균 시간	최악 시간
삽입	O(1)	O(n) (충돌 많을 때)
삭제	O(1)	O(n)
탐색	O(1)	O(n)

공간 복잡도는 O(n), 테이블 크기 조절 시 리해싱 비용이 발생할 수 있다.

---

5. 해시 테이블 vs 배열 vs 트리

자료구조	탐색 속도	정렬 필요	특징
해시 테이블	O(1)	X	키 기반 빠른 접근, 순서 없음
배열	O(1) (인덱스 기준)	O(n log n) (정렬 시)	순차 데이터 처리에 적합
이진 탐색 트리	O(log n)	자동 정렬	정렬된 출력 가능

---

6. 활용 사례

분야	예시
캐시 구현	LRU, LFU 캐시의 내부 키-값 매핑
중복 검사	문자열, 숫자 집합에서 중복 제거
카운팅	단어 빈도수, 상품 판매량, 투표 수
집합 연산	합집합, 교집합 구현 (set 구조)
키 기반 조회	사전, 검색 엔진 인덱스 등

---

7. 해시 테이블의 장단점

항목	장점	단점
속도	매우 빠른 O(1) 접근	최악 시 O(n) (충돌 시)
유연성	문자열, 객체 등 다양한 키 사용 가능	메모리 사용량 많음
구현	파이썬 dict 등 기본 자료구조로 제공	해시 함수 설계가 중요
순서	없음 (Python 3.7+는 순서 유지)	정렬된 출력 불가능

---

8. 결론

해시 테이블은 키를 기반으로 데이터를 빠르게 저장하고 탐색할 수 있는 효율적인 자료구조다. 알고리즘 문제풀이부터 대규모 데이터 처리, 캐시 구현 등 수많은 분야에서 활용되며, 다양한 해시 함수 설계와 충돌 처리 전략에 대한 이해가 필요하다. 해시 테이블의 원리와 성능을 정확히 이해하면 실무에서도 매우 강력한 도구가 된다.