출시·고도화 중
기본 자료구조 안내서 · 6/6
이 안내서의 자료구조는 거의 모든 프로그램의 바닥에 깔려 있습니다. 표준 라이브러리가 이를 어떻게 구현했는지 알면 뜻밖의 성능 문제와 흔한 버그 몇 가지가 설명됩니다.
set 도 개방 주소법 해시 테이블입니다.std::deque 는 고정 크기 덩어리와 덩어리 포인터 표로 이루어지고, std::unordered_map 은 분리 연결법을 쓰며 기본 최대 적재율이 1.0입니다.HashMap 은 2의 거듭제곱 크기 버킷 배열과 기본 적재율 0.75를 쓰고, 한 버킷의 항목이 8개를 넘고 테이블이 64칸 이상이면 그 사슬을 레드-블랙 트리로 바꿉니다.| 구조 | 대표적인 쓰임 |
|---|---|
| 스택 | 함수 호출 스택, 되돌리기 기록, 수식 파싱, 깊이 우선 탐색 |
| 큐 | 작업·메시지 큐, 너비 우선 탐색, 인쇄 대기열, 처리율 제한 창 |
| 원형 버퍼 | 오디오·네트워크 버퍼, 로그 꼬리, 생산자-소비자 파이프 |
| 연결 리스트 | 운영체제 커널의 리스트, 메모리 할당기의 빈 블록 목록, LRU 캐시의 최근 사용 순서 |
| 해시 테이블 | 캐시, 컴파일러의 심볼 테이블, 데이터베이스 해시 조인과 인덱스, 중복 제거 |
둘을 조합한 좋은 예가 LRU 캐시입니다. 해시 맵이 항목을 O(1)에 찾고, 이중 연결 리스트가 최근 사용 순서를 유지해 가장 오래된 항목을 O(1)에 내보냅니다. Python의 OrderedDict 가 바로 그 조합입니다.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.data = OrderedDict()
def get(self, key):
if key not in self.data:
return None
self.data.move_to_end(key) # 가장 최근에 쓴 것으로 표시
return self.data[key]
def put(self, key, value):
self.data[key] = value
self.data.move_to_end(key)
if len(self.data) > self.capacity:
self.data.popitem(last=False) # 가장 오래전에 쓴 것을 내보냄
cache = LRUCache(2)
cache.put("a", 1); cache.put("b", 2); cache.get("a"); cache.put("c", 3)
print(list(cache.data)) # ['a', 'c'] -- 'b' 가 밀려남list.pop(0), ArrayList.remove(0), Array.prototype.shift 는 남은 원소를 모두 옮깁니다. 큐에는 덱이나 원형 버퍼를 씁니다.equals 와 hashCode 를 함께 재정의하고, 그 계산에 쓰는 필드를 바꾸지 않아야 합니다.dict, Map, LinkedHashMap 은 넣은 순서를 지키지만 HashMap, HashSet, std::unordered_map, Python set 은 그렇지 않습니다. 어떤 입력에서 우연히 맞던 코드가 다른 입력에서 깨질 수 있습니다.std::vector 가 재할당되면 그 안을 가리키던 포인터, 참조, 반복자가 모두 무효가 됩니다. 미리 reserve 하거나 인덱스를 저장합니다.RuntimeError, Java는 ConcurrentModificationException 을 냅니다.Java의 함정을 코드로 보면 다음과 같습니다. hashCode 가 없으면 같은 키가 서로 다른 버킷에 들어가 조회가 실패합니다. record 는 두 메서드를 일관되게 만들어 줍니다.
import java.util.HashMap;
public class KeyDemo {
static final class BadPoint {
final int x, y;
BadPoint(int x, int y) { this.x = x; this.y = y; }
@Override public boolean equals(Object o) {
return o instanceof BadPoint p && p.x == x && p.y == y;
}
// hashCode 가 없음: 같은 점인데 해시값이 다름
}
record Point(int x, int y) {} // equals 와 hashCode 를 함께 만들어 줌
public static void main(String[] args) {
var bad = new HashMap<BadPoint, String>();
bad.put(new BadPoint(1, 2), "found");
var good = new HashMap<Point, String>();
good.put(new Point(1, 2), "found");
System.out.println(bad.get(new BadPoint(1, 2)) + " " + good.get(new Point(1, 2))); // 거의 언제나: null found
}
}C++의 함정은 이렇습니다. 재할당 전에 얻은 포인터는 재할당 뒤에 쓰면 안 됩니다.
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{1, 2, 3};
v.reserve(100); // 용량을 미리 확보: 아래에서 재할당이 없음
int* first = &v[0];
for (int i = 0; i < 50; ++i) v.push_back(i);
std::cout << *first << ' ' << v.size() << ' ' << v.capacity() << '\n'; // 1 53 100
// reserve 가 없으면 push_back 이 재할당할 수 있고 first 는 허공을 가리킵니다
}표준 컨테이너는 이 안내서의 구조를 정성껏 다듬은 것입니다. 기하급수적으로 자라는 동적 배열, 블록으로 만든 덱, 적재율을 제한한 해시 테이블이 그 예입니다. 직접 만들기보다 이들을 쓰되, 필요한 연산으로 고르고, 배열 앞에서 빼기, 불안정한 키, 순서에 대한 가정, 무효가 된 참조, 신뢰할 수 없는 키 같은 흔한 함정을 조심합니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.
첫 댓글을 남겨 보세요.