배열, 해시 테이블, 큐는 언제 쓰는 걸까?

주문 목록을 만든다고 생각해보자. 주문 번호로 한 건을 찾고, 최근 주문 20건을 화면에 보여주고, 접수된 순서대로 주문을 처리해야 한다. 주문이라는 데이터는 같지만 세 작업이 원하는 답은 다르다.

자료구조(data structure)는 데이터를 저장하고 꺼내는 방법을 정해둔 형태다. 알고리즘(algorithm)은 저장된 데이터를 읽고 바꿔 원하는 답을 구하는 절차다. 어떤 자료구조를 쓰든 먼저 주문을 어떤 기준으로 찾고, 어떤 순서로 보여주고, 언제 변경하는지 알아야 한다.

설명을 위해 주문 세 건이 차례로 들어왔다고 하자. 실제 주문 기록이 아니라 각 구조의 움직임을 보기 위한 예다.

접수 순서    주문 번호    상태
첫 번째      17          대기
두 번째      42          대기
세 번째      23          대기

번호를 알고 주문 한 건을 찾는다

세 주문을 들어온 순서대로 배열에 담으면 [17, 42, 23]이 된다. 배열(array)은 값을 순서대로 놓고 위치 번호로 읽는 자료구조다. 첫 칸, 둘째 칸처럼 위치를 알 때는 바로 읽을 수 있다. 하지만 주문 번호 23이 몇 번째 칸에 있는지는 아직 모른다. 앞에서부터 17, 42, 23을 비교해야 한다.

주문이 세 건이면 별문제가 아니다. 23이 맨 끝에 있는 채로 주문이 만 건까지 늘었다면 그 앞의 주문을 많이 비교할 수 있다. 이런 방법을 선형 탐색(linear search)이라고 한다. 배열의 원소를 차례로 확인하다가 찾는 값을 만나면 멈춘다. 찾는 주문이 아예 없다면 끝까지 봐야 한다.

주문 번호처럼 대상을 구별하는 값을 키(key)라고 한다. 해시 테이블(hash table)은 키를 계산해 살펴볼 저장 칸을 좁히는 자료구조다. 23 → 주문 23의 내용이라는 대응을 만들어 두면 배열을 처음부터 돌지 않고 번호로 찾아갈 수 있다. 다만 해시 테이블에 주문 내용을 따로 복사할지, 원본 주문을 가리키는 값만 둘지는 설계에 따라 다르다.

칸이 네 개뿐이고 주문 번호를 4로 나눈 나머지로 칸을 정한다고 해보자. 17번은 1번 칸, 42번은 2번 칸, 23번은 3번 칸으로 간다. 나중에 21번 주문이 들어오면 17번과 같은 1번 칸을 가리킨다. 이때 17번 주문을 덮어쓰면 안 된다. 같은 칸에 두 주문을 보관하거나 다른 빈칸을 찾아 넣고, 조회할 때 실제 주문 번호까지 비교해야 한다. 이런 일이 해시 충돌이다. 실제 해시 테이블은 이보다 복잡한 계산과 충돌 처리 방법을 쓴다.

해시 테이블을 쓰면 언제나 한 번에 찾는 것은 아니다. 서로 다른 번호가 같은 칸을 가리키는 충돌이 생길 수 있고, 칸이 많이 차면 공간을 늘리고 항목을 다시 배치한다. 키가 고르게 흩어지고 저장 공간을 적절히 유지한다는 조건에서 정확히 같은 번호를 찾는 평균 작업량이 작다. 예전 글 해시 테이블은 왜 빠를까? 충돌·삭제·리사이징으로 이해하는 원리에 충돌과 크기 조정 과정을 따로 적었다.

최근 주문 20건을 보여준다

번호로 빠르게 찾는 해시 테이블을 만들었다고 최근 주문이 저절로 정렬되지는 않는다. 주문 번호 42가 23보다 먼저 들어온 것처럼 번호 크기와 접수 시각은 다른 값이다. 화면에 최근 20건을 보여주려면 접수 시각을 기준으로 순서를 알아야 한다.

