해싱이 배신하는 순간

"해싱은 치트키 같아서 뭐든 여기다 밀어 넣고 싶어져. 그런데 즉시 조회 하나를 얻는 대신 내주는 게 있어. 순서에 대한 감각 전체야. 그 선이 어디인지 아는 게 이번 이야기의 핵심이고."

큰 사각지대: 순서가 없어

해시맵은 키를 해시값에 따라 흩어 놓는데, 그 해시는 일부러 값과 무관하게 만들어져. "이 키가 정확히 존재하나?"에는 최고지만 순서에 관한 질문에는 아무 쓸모가 없지. 해시맵한테는 "가장 작은 키 줘", "10과 20 사이의 키 전부", "이거 다음 키는?" 같은 걸 물을 수가 없어. 전부 쏟아내서 정렬하지 않는 한 말이야. 그러면 O(n log n)이 드니까 애초에 쓰는 이유가 사라지고. 참고로 Python dict가 보존하는 건 삽입 순서지 정렬된 순서가 아니야. 이 둘을 헷갈리면 안 돼. 풀려는 문제가 순서나 범위 질의를 요구하는 순간 해싱은 잘못된 도구고, 트리를 꺼내야 해. 바로 다음 트랙이 가는 곳이지.

다른 배신들

• 최악은 O(n)이야. 공격자가 전부 충돌하는 키를 만들어 낼 수 있으면 모든 연산이 선형 훑기로 떨어져. hash flooding이라고 부르는 실제 서비스 거부 공격이야. Python이 문자열 해시를 프로세스마다 무작위화하는 이유가 이거고(앞에서 본 PYTHONHASHSEED 소금), 그래야 공격자가 충돌 키 묶음을 미리 계산해 둘 수 없거든.
• 가변 키는 맵을 망가뜨려. 리스트는 키로 못 쓰고, 키로 쓴 객체를 나중에 바꿔서도 안 돼. 바뀌면 해시도 바뀌고 맵은 그 키를 다시는 못 찾으니까. 여기서 불변성은 Python의 별난 성질이 아니라 정확성 요구사항이야.
• 메모리를 더 써. 조회를 빠르게 유지해 주는 그 빈 슬롯들도 메모리를 차지하거든. 작고 촘촘한 정수 키만 다룬다면 평범한 배열로 직접 인덱싱하는 쪽이 속도와 공간 양쪽에서 dict를 이길 수도 있어.

더 깊은 교훈: 만능 구조는 없다

퀘스트 전체를 관통하는 이야기가 여기서 또 떠올라. 모든 상황에서 이기는 구조 같은 건 없어. 배열은 삽입을 내주고 인덱싱을 얻고, 연결 리스트는 인덱싱을 내주고 잇기를 얻고, 해시맵은 순서를 내주고 즉시 조회를 얻어. 저마다 어떤 종류의 접근에 맞춰진 추상화인 거지. 숙달은 구조를 외우는 게 아니라 문제를 읽고 그게 어떤 거래를 요구하는지 알아듣는 거야. "빠른 조회도 필요하고 정렬된 순서도 필요해"라는 문장이 나오는 순간, 이 트랙에서 다음 트랙으로 넘어갈 때가 된 거고.

피파의 고백