Algorithm Guidecomplexity: 평균 O(1)

해시 테이블 (Hash Table)

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

01해시 테이블 (Hash Table)

알고리즘 작동 원리 탐색

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

put(10) · 10 % 5 = 0. 0번 버킷에 10을 넣습니다.

put(24) · 24 % 5 = 4. 4번 버킷에 24를 넣습니다.

put(14) · 14 % 5 = 4. 이미 24가 있는 4번에서 충돌 — 24 뒤에 체인으로 매답니다.

put(3) · 3 % 5 = 3. 비어 있던 3번 버킷에 3을 넣습니다.

get(14) · 14 % 5 = 4번으로 바로 이동. 체인을 훑어 24(아님) → 14(일치)를 찾습니다.

버킷 번호를 한 번에 계산하므로 평균 O(1). 충돌은 체이닝으로 풀고, 그 버킷 안에서만 짧게 탐색합니다.

0›

—

1›

—

2›

—

3›

—

4›

—

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

1 / 7

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