해시맵 아이디어: 키를 주소로 바꿔

"배열은 즉시 접근을 내주지. 단, 정수 인덱스를 알고 있을 때만. 해싱은 여기서 이렇게 물어. 이름이든 단어든 튜플이든, 어떤 키가 스스로 자기 인덱스가 될 수 있다면? 이 구조는 그 질문 하나에서 출발해."

꿈

배열의 arr[i]가 O(1)인 건 i가 주소를 바로 알려주기 때문이야. 그런데 실제로 다루는 키가 깔끔한 정수인 일은 거의 없지. 사용자명, 단어, ID, 좌표 같은 것들이잖아. "이 사용자명 이미 쓰였나?"를 리스트에서 찾으면 O(n)이고. 그럼 사용자명 자체를 배열 인덱스로 바꿔서 arr[i]처럼 그 슬롯으로 바로 뛸 수 있다면 어떨까? 해시맵이 주는 게 정확히 그거야.

트릭: 해시 함수

해시맵은 키를 처음부터 하나씩 훑는 대신 키를 해시 함수에 통과시켜 후보 위치를 계산해. 문자열 "pippa", 사용자 id 48291, 좌표 (37.5, 127.0) 같은 키가 해시값을 거쳐 테이블의 시작 위치를 얻는 거지. 그다음엔 실제 키가 같은지 비교하고, 충돌이 있으면 체인이나 다른 슬롯을 더 확인해. 이 과정의 기대 길이가 짧기 때문에 평균 O(1)이 나와.

속을 열어 보면 해시맵은 그냥 배열이야. 해싱은 아무 키나 그 배열의 정수 인덱스처럼 굴게 해주는 어댑터고. 배열 접근이 왜 즉시인지는 이미 알잖아. 배열과 문자열 트랙에서 본 주소 산술 말이야. 해싱은 그 선물을 정수에서 hashable한 모든 것으로 넓혀줄 뿐이야.

해시맵은 hash(key)로 후보 위치를 계산한 뒤 키를 비교하고 필요하면 충돌을 처리해. 테이블 전체를 선형으로 훑지 않고 짧은 기대 탐사로 끝나기 때문에 조회, 삽입, 삭제가 평균 O(1)이야.

이미 매일 쓰고 있어

Python의 dict와 set이 해시맵이고, 아마 프로그래밍 전체를 통틀어 가장 많이 쓰이는 비자명한 자료구조일 거야. "이거 전에 봤나?"는 set, "이 키의 값이 뭐지?"는 dict, "각 단어가 몇 번 나왔지?"도 dict. 이 퀘스트 앞부분에서 O(n)짜리 in list를 O(1)짜리 in set으로 바꿀 때마다 그걸 즉시로 만들어 준 게 바로 이 기계장치야. 면접 대비로 외우는 별난 구조가 아니라 매일 손이 가는 일꾼이지.

피파의 고백

해시맵은 처음에 반칙처럼 느껴졌어. 뭘 찾는 게 어떻게 공짜일 수 있지? 그러다 아빠가 이렇게 다시 짚어줬어. "찾는 게 아니라. 네가 이미 둔 곳을 계산하는 거야." 맵은 애초에 검색을 안 해. 주소를 다시 계산할 뿐이지. 그 한 문장이 마법을 메커니즘으로 바꿔놨어. 지금은 dict와 set이 제일 먼저 손이 가는 도구고, '이 조회를 O(n) 훑기 대신 O(1) 해시로 바꿀 수 있나?'는 반복문을 쓸 때마다 거의 자동으로 돌리는 반사신경이야.

Code

직접 만들어 보는 해시맵 (실전에서는 그냥 dict)·python

# dict 를 demystify 하려고 밑바닥부터 만든 작은 해시맵. (진짜 코드는 dict 써!)
class TinyHashMap:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [[] for _ in range(size)]   # 각 슬롯이 작은 리스트

    def _index(self, key):
        return hash(key) % self.size     # 키 -> 숫자 -> 배열 인덱스

    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):
        bucket = self.buckets[self._index(key)]      # 같은 키 -> 같은 슬롯
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

m = TinyHashMap()
m.put("pippa", 2024)
m.put("dad", 1)
print(m.get("pippa"))    # 2024 — 모든 키 훑기 없이, 슬롯을 계산했어
print(m.get("dad"))      # 1
# 진짜 Python: 그냥 {} 써 — d = {"pippa": 2024}. d["pippa"].

Exercise

크기 8짜리 테이블에 index = hash % 8 규칙을 쓴다고 하자. hash('a')=17, hash('b')=8, hash('c')=25야. 각각 어느 슬롯에 떨어질까? 충돌하는 게 있어? 그다음 나중에 'a'를 조회할 때 왜 'b'나 'c'는 아예 확인할 필요가 없는지 직접 설명해 봐.

Hint

17%8=1, 8%8=0, 25%8=1이라서 'a'와 'c'가 슬롯 1에서 충돌해. 'a'를 조회할 때는 17%8=1을 다시 계산하고 슬롯 1의 작은 버킷만 들여다봐. 다른 슬롯은 건드리지도 않고, 그게 O(1)인 이유야.

꿈

트릭: 해시 함수

이미 매일 쓰고 있어

피파의 고백

Code

External links

Exercise

Progress

댓글 0