목차
이 시리즈는 주방 이야기로 시작했다. 상자 하나에 다 넣으면 넣기는 편하고 찾기는 바닥까지 뒤져야 한다는 것. 이제 그릇을 다 열어봤으니 어느 그릇을 언제 꺼내느냐로 닫는다.
다시 주방으로
시작할 때 한 말을 다시 꺼내 보자. 자료구조는 빠른 것과 느린 것으로 나뉘지 않는다. 어느 동작을 싸게 하고 어느 동작을 비싸게 할지 고르는 일이다.
여기까지 열어본 그릇들이 그 말을 하나씩 증명했다.
- 해시테이블은 찾기를 공짜에 가깝게 만들면서 순서를 통째로 내줬다.
- 트리는 순서를 지키면서 찾기를 한 단계 느리게 받았다.
- 힙은 꼭대기 하나만 약속해서 나머지를 정렬하지 않는 값을 벌었다.
- 연결리스트는 끼우기를 싸게 만들고 곧장 가기를 잃었다.
아무것도 잃지 않은 그릇은 하나도 없었다. 그러니 “제일 좋은 것”을 찾는 대신 “내가 무엇을 자주 하는지”를 먼저 알아야 한다.
결국 네 질문이다
첫 글에서 그릇을 만나면 넷을 묻는다고 했다. 그 넷이 여기서 그대로 답이 된다.
초록으로만 채워진 줄이 하나도 없다. 어느 그릇이든 비싸거나, 아예 못 하거나, 그럭저럭인 칸을 안고 있다.
가로로 읽으면 그릇 하나가 무엇을 사고 무엇을 팔았는지 보인다. 세로로 읽으면 한 동작을 위해 무엇을 골라야 하는지 보인다.
그림에서 눈에 띄는 건 한 줄이 통째로 초록인 그릇이 없다는 것이다. 해시테이블은 아예 못 하는 칸이 있고, 이진탐색트리는 못 하는 건 없는 대신 대부분의 칸에서 그럭저럭에 머문다. 만능이 없다는 게 이 표의 결론이다.
한 장으로 본 거래표
말로 옮기면 이렇게 된다. 각 그릇이 무엇을 내주고 무엇을 얻었는지다.
| 그릇 | 얻은 것 | 내준 것 |
|---|---|---|
| 배열 | 몇 번째든 곧장, 붙어 있어 빠름 | 중간에 끼우면 뒤를 전부 민다 |
| 연결리스트 | 끼우고 빼기가 고리 둘 | 곧장 못 간다. 흩어져 있어 느리다 |
| 스택·큐 | 규칙이 단순해 읽는 사람이 덜 의심한다 | 중간을 아예 못 만진다 |
| 해시테이블 | 찾기가 사실상 공짜 | 순서·범위·정렬을 전부 잃는다 |
| 이진탐색트리 | 순서를 지키면서 반씩 좁힌다 | 찾기가 해시보다 느리고, 쏠리면 무너진다 |
| 힙 | 다음 하나를 늘 싸게 꺼낸다 | 꼭대기 말고는 아무 순서도 모른다 |
| 그래프 | 관계 자체를 담는다 | 돌아다니는 값이 비싸고 순환을 조심해야 한다 |
이 표는 “무엇이 좋은가”가 아니라 “무엇을 팔았는가”로 읽어야 한다. 내가 안 쓰는 것을 판 그릇이면 그건 손해가 아니다.
먼저 물을 것: 무엇을 가장 자주 하나
고르는 순서가 있다. 첫 질문이 대부분을 결정한다.
키 하나로 찾는 게 대부분이라면 해시테이블이다. 회원을 아이디로, 설정을 이름으로, 캐시를 키로 꺼내는 일. 실무 코드에서 가장 흔한 모양이고, Map을 쓰면 그게 이거다.
앞에서부터 순서대로 훑는 게 대부분이라면 배열이다. 목록을 받아 화면에 뿌리거나, 전부 돌면서 합계를 내는 일. 이때 해시테이블을 쓰면 얻는 게 없고 순서만 잃는다.
양 끝에서만 넣고 뺀다면 스택이나 큐다. 그리고 이때는 이름을 제대로 붙이는 게 성능보다 중요하다. 스택이라고 말하는 순간 중간을 안 건드린다는 약속이 생긴다.
다음 하나만 계속 꺼낸다면 힙이다. 전부 정렬하려던 코드가 사실 이 문제인 경우가 꽤 있다.
그다음: 순서가 필요한가
첫 질문에서 해시테이블이 나왔다면 하나를 더 물어야 한다. 순서나 범위로 물을 일이 있나.
- “20에서 50 사이” → 해시테이블로는 못 한다
- “가나다순으로 보여줘” → 못 한다
- “가장 최근 것부터” → 못 한다
하나라도 있으면 트리 쪽이다. 실무에서는 대개 정렬된 맵이라는 이름으로 있다. 그리고 이 질문이 데이터베이스에서는 인덱스를 무엇으로 만드느냐로 그대로 나타난다.
⚠️ 자주 걸리는 자리 하나. 넣은 순서를 유지하는 맵과 키 순서로 정렬된 맵은 다른 것이다. 자바의 LinkedHashMap과 TreeMap, 파이썬 딕셔너리의 삽입 순서 유지가 여기 걸린다. “순서가 있다”는 말이 어떤 순서인지 확인하지 않으면 범위 조회에서 어긋난다.
그다음: 얼마나 커지나
마지막 질문이 가장 자주 무시된다. 이 데이터가 얼마나 커지나.
100건이면 무엇을 써도 즉시 끝난다. 리스트를 매번 훑어도 사람이 못 느낀다. 이 구간에서는 고민하는 시간이 절약하는 시간보다 비싸다.
갈리기 시작하는 건 수만 건부터고, 그때 갈리는 건 대개 눈에 안 보이는 반복 때문이다.
for (Order o : orders) { // 1만 번
if (vipIds.contains(o.userId)) // vipIds가 리스트면 여기서 또 1만 번이런 코드는 100건일 때 아무 문제가 없다가 데이터가 늘면서 갑자기 무너진다. 성능이 서서히 나빠지는 게 아니라 어느 날 절벽처럼 떨어지는 건 대개 이 모양이다.
대부분은 셋으로 끝난다
솔직하게 말할 대목이 있다. 실무 코드의 대부분은 배열·해시테이블·큐 셋으로 끝난다.
트리는 직접 쓰기보다 데이터베이스 인덱스 안에서 만난다. 힙은 스케줄러나 라이브러리 안에 들어 있다. 그래프는 문제를 그렇게 읽을 때 꺼낸다. 손으로 짜는 일은 드물다.
그러면 나머지를 왜 배웠나. 남이 만든 것을 옳게 고르고 쓰기 위해서다.
- 인덱스를 걸었는데 왜 범위 조회만 빠르고 다른 건 그대로인지
HashMap이 왜 갑자기 느려졌는지, 키로 쓴 객체를 나중에 고치지는 않았는지- 정렬해서 상위 10개를 뽑는 코드가 왜 메모리를 그렇게 쓰는지
- “순환 의존” 에러가 왜 나는지
이런 판단은 그릇의 속을 알아야 내려진다. 직접 만들 일이 없다는 게 몰라도 된다는 뜻은 아니다.
안 고르는 것도 고르는 것이다
마지막으로 반대 방향의 주의를 하나 둔다. 이 시리즈를 읽고 나면 코드를 열어 그릇부터 바꾸고 싶어진다. 대개는 하지 않는 게 맞다.
- 재보지 않았으면 고치지 않는다. 느릴 것 같은 자리와 실제로 느린 자리는 자주 다르다.
- 정교한 그릇은 읽기 어렵다. 팀이 유지할 코드라면 그것도 값이다.
- 데이터 크기를 모르면 판단할 수 없다. 커질지 안 커질지가 답을 바꾼다.
그릇을 고르는 일이 값을 하는 순간은 둘뿐이다. 처음 만들 때 기본값을 옳게 잡는 것, 그리고 재보고 원인이 그릇으로 드러났을 때 바꾸는 것. 그 사이에서 미리 바꿔두는 것은 대개 값만 내고 아무것도 못 산다.
정리
- 아무것도 잃지 않은 그릇은 없었다. 고르는 일은 무엇을 팔지 고르는 일이다.
- 순서는 셋이다. 무엇을 자주 하나 → 순서가 필요한가 → 얼마나 커지나.
- 첫 질문에서 대부분 끝난다. 키로 찾으면 해시, 순서대로 훑으면 배열, 양 끝만 쓰면 스택·큐, 다음 하나만 꺼내면 힙.
- 실무 코드는 대개 셋으로 끝나지만, 나머지를 아는 이유는 남이 만든 것을 옳게 쓰기 위해서다.
- 재보지 않았으면 바꾸지 않는다. 안 고르는 것도 결정이다.