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

"배열은 즉시 접근을 줘 — 근데 정수 인덱스를 알아야만. 해싱이 물어: 어떤 키든 — 이름, 단어, 튜플 — 자기 자신의 인덱스가 될 수 있다면? 그 질문이 구조 전부야."

꿈

배열의 arr[i] 는 i 가 주소를 바로 알려줘서 O(1) 이야. 근데 네 키는 깔끔한 정수인 경우가 드물어 — 사용자명, 단어, ID, 좌표야. "이 사용자명 쓰였나?" 를 리스트에서 검색하면 O(n). 사용자명 자체를 배열 인덱스로 바꿔 arr[i] 처럼 그 슬롯으로 곧장 점프할 수 있다면? 그게 해시맵이 주는 꿈이야.

트릭: 해시 함수

해시 함수는 어떤 키든 받아 결정론적으로 숫자 — 그 해시 — 를 만들어. 그 숫자를 테이블 크기로 modulo 하면 배열 인덱스가 나와. 이제: 키를 저장하려면, 해시해서 인덱스를 얻고 그 슬롯에 떨궈. 조회하려면, 다시 해시해서 같은 인덱스를 얻고 그 슬롯을 읽어. 검색 없음 — 어디 사는지 정확히 계산했어. 두 연산 다 평균 O(1): 해시 계산 한 번 + 배열 접근 한 번.

밑에서, 해시맵은 그냥 배열이야. 해싱은 임의 키가 그 배열의 정수 인덱스처럼 행동하게 하는 어댑터야. 배열 접근이 왜 즉시인지는 이미 알아 (Arrays 트랙의 주소 산술); 해싱은 그 선물을 정수에서 해시 가능한 모든 것으로 확장할 뿐이야.

해시맵은 해시 함수로 키를 배열 인덱스로 바꾸고, 배열의 O(1) 접근을 써. 정수만이 아니라 어떤 해시 가능한 키든 받는 어댑터를 입은 배열이야. 삽입, 조회, 삭제: 다 평균 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