[100일의 IT 초보 탈출] #69 해시 테이블 _ 빠른 검색의 마법

오늘은 무엇을 배우게 될까요?

 

우리는 프로그램에서 특정 데이터를 빠르게 찾고 싶을 때가 많습니다.

예를 들어

 

• 사용자 ID가 등록되어 있는지?
• 어떤 단어가 이미 등장했는지?
• 특정 키에 대한 값을 얼마나 빠르게 찾을 수 있을까?

 

이럴 때 사용하는 대표적인 자료구조가 바로 해시 테이블(Hash Table)입니다.

 

---

 

해시 테이블이란?

 

Key → Value 쌍으로 데이터를 저장하는 구조입니다.

검색, 삽입, 삭제를 매우 빠르게 할 수 있습니다.

 

• Key는 고유한 식별자
• Value는 저장하고 싶은 데이터

 

---

 

 

해시 함수란?

 

해시 테이블의 핵심은 해시 함수(Hash Function)입니다.

Key를 받아서 내부 배열의 인덱스로 바꿔주는 함수입니다.

Index = Hash(Key) % Table_Size

좋은 해시 함수일수록 Key가 잘 분산되고 충돌이 적습니다.

 

---

Python 코드로 해시 테이블 흉내내기

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def _hash(self, key):
        return sum(ord(c) for c in key) % self.size
    
    def insert(self, key, value):
        index = self._hash(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value))
    
    def get(self, key):
        index = self._hash(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

 

---

사용 예시

ht = HashTable(10)
ht.insert("apple", 5)
ht.insert("banana", 10)
ht.insert("grape", 7)

print(ht.get("banana"))  # 출력: 10
print(ht.get("melon"))   # 출력: None

 

---

충돌(Collision)이란?

 

서로 다른 키가 같은 해시값을 가질 경우, 한 인덱스에 여러 개의 데이터가 들어갑니다.

 

이를 처리하는 방식

 

체이닝(Chaining)	같은 인덱스에 리스트로 저장
개방 주소법(Open Addressing)	빈 인덱스를 찾아 저장 (선형 탐사 등)

 

---

 

 

시간 복잡도 비교

연산평균 시간최악 시간 (충돌 시)

삽입	O(1)	O(N) (최악)
탐색	O(1)	O(N) (최악)
삭제	O(1)	O(N) (최악)

→ 평균적으로는 매우 빠름!

 

---

Python 내장 해시 구조

 

• dict: 해시 테이블 기반
• set: 내부적으로 key만 가진 해시 테이블

d = {'name': 'Alice', 'age': 25}
print(d['name'])  # O(1) 접근

s = set()
s.add("apple")
print("apple" in s)  # O(1) 검색

 

---

해시 테이블의 활용 예시

분야설명

데이터베이스	인덱싱 구조로 사용 (Hash Index)
캐시	최근 결과를 빠르게 저장/검색
중복 제거	Set처럼 존재 여부만 확인
언어 처리	단어 빈도 수 세기
그래프 탐색	정점-간선 관계 저장

 

---

해시 테이블 vs 배열/리스트

 

배열	인덱스 접근 빠름	키를 숫자로만 사용
리스트	삽입/삭제 유연	검색 느림 (O(N))
해시 테이블	키 기반 빠른 검색 (O(1))	충돌 처리 필요

 

---

한 줄 요약

 

👉 해시 테이블은 키-값 쌍 데이터를 초고속으로 검색/저장할 수 있는 자료구조로,

모든 프로그래밍 언어에서 가장 많이 쓰이는 핵심 도구 중 하나입니다.