Hash Table이란? for python

해시 테이블 HashTabelHashTabelHash Tabel 이란?

해시 테이블은 키$Key$를 해시 함수로 계산해서
고유한 인덱스$Index$에 값을 저장하는 자료구조입니다.

 

즉, 리스트처럼 인덱스로 접근하되,

그 인덱스를 직접 지정하는 대신 해시 함수가 계산해줍니다.

 

파이썬에서 가장 대표적인 해시 테이블 구조는 dict, set 입니다.

---

해시 테이블 작동 원래 간단예시간단예시간단 예시

1. key를 hash 함수로 변환
2. 이 값을 배열의 인덱스로 사용
3. 그 자리에 value 저장!

my_dict = {'apple': 100, 'banana': 200}
print(my_dict['apple'])  # 100

내부적으로 'apple' → hash$'apple'$ → 인덱스 계산 → 해당 위치에 100 저장됨

---

왜 해시 테이블이 빠를까?

• 일반 배열은 인덱스로 접근: O$1$
• 해시 테이블도 → 인덱스를 바로 계산 하니깐 → O$1$ $상수 시간$

즉, my_dict['apple'] 은

리스트에서 arr[3] 처럼 빠르다.

 

시간 복잡도 요약

연산	시간복잡도
검색, 삽입, 삭제	O$1$ 평균
최악의 경우	O$n$ $해시 충돌 발생 시$

---

해시 충돌CollisionCollisionCollision 문제

해시 충돌이란 서로 다른 키가 같은 인덱스로 해시되는 경우입니다.

# 예를 들어 같은 인덱스에 저장되는 상황
hash("a") % 8 == hash("b") % 8

 

해결 방법:

• Chaining 방식: 같은 인덱스에 여러 값을 리스트로 연결
  
• Open Addressing: 충돌 시 빈 자리를 찾아 저장 $ex: Linar Probing$

파이썬의 dict는 Open Addressing 방식을 사용합니다.

 

해당 코드는 직접 Python으로 Chaining방식을 구현한 코드입니다.

class ChainedHashTable:
    def __init__(self, size=8):
        self.size = size
        self.table = [[] for _ in range(size)]  # 각 인덱스에 리스트

    def _hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        idx = self._hash(key)
        for pair in self.table[idx]:
            if pair[0] == key:
                pair[1] = value
                return
        self.table[idx].append([key, value])

    def get(self, key):
        idx = self._hash(key)
        for pair in self.table[idx]:
            if pair[0] == key:
                return pair[1]
        return None

    def display(self):
        for i, bucket in enumerate(self.table):
            print(f"Index {i}: {bucket}")

---

# dict
scores = {'Tom': 85, 'Jane': 92}
scores['Tom'] = 90
print(scores['Tom'])  # 90

# set
fruits = set()
fruits.add('apple')
fruits.add('banana')
print('apple' in fruits)  # True

 

set은 중복을 허용하지 않고, 존재 여부 확인이 빠름
→ 내부적으로 dict의 key만 사용하는 구조

---

언제 해시 테이블을 사용해야 할까?

• 빠르게 검색해야 할 때
• 중복 제거가 필요할 때
• 존재 여부를 자주 확인해야 할 때
• 키-값 쌍을 저장해야 할 때

---

요약 정리

항목	내용
구조	키 → 해시 함수 → 인덱스 → 값 저장
시간복잡도	평균 O$1$, 최악 O$n$ $충돌 시$
핵심 장점	빠른 검색 / 삽입 / 삭제
단점	해시 충돌, 메모리 사용 많을 수 있음