이 글에서 얻는 것
- 해시맵이 평균 O(1)인 이유와, “갑자기 느려지는 순간”이 언제인지(충돌/리사이즈/메모리) 설명할 수 있습니다.
- Rust 표준
HashMap이 사용하는 SwissTable 계열의 아이디어(컨트롤 바이트, 캐시 친화, 프로빙)를 큰 그림으로 이해합니다. with_capacity/reserve/entry같은 API가 성능에 어떤 영향을 주는지 감각을 잡습니다.- “보안 vs 성능” 관점에서 해시 함수(SipHash vs ahash 등)를 선택할 때 무엇을 고려해야 하는지 정리합니다.
왜 백엔드에서 해시맵 내부를 알아야 할까
해시맵은 캐시, 집계, 중복 제거, 라우팅(키 → 핸들러), 세션/토큰 관리 등 백엔드 곳곳에 등장합니다. 대부분의 경우 “그냥 쓰면 빨라서” 문제가 없지만, 규모가 커지면 다음이 성능/장애로 이어집니다.
- 키가 많아질수록 리사이즈(재해싱) 비용이 스파이크를 만든다
- 충돌이 많아지면 “O(1)”이 아니라 체감상 O(n) 처럼 느려진다
- 키/값이 무겁거나(큰 객체) 할당이 많으면 메모리/GC 부담이 커진다
1) 해시맵의 기본 동작(충돌 처리 관점)
해시맵은 크게 두 방식을 많이 씁니다.
- Separate Chaining: 버킷마다 리스트/트리로 충돌을 연결(자바 HashMap은 체이닝 + 일부 트리화)
- Open Addressing: 충돌이 나면 “다음 칸”으로 이동하며 빈 자리를 찾음(프로빙)
Rust의 HashMap은 기본적으로 open addressing 계열(구현은 hashbrown/SwissTable 아이디어)을 사용합니다.
핵심 감각:
- open addressing은 메모리가 비교적 연속적이라 캐시 친화적일 수 있음
- 대신 부하율(load factor)이 올라가면 프로빙 길이가 길어져 성능이 급격히 나빠질 수 있음
2) SwissTable 계열의 아이디어(큰 그림)
SwissTable의 포인트는 “충돌이 나도 빨리 찾게” 만드는 구현 디테일에 있습니다.
- 엔트리를 저장하는 배열과 별도로, 컨트롤 바이트(control bytes) 라는 작은 메타데이터 배열을 둡니다.
- 조회할 때는 컨트롤 바이트를 먼저 훑어서(종종 SIMD로) “후보가 될 수 있는 버킷”을 빠르게 좁힙니다.
- 그 다음에만 실제 키 비교를 수행합니다(키 비교는 보통 더 비싸기 때문).
이 구조가 주는 효과:
- 캐시 미스가 줄어들고, 키 비교 횟수가 줄어들어 평균 성능이 좋아질 수 있습니다.
3) 리사이즈와 capacity: 성능 스파이크의 주범
해시맵은 내부 배열이 꽉 차면 더 큰 배열로 옮기는 과정(리사이즈/재해싱)을 합니다. 이때 순간적으로 CPU/메모리를 크게 쓰면서 지연이 튈 수 있습니다.
그래서 “대충 크기를 예측할 수 있을 때”는 초기 용량을 주는 게 좋습니다.
use std::collections::HashMap;
let mut counts: HashMap<String, usize> = HashMap::with_capacity(100_000);
실무 감각:
- 이벤트 집계/로그 분석/대량 배치처럼 “대략 N개 들어올 것”을 알면
with_capacity/reserve로 스파이크를 줄입니다.
4) entry API: 중복 조회를 줄이는 기본기
집계 코드는 get 후 insert를 하면 해시를 두 번 치는 경우가 많습니다.
entry는 한 번의 조회로 “있으면 수정/없으면 생성”을 처리합니다.
use std::collections::HashMap;
let mut counts: HashMap<String, usize> = HashMap::new();
for word in ["a", "b", "a"] {
*counts.entry(word.to_string()).or_insert(0) += 1;
}
5) 해시 함수 선택: 보안 vs 성능
해시맵은 입력이 “특정 형태로 편향”되면 충돌이 늘어 성능이 급락할 수 있습니다. 그래서 표준 라이브러리는 일반적으로 충돌 공격(DoS)에 강한 해시를 기본값으로 둡니다(대신 느릴 수 있음).
- 기본(SipHash 계열): 공격에 비교적 강함(사용자 입력 키가 많은 경우 안전)
- 빠른 해시(ahash 등): 성능이 좋을 수 있지만, 신뢰 경계 밖 입력에는 주의해야 함
선택 기준(요약):
- 키가 외부 사용자 입력에 크게 좌우된다 → 기본 해시 유지가 안전
- 내부 시스템에서 생성된 키(신뢰 가능한 입력) + 성능 병목이 명확하다 → 빠른 해시를 “근거 있게” 고려
6) 실무에서 자주 하는 실수
- “Map이 느리다”라고 느끼면 무작정 해시를 바꾸기 전에, 먼저 리사이즈/할당/키 크기부터 확인하기
- 커스텀 키 타입을 만들 때
Hash/Eq가 일관되지 않으면(동등한데 해시가 다름) 조회가 깨집니다 - 순회 순서가 안정적일 거라고 기대하기(해시맵의 순서는 보장되지 않습니다)
연습(추천)
with_capacity를 넣었을 때/안 넣었을 때 대량 삽입의 지연 스파이크를 비교해보기entry로 집계를 작성하고,get+insert와 비교해서 코드/성능이 어떻게 달라지는지 정리해보기- “충돌이 많아지는 입력”을 일부러 만들어서, 해시맵 성능이 어떻게 변하는지 관찰해보기(학습용으로만)
💬 댓글