class HashMap:
"""
간단한 체이닝(Chaining) 기반 해시맵 구현.
───────────────────────────────────────────────
• 충돌 처리 : 동일 인덱스에 리스트(버킷)를 두어 체이닝
• 리사이즈 : (size+1)/capacity ≥ load_factor 가 되면 용량 2배
• API : put / get / remove
"""
# ───────────────────────────── 초기화 ───────────────────────────── #
def __init__(self, capacity: int = 8, load_factor: float = 0.75):
"""
▸ capacity : 버킷 배열 초기 길이 (항상 2의 거듭제곱이 좋다)
▸ load_factor : (저장된 엔트리 수 / 버킷 수)가 이 값 이상이면 리사이즈
"""
self.cap = capacity # 현재 버킷 배열 길이
self.lf = load_factor # 허용 로드팩터
self.size = 0 # 저장된 (key,value) 쌍 수
self.buckets = [[] for _ in range(self.cap)] # 버킷 배열(리스트의 리스트)
# ──────────────────────────── 내부 유틸 ──────────────────────────── #
def _hash(self, key):
"""
▸ 파이썬 내장 hash() 결과를 현재 capacity 로 모듈러.
한 프로세스 안에서는 hash(key)가 고정이므로
같은 키 → 같은 인덱스.
"""
return hash(key) % self.cap
def _resize(self):
"""
▸ capacity 2배 확장 후, 기존 모든 (key,value)를
새 배열로 '다시 해시' 해서 옮긴다.
"""
old_buckets = self.buckets # ① 기존 배열 백업
self.cap *= 2 # ② 용량 2배
self.buckets = [[] for _ in range(self.cap)]
self.size = 0 # ③ 재삽입할 것이므로 0으로 초기화
for bucket in old_buckets: # ④ 백업 배열 순회
for k, v in bucket:
self.put(k, v) # 새 배열에 재삽입 (size 다시 증가)
# ───────────────────────────── Public API ───────────────────────────── #
def put(self, key, value):
"""
▸ (key,value) 저장.
- 이미 존재하는 키면 값만 덮어씀(O(1))
- 없으면 새 튜플을 버킷 리스트 끝에 추가(O(1) 평균)
"""
# 1) 리사이즈 필요 여부 판단
if (self.size + 1) / self.cap >= self.lf: # ⚠️ 괄호! (size+1) 먼저
self._resize()
# 2) 적절한 버킷 선택
idx = self._hash(key)
bucket = self.buckets[idx]
# 3) 동일 키 존재 여부 검사 → 있으면 덮어쓰고 종료
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value) # 같은 자리에서 덮어쓰기
return # append·size 증가 X
# 4) 동일 키가 없으면 새 튜플 추가
bucket.append((key, value))
self.size += 1
def get(self, key, default=None):
"""
▸ 키가 있으면 값 반환, 없으면 default (기본 None) 반환.
"""
idx = self._hash(key)
for k, v in self.buckets[idx]:
if k == key:
return v
return default
def remove(self, key):
"""
▸ 키가 존재하면 (key,value) 쌍을 제거.
존재하지 않으면 KeyError 를 일으켜 호출자에게 알림.
"""
idx = self._hash(key)
bucket = self.buckets[idx]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket.pop(i) # 리스트에서 제거 (O(bucket 길이))
self.size -= 1
return
raise KeyError(f"{key!r} not found")
# ───────────────────────────── 편의 메서드 ───────────────────────────── #
def __len__(self):
"""len(hashmap) → 현재 엔트리 수"""
return self.size
def __contains__(self, key):
"""key in hashmap → bool"""
return self.get(key, default=_sentinel) is not _sentinel
# 내부 sentinel 객체 (contains 구현에 사용)
_sentinel = object()
# ───────────────────────────── 사용 예시 & Quick Test ───────────────────────────── #
if __name__ == "__main__":
hm = HashMap()
hm.put("apple", 12)
hm.put("banana", 13)
hm.put("cherry", 14)
hm.put("apple", 99) # 덮어쓰기
print("apple =", hm.get("apple")) # 99
print("grape =", hm.get("grape", 0)) # default 0
hm.remove("banana")
print("size =", len(hm)) # 2
print("raw buckets →", hm.buckets) # 내부 구조 확인용