해싱이 널 배신할 때

"해싱은 치트키처럼 느껴져서, 모든 것에 쓰고 싶어져. 근데 그건 딱 하나 — 즉시 지점 조회 — 를 사주는 대신 다른 하나를 내줘: 순서 감각 전부. 그 선을 아는 게 lesson 이야."

큰 사각지대: 순서 없음

해시맵은 키를 그 해시로 흩는데, 그건 일부러 값과 무관해. "이 정확한 키가 있나?" 엔 좋고, 순서에 관한 어떤 것에도 쓸모없어. 해시맵한테 못 물어: "가장 작은 키 줘", "10 과 20 사이 모든 키", "이것 다음 키" — 전부를 쏟아 정렬 (O(n log n)) 하지 않고는, 그건 목적을 무너뜨려. (Python dict 는 삽입 순서를 보존하지만, 그건 정렬된 순서가 아니야 — 둘을 헷갈리지 마.) 네 문제가 순서나 범위 쿼리가 필요한 순간, 해싱은 틀린 도구고, 트리로 손을 뻗어 — 정확히 다음 트랙이 가는 곳이야.

다른 배신들

최악 O(n). 공격자가 다 충돌하는 키를 만들 수 있으면, 모든 연산이 선형 훑기로 떨어져 — hash flooding 이라는 진짜 서비스 거부 공격. Python 이 문자열 해시를 프로세스별 무작위화하는 (앞의 PYTHONHASHSEED 소금) 이유야: 공격자가 충돌 키 집합을 미리 계산 못 하게.
가변 키는 맵을 망가뜨려. 리스트를 키로 못 쓰고, 키로 쓴 객체를 그 후 변형하면 안 돼 — 바꾸면 그 해시가 바뀌고, 맵이 다시는 못 찾아. 여기서 불변성은 Python 변덕이 아니라; 정확성 요구사항이야.
메모리 오버헤드. 조회를 빠르게 유지하는 빈 슬롯이 메모리도 들어. 작고 빽빽한 정수 키엔, 평범한 배열 (직접 인덱싱) 이 속도랑 공간 둘 다 dict 를 이길 수 있어.

해싱은 O(1) 지점 조회를 주지만 순서를 버려. '가장 작은', '범위 안', '정렬', '다음 더 큰' 이 필요해? 그건 해시가 아니라 트리야. 해싱은 또 O(n) 최악 (충돌) 이 있고, 가변 키를 금지하고, 메모리를 속도랑 맞바꿔. 강력하지만 만능은 아니야.

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

이게 퀘스트 전체의 관통선이고, 또 떠올라: 모든 것에 이기는 구조 하나는 없어. 배열은 삽입을 인덱싱이랑 맞바꾸고; 연결 리스트는 인덱싱을 잇기랑; 해시맵은 순서를 즉시 조회랑. 각자 어떤 종류의 접근에 맞는 추상화야. 숙달은 구조를 외우는 게 아니라 — 문제를 읽고 어떤 거래를 요구하는지 듣는 거야. "빠른 조회 그리고 정렬 순서 둘 다 필요해" 가 이 트랙에서 다음 트랙으로 보내는 문제 진술이야.

피파의 고백

dict 랑 사랑에 빠진 뒤, 끊임없이 "점수 top 10" 이랑 "순위 50~60 사이 모두" 가 필요한 리더보드에 하나 쓰려 했어. 반복된 전체 정렬의 재앙이었어. 아빠가 그냥 말했어: "해싱은 순서가 없어. 트리를 원하는 거야." 그 문장이 경계를 그어줬어: 해시맵은 지점 조회의 반사신경이지만, 문제가 '순서' 나 '범위' 를 속삭이는 순간, 트리한테 넘겨. 다음 트랙이 그 넘김이야.

Code

순서 없음, 가변 키 없음, 소금 친 해시·python

# 1) dict 는 삽입 순서를 보존, 정렬 순서가 아니라.
d = {}
for k in [5, 1, 9, 3]:
    d[k] = k * 10
print(list(d))            # [5, 1, 9, 3] — 삽입 순서, 정렬 아님
print(sorted(d))          # [1, 3, 5, 9] — 그리고 정렬은 매번 O(n log n)
# '가장 작은 키', '[2, 6] 안 키', '5 다음 키' 가 다 먼저 정렬을 요구.
# 그게 자주 필요하면, 해시맵은 틀린 구조 -> 트리를 써.

# 2) 가변 객체는 키가 못 돼 (그리고 키였으면 변형하면 안 돼).
try:
    bad = {[1, 2]: "x"}   # 리스트는 해시 불가능
except TypeError as e:
    print("TypeError:", e)   # unhashable type: 'list'

# 3) 해시 무작위화 (새 프로세스에서 두 번 돌리면 -> 다른 숫자).
print(hash("pippa"))      # 프로세스별 소금; 조작된 충돌 DoS 를 막아

Exercise

각각, 해시맵 (dict/set) 이 맞는 구조인지 순서 있는 게 필요한지 말해: (1) '이 이메일 이미 등록됐나?', (2) '두 날짜 사이 모든 주문 줘', (3) '페이지별 방문 수 세기', (4) '내 점수 위 다음으로 높은 점수가 뭐야?'. 실패하는 것들엔, 해시맵이 뭘 못 하는지 대봐.

Hint

(1) 과 (3) 은 해시에 완벽 (정확 조회, 세기). (2) 와 (4) 는 순서/범위가 필요 — 해시맵은 전체 정렬 없이 '사이' 나 '다음 더 큰' 을 못 줘서, 트리 (또는 정렬된 구조) 를 불러. 그게 Trees 트랙으로의 다리야.

큰 사각지대: 순서 없음

다른 배신들

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

피파의 고백

Code

External links

Exercise

Progress

댓글 0