[Python] 알고리즘 개념10 - 해시 테이블과 해싱

 

 

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

**해시 테이블(Hash Table)**은 키(Key)와 값(Value)을 저장하는 자료구조로, 데이터를 빠르게 검색할 수 있어요.

 

💡 쉽게 이해하기

• 📦 **사전(Dictionary)**과 비슷하게 동작해요!
• 🔢 데이터를 저장할 때, **해시 함수(Hash Function)**를 사용해 특정 위치(해시 버킷)에 저장해요.
• 🚀 해시 함수를 통해 O(1) 시간 복잡도로 데이터 검색이 가능해요!

 

📌 해시 테이블의 기본 개념

# Python의 딕셔너리를 활용한 해시 테이블 구현
hash_table = {}
hash_table['apple'] = 5
hash_table['banana'] = 3
print(hash_table['apple'])  # 출력: 5

➡ 딕셔너리는 내부적으로 해시 테이블을 사용하여 빠르게 데이터를 검색합니다.

---

 

 

🚀 2. 해시 함수(Hash Function)란?

해시 함수는 임의의 데이터를 일정한 크기의 값(해시 값)으로 변환하는 함수예요.

 

📌 좋은 해시 함수의 특징

• 🎯 항상 같은 입력에 대해 같은 해시 값을 반환해야 해요.
• 🔄 충돌(Collision)이 최소화되어야 해요.
• ⚡ 빠르게 계산할 수 있어야 해요.

 

💡 Python에서 내장된 hash() 함수 활용하기

print(hash("apple"))  # 실행할 때마다 동일한 해시 값 출력
print(hash("banana"))

➡ 해시 함수는 특정 값을 일정한 길이로 변환하는 역할을 합니다.

---

 

 

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

해시 테이블은 같은 해시 값을 갖는 두 개 이상의 키가 존재할 수도 있어요. 이를 **해시 충돌(Hash Collision)**이라고 해요.

 

📌 해시 충돌 해결 방법

 

✅ 1) 체이닝(Chaining)

• 🚀 같은 해시 값의 데이터를 연결 리스트(Linked List)로 저장하는 방식
• 📌 Python의 defaultdict(list)을 사용해 구현할 수 있어요.

from collections import defaultdict

hash_table = defaultdict(list)
hash_table[hash("apple")].append("apple")
hash_table[hash("banana")].append("banana")
print(hash_table)

 

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

• 📦 충돌이 발생하면 빈 공간을 찾아 데이터를 저장하는 방식
• 🔄 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing) 등의 기법을 활용

➡ Python의 dict는 체이닝 방식을 사용합니다!

---

 

 

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

 

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

삽입(Insert)	O(1)	O(n)
삭제(Delete)	O(1)	O(n)
검색(Lookup)	O(1)	O(n)

➡ 일반적으로 해시 테이블은 O(1)의 속도로 매우 빠르지만, 해시 충돌이 많아지면 O(n)까지 성능이 저하될 수 있어요.

---

 

 

🚀 5. 해시 테이블 활용 예시

 

📌 해시 테이블은 어디에서 사용될까요?

1. 사전(Dictionary) 구현 → 키-값 쌍을 저장하는 가장 기본적인 활용법
2. 캐싱(Cache) → 웹 페이지나 데이터베이스 결과를 빠르게 저장하여 다시 사용할 때
3. 중복 검사(Duplicate Check) → 한 번 등장한 데이터를 빠르게 확인하기 위해 사용
4. 빈도수 계산(Frequency Count) → 문자열 내 단어 빈도 수 세기 등
5. 데이터베이스 인덱싱(Indexing) → 데이터베이스에서 빠른 검색을 위해 사용

➡ 해시 테이블은 실생활에서 매우 자주 활용되는 자료구조입니다! 😊

---

 

 

✅ 마무리 정리

• 해시 테이블은 키-값을 저장하는 빠른 자료구조로, 해시 함수를 활용해 데이터를 저장합니다.
• 해시 충돌을 해결하는 방식으로 체이닝과 개방 주소법이 존재합니다.
• 해시 테이블은 O(1) 시간복잡도를 가지지만, 충돌이 많아지면 O(n)까지 느려질 수 있습니다.
• Python의 딕셔너리는 해시 테이블을 기반으로 구현됩니다.