알고리즘 기초 - 해시 테이블

---

헤시테이블이란?

---

 

• 키(key)와 값(value)을 짝지어 저장하는 자료구조
• 해시 함수(Hash Function)를 사용해 키를 특정 인덱스로 변환하여 값을 저장하고 검색
• 대표적으로 딕셔너리(Dictionary, Python), 맵(Map, Java), 객체(Object, JavaScript) 같은 자료형이 해시테이블 기반으로 동작

동작 원리

 

1. 해시 함수(Hash Function) 적용
   키 → 해시 함수 → 해시값(배열 인덱스)
2. 저장
   배열의 해당 인덱스 위치에 값 저장
3. 검색
   동일한 키로 해시 함수 → 같은 인덱스 → 값 꺼냄

 

예시

# 파이썬 딕셔너리 = 해시테이블
hash_table = {}

hash_table["apple"] = 100
hash_table["banana"] = 200

print(hash_table["apple"])  # 100
del hash_table["banana"]
print(hash_table)  # {'apple': 100}

---

장점과 단점

---

 

장점	단점
- 평균적으로 검색, 삽입, 삭제 연산이 O(1)로 매우 빠름	- 충돌(Collision) 발생 가능 (서로 다른 키가 같은 해시값을 가질 때)
- 키를 직접 저장하므로 탐색이 효율적임	- 충돌 해결(체이닝/버킷 등)로 인해 공간 효율 낮음
- 문자열, 숫자 등 다양한 자료형의 키 사용 가능	- 해시 함수가 좋지 않으면 성능 저하 발생

 

 

 

충돌 해결방법

1. 체이닝(Chaining)
   같은 인덱스에 연결 리스트로 여러 값 저장
2. 개방 주소법(Open Addressing)
   충돌 시 다른 빈 공간 찾아 저장 (선형 탐사, 이차 탐사 등)

 

---

마무리

---

 

해시테이블은 빠른 탐색과 삽입을 보장하는 강력한 자료구조지만,
충돌 관리와 해시 함수 설계가 중요하다는 점을 꼭 기억해야 합니다.