해시맵 - 이름표로 바로 찾는 창고

Python의 dict가 내부적으로 하는 일을 직접 만드는 겁니다.

동작 원리

1. 해시 함수: 키(문자열)를 숫자로 바꿈
2. 그 숫자를 버킷(bucket) 개수로 나눈 나머지 = 저장 위치(방 번호)
3. 찾을 때도 같은 계산 → 바로 그 방만 확인 → 평균 O(1)

def _hash(self, key: str) -> int:
    """키 문자열을 방 번호(버킷 인덱스)로 바꾸는 함수"""
    h = 0
    for ch in key:            # 문자 하나하나에
        h = (h * 31 + ord(ch)) % self._bucket_count  # 큰 소수 곱하기 트릭으로 고루 분포
    return h

충돌(collision)과 체이닝

다른 키가 같은 방 번호로 배정되는 경우가 생깁니다(충돌). 체이닝 = 그 방 안에 여러 건을 연결 리스트로 줄 세워두는 방식. → 요구사항 권장대로 위에서 만든 이중 연결 리스트를 재사용하면 됩니다.

로드 팩터(load factor)와 확장

• 로드 팩터 = 저장된 항목 수 ÷ 버킷 수 (방이 얼마나 붐비는지)
• 0.75를 넘으면 충돌이 잦아져 느려지므로, 버킷을 2배로 늘리고 모든 항목을 재배치(rehash)

주의: 버킷 배열은 "고정 길이 배열/인덱스 접근" 수준으로 list를 쓰는 것까지만 허용됩니다. dict로 put/get을 구현하는 건 금지!

---

출처: Codyssey-B1/B5-1