Algorithm Guidecomplexity: 평균 O(1)

해시 테이블 (Hash Table)

키를 해시 함수로 버킷 인덱스에 매핑해 평균 O(1)에 저장·조회합니다. 서로 다른 키가 같은 버킷으로 충돌하면 체이닝(연결 리스트)이나 개방 주소법으로 해결합니다.

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

Hash Table · 체이닝

0›

—

1›

—

2›

—

3›

—

4›

—

해시 테이블. 키를 해시 함수(여기선 key % 5)로 계산해 버킷 번호를 정합니다.

Logic Node1 / 7

Live Python

1def _index(key):

2 return key % capacity # 해시 → 버킷 번호

4def put(key):

5 i = _index(key)

6 buckets[i].append(key) # 충돌 시 체인에 추가

8def get(key):

9 i = _index(key)

10 for k in buckets[i]: # 그 버킷만 선형 탐색

11 if k == key:

12 return k

13 return None

02 쉽게 이해하기

For Everyone

🔑비유

사물함 — 이름을 번호로 바꿔주는 규칙(해시)이 있어 물건 위치를 한 번에 찾습니다.

💡쉽게 말하면

키를 계산해 저장 위치를 바로 정합니다.

뒤지지 않고 거의 즉시 찾아요(평균 O(1)).

같은 칸이 겹치면(충돌) 줄줄이 매달아 해결합니다.

📍어디에 쓰나

–사전/딕셔너리
–중복 검사
–데이터베이스 인덱스
–캐시

03 파이썬 구현 코드

해시 테이블 (Hash Table)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

class HashTable:
    def __init__(self, capacity=8):
        self.capacity = capacity
        self.buckets = [[] for _ in range(capacity)]

    def _index(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        return None