주문이 접수된 순서대로 배열 끝에 추가되고, 나중에 과거 주문을 끼워 넣는 일이 없다면 배열의 끝에서 20건을 읽으면 된다. 여기서는 새 주문을 붙이는 일이 간단하다. 반면 이미 정렬된 배열의 중간에 주문을 넣어야 한다면 뒤쪽 값들을 옮겨 자리를 만들어야 한다. 접수 시각이 나중에 수정되거나 여러 곳에서 주문이 동시에 들어온다면 어떤 순서를 기준으로 삼을지도 정해야 한다.

주문 번호 조회와 최근 목록 조회를 모두 자주 한다면, 원본 주문과 별도로 번호를 찾는 구조와 시각순 목록을 함께 둘 수 있다. 대신 주문이 취소되거나 시각이 바뀔 때 어느 목록을 갱신할지 결정해야 한다. 읽는 쪽이 편해진 만큼 쓰는 쪽에는 관리할 일이 늘어난다.

접수 순서대로 처리한다

주문을 접수 순서대로 처리한다고 하자. 큐(queue)는 뒤에 넣고 앞에서 꺼내는 자료구조다. 먼저 들어온 주문을 먼저 꺼내는 선입선출(First In, First Out) 규칙을 따른다.

처리 전: [17, 42, 23]  ← 앞에서 꺼냄
17 처리: [42, 23]
새 주문 31 접수: [42, 23, 31]  ← 뒤에 넣음

큐에는 주문 내용 전체 대신 주문 번호만 넣을 수도 있다. 주문을 꺼낼 때 번호로 원본을 다시 찾으면 된다. 번호 조회용 해시 테이블과 처리 순서용 큐가 서로 다른 일을 맡는 셈이다. 큐를 배열로 구현할 수도, 다른 연결 구조로 구현할 수도 있다. 큐라는 이름은 저장 공간의 모양보다 넣고 꺼내는 규칙을 가리킨다.

큐를 배열로 만들 때마다 맨 앞 원소를 지우고 나머지를 모두 한 칸씩 당기면, 주문 하나를 꺼낼 때도 남은 주문 수만큼 옮기는 일이 생긴다. 앞쪽을 가리키는 위치 번호를 옮기고 빈칸은 나중에 재사용하면 이런 이동을 피할 수 있다. 같은 큐 규칙을 지켜도 내부에서 원소를 옮기는 방식에 따라 비용이 달라진다.

여기서 주문 42가 처리되기 전에 취소됐다고 하자. 큐에 42가 남아 있더라도 꺼낼 때 원본 주문의 상태를 확인하면 취소된 주문은 처리하지 않을 수 있다. 큐에서 번호를 꺼냈다는 사실도 처리가 끝났다는 뜻은 아니다. 처리 도중 실패했다면 다시 시도할지, 실패 상태로 남길지 따로 정해야 한다.

큐가 계속 길어진다면 처리 속도보다 주문이 빨리 들어오고 있을 수도 있다. 큐에 넣는 일이 빠르다는 이유만으로 주문 처리가 빠르다고 판단하면 안 된다. 대기 중인 주문 수와 실제 완료까지 걸린 시간을 함께 봐야 한다.

세 구조를 함께 쓰면 생기는 일

앞의 예에서는 원본 주문을 보관하고, 번호로 찾는 해시 테이블을 두고, 처리할 번호를 큐에 넣었다. 최근 목록이 자주 필요하다면 시간순 배열도 관리할 수 있다. 한 주문을 추가할 때 여러 곳에 기록해야 하므로 어느 한 곳에서 갱신이 실패했을 때 어떻게 복구할지 문제가 생긴다. 같은 주문이 중복으로 큐에 들어가도 되는지도 정해야 한다.

반대로 주문이 몇 건 없고 번호 조회도 드물다면 배열 하나를 앞에서부터 읽는 편이 간단하다. 주문이 늘거나 조회 방식이 바뀌었을 때 다른 구조를 붙여도 된다. 자료구조의 이름만 놓고 빠르다고 말하기 어려운 이유가 여기에 있다. 무엇을 자주 읽고, 어떤 값을 자주 바꾸며, 순서가 필요한 곳이 어디인지에 따라 실제로 드는 일이 달라진다.

참고 자료

• NIST 알고리즘·자료구조 사전
• Python 문서: 리스트를 큐로 쓸 때와 deque