pkglog
EN

Rust 컬렉션 | Vec, HashMap, HashSet

작성 · · 17분 읽기 · 수정 중급 튜토리얼

이 글의 핵심

Rust 컬렉션에서 막히는 지점은 대부분 문법이 아니라 소유권입니다. 값을 넣을 때 이동되는지, 순회할 때 &T·&mut T·T 중 무엇을 받는지 구분하는 법을 Vec·HashMap·HashSet 예제와 단어 빈도 카운터로 익히고, Vec·VecDeque·LinkedList와 HashMap·BTreeMap을 어떤 상황에서 골라야 하는지 성능 관점에서 비교합니다.

시리즈 안내

#06 | 📋 전체 목차 | 이전: #05 트레이트 · 다음: #07 동시성

들어가며

Vec·HashMap 등 컬렉션은 요소의 소유권을 어떻게 넣고 빼는지가 API마다 다릅니다. 열쇠를 넘기는지(push), 잠깐 빌려만 보는지(iter)를 구분하면 읽기 쉽습니다.

Vec 생성·메서드·순회

기본 사용

fn main() {
    // 빈 벡터 생성
    let mut v: Vec<i32> = Vec::new();
    
    // 요소 추가
    v.push(1);
    v.push(2);
    v.push(3);
    
    println!("{:?}", v);  // [1, 2, 3]
    
    // 매크로로 생성
    let v = vec![1, 2, 3, 4, 5];
    
    // 인덱스 접근
    println!("{}", v[0]);  // 1
    
    // get으로 안전 접근
    match v.get(2) {
        Some(value) => println!("값: {}", value),
        None => println!("인덱스 초과"),
    }
    
    // 마지막 요소 제거
    let mut v = vec![1, 2, 3];
    let last = v.pop();
    println!("{:?}", last);  // Some(3)
}

v[0]과 v.get(0)의 차이는 실패 처리 방식입니다. 인덱스가 범위를 벗어나면 v[10]은 index out of bounds: the len is 5 but the index is 10 메시지와 함께 panic하고, get은 None을 돌려줍니다. 인덱스가 코드 로직상 절대 벗어날 수 없다면 []가 간결하고, 사용자 입력이나 외부 데이터로 인덱스를 만든다면 get으로 받아 None을 처리하는 편이 안전합니다. pop()이 Option을 반환하는 것도 같은 이유로, 빈 벡터에서 꺼내는 상황을 타입으로 강제로 처리하게 만듭니다.

Vec를 처음 쓸 때 가장 많이 만나는 컴파일 에러는 다음 형태입니다.

let mut v = vec![1, 2, 3];
let first = &v[0];      // 불변 참조
v.push(4);              // error[E0502]: cannot borrow `v` as mutable
                        // because it is also borrowed as immutable
println!("{}", first);

“첫 번째 요소만 봤을 뿐인데 왜 뒤에 추가를 못 하지?”라고 느끼기 쉽지만, 이유는 명확합니다. push가 용량을 넘기면 Vec는 더 큰 버퍼를 새로 할당하고 기존 요소를 옮긴 뒤 이전 버퍼를 해제합니다. 그러면 first는 해제된 메모리를 가리키게 됩니다. C++의 std::vector에서 반복자 무효화로 생기는 바로 그 버그를 Rust는 빌림 규칙으로 컴파일 시점에 막는 것입니다. 해결은 참조 대신 값을 복사해 두거나(let first = v[0];), push를 참조 사용이 끝난 뒤로 옮기는 것입니다.

Vec 메서드

let mut v = vec![1, 2, 3, 4, 5];
// 길이
println!("길이: {}", v.len());
// 비어있는지
println!("비어있음: {}", v.is_empty());
// 특정 인덱스에 삽입
v.insert(2, 10);  // [1, 2, 10, 3, 4, 5]
// 특정 인덱스 제거
v.remove(2);  // [1, 2, 3, 4, 5]
// 비우기
v.clear();
// 용량 관리 (요소를 넣지 않으면 타입을 추론할 수 없으므로 명시)
let mut v: Vec<i32> = Vec::with_capacity(10);
println!("용량: {}", v.capacity());

Vec 순회

let v = vec![1, 2, 3, 4, 5];
// 불변 참조
for item in &v {
    println!("{}", item);
}
// 가변 참조
let mut v = vec![1, 2, 3];
for item in &mut v {
    *item *= 2;
}
println!("{:?}", v);  // [2, 4, 6]
// 소유권 이동
for item in v {
    println!("{}", item);
}
// v는 더 이상 사용 불가

세 가지 순회 형태는 for 문이 내부적으로 IntoIterator를 호출하는 대상이 다를 뿐입니다. for item in &v는 v.iter()와 같아서 item이 &i32이고, &mut v는 v.iter_mut()로 &mut i32를, v 자체는 v.into_iter()로 i32 값을 꺼냅니다. 마지막 형태 이후에 v를 쓰면 borrow of moved value: v 에러가 납니다. i32처럼 복사가 싼 타입이라면 차이를 느끼기 어렵지만, Vec<String>을 소유권 이동으로 순회하면 각 String을 복제 없이 가져갈 수 있어서 변환 후 원본이 필요 없을 때 가장 효율적입니다.

HashMap<K, V> 기본 사용과 메서드

기본 사용

use std::collections::HashMap;
fn main() {
    let mut scores = HashMap::new();
    
    // 삽입
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Red"), 50);
    
    // 조회
    let team = String::from("Blue");
    let score = scores.get(&team);
    
    match score {
        Some(s) => println!("점수: {}", s),
        None => println!("팀 없음"),
    }
    
    // 기본값
    let score = scores.get("Green").unwrap_or(&0);
    println!("점수: {}", score);
}

insert(String::from("Blue"), 10)에서 String은 맵으로 이동합니다. 이후 그 변수는 쓸 수 없고, 맵이 키를 소유합니다. 반면 조회는 scores.get("Green")처럼 &str로도 할 수 있습니다. String이 Borrow<str>를 구현하기 때문에 HashMap<String, V>는 &str로 찾을 수 있고, 조회 때마다 String을 새로 만들 필요가 없습니다. unwrap_or(&0)에서 &0인 이유는 get이 값의 참조(Option<&i32>)를 돌려주기 때문입니다. 값을 복사해서 받고 싶다면 scores.get("Green").copied().unwrap_or(0)이 더 읽기 쉽습니다.

성능 측면에서 알아둘 점도 있습니다. 표준 HashMap의 기본 해셔는 해시 충돌 공격(HashDoS)에 강한 SipHash 계열이고 프로세스마다 무작위 시드를 씁니다. 안전한 대신 짧은 정수 키에서는 상대적으로 느리므로, 외부 입력이 키로 들어오지 않는 내부 캐시라면 rustc-hash(FxHashMap)나 ahash 같은 크레이트로 해셔를 바꾸기도 합니다. 무작위 시드 때문에 순회 순서가 실행할 때마다 달라진다는 점도 기억해야 합니다. 테스트에서 HashMap을 순회한 결과를 문자열로 비교했다가 가끔만 실패하는 불안정한 테스트가 만들어지는 흔한 원인입니다.

HashMap 메서드

use std::collections::HashMap;
let mut map = HashMap::new();
map.insert("a", 1);
map.insert("b", 2);
// 존재 여부
if map.contains_key("a") {
    println!("a 있음");
}
// 없을 때만 삽입
map.entry("c").or_insert(3);
map.entry("a").or_insert(10);  // 무시됨
// 값 수정
let count = map.entry("a").or_insert(0);
*count += 1;
// 순회
for (key, value) in &map {
    println!("{}: {}", key, value);
}
// 삭제
map.remove("b");

중복 제거와 집합 연산: HashSet

use std::collections::HashSet;
fn main() {
    let mut set = HashSet::new();
    
    // 추가
    set.insert(1);
    set.insert(2);
    set.insert(3);
    set.insert(1);  // 중복 무시
    
    println!("{:?}", set);  // {1, 2, 3} (출력 순서는 보장되지 않음)
    
    // 포함 여부
    if set.contains(&2) {
        println!("2 있음");
    }
    
    // 집합 연산
    let set1: HashSet<_> = [1, 2, 3].iter().cloned().collect();
    let set2: HashSet<_> = [2, 3, 4].iter().cloned().collect();
    
    // 합집합
    let union: HashSet<_> = set1.union(&set2).cloned().collect();
    println!("합집합: {:?}", union);  // {1, 2, 3, 4}
    
    // 교집합
    let intersection: HashSet<_> = set1.intersection(&set2).cloned().collect();
    println!("교집합: {:?}", intersection);  // {2, 3}
    
    // 차집합
    let difference: HashSet<_> = set1.difference(&set2).cloned().collect();
    println!("차집합: {:?}", difference);  // {1}
}

union, intersection, difference는 새 집합을 만들지 않고 두 집합을 빌려 보는 반복자를 돌려줍니다. 요소 타입이 &i32라서 새 HashSet<i32>로 모으려면 .cloned()(또는 .copied())가 필요합니다. 결과를 한 번 순회만 할 거라면 collect 없이 반복자로 바로 쓰는 편이 할당이 없어 효율적입니다. 또 Rust 1.56부터는 [1, 2, 3].iter().cloned().collect() 대신 HashSet::from([1, 2, 3])로 더 간단히 만들 수 있습니다. HashSet<T>는 내부적으로 HashMap<T, ()>이므로 요소 타입에 필요한 조건(Hash + Eq)과 성능 특성은 HashMap과 같습니다.

반복자 메서드 체인

기본 반복자

let v = vec![1, 2, 3, 4, 5];
// iter: 불변 참조
let sum: i32 = v.iter().sum();
println!("합계: {}", sum);
// iter_mut: 가변 참조
let mut v = vec![1, 2, 3];
for item in v.iter_mut() {
    *item *= 2;
}
// into_iter: 소유권 이동
let v = vec![1, 2, 3];
let doubled: Vec<i32> = v.into_iter().map(|x| x * 2).collect();

반복자 메서드

let v = vec![1, 2, 3, 4, 5];
// map
let doubled: Vec<i32> = v.iter().map(|x| x * 2).collect();
// filter
let evens: Vec<i32> = v.iter().filter(|x| *x % 2 == 0).cloned().collect();
// fold (reduce)
let sum = v.iter().fold(0, |acc, x| acc + x);
// take
let first_three: Vec<i32> = v.iter().take(3).cloned().collect();
// skip
let skip_two: Vec<i32> = v.iter().skip(2).cloned().collect();
// enumerate
for (i, value) in v.iter().enumerate() {
    println!("{}: {}", i, value);
}

반복자 어댑터(map, filter, take 등)는 지연 평가됩니다. v.iter().map(|x| x * 2);만 쓰고 collect()나 for로 소비하지 않으면 아무 일도 일어나지 않고, 컴파일러가 unused Map that must be used: iterators are lazy and do nothing unless consumed 경고를 냅니다. 이 지연 평가 덕분에 filter().map().take(3) 같은 체인은 중간 Vec를 만들지 않고 요소를 하나씩 끝까지 흘려보내며, 최적화 빌드에서는 손으로 쓴 for 루프와 거의 같은 기계어로 컴파일됩니다.

filter 클로저에서 *x를 쓰는 이유도 헷갈리는 부분입니다. v.iter()의 요소는 &i32이고, filter는 요소를 다시 빌려서 넘기므로 클로저 인자 x는 &&i32가 됩니다. |&&x| x % 2 == 0처럼 패턴으로 풀어 써도 같습니다. collect의 결과 타입은 대상 변수의 타입 표기(Vec<i32>)나 터보피시(collect::<Vec<_>>())로 알려줘야 하며, 둘 다 없으면 type annotations needed 에러가 납니다.

예제: 단어 빈도 카운터

use std::collections::HashMap;
fn count_words(text: &str) -> HashMap<String, usize> {
    let mut counts = HashMap::new();
    
    for word in text.split_whitespace() {
        let word = word.to_lowercase();
        let count = counts.entry(word).or_insert(0);
        *count += 1;
    }
    
    counts
}
fn main() {
    let text = "hello world hello rust world world";
    let counts = count_words(text);
    
    for (word, count) in &counts {
        println!("{}: {}", word, count);
    }
}

Vec, VecDeque, LinkedList의 성능 차이

컬렉션메모리인덱스 접근앞/뒤 삽입·삭제일반적인 선택
Vec연속 버퍼, 캐시 친화적O(1)뒤: O(1) 평균 / 앞: O(n)기본 선택
VecDeque링 버퍼(연속 블록)O(1)앞·뒤 O(1)큐, 양끝 작업
LinkedList노드 분산 할당O(n) 탐색알려진 노드 기준 삽입은 O(1)이지만 순회 비용이 큼Rust에서는 드묾

실무에서는 대부분 Vec 또는 VecDeque로 충분합니다. LinkedList는 노드 위치를 이미 알고 있으면 중간 삽입이 O(1)이지만, 그 위치까지 가는 순회가 O(n)이고 노드마다 따로 할당된 메모리를 포인터로 따라가느라 캐시 미스가 잦습니다. 반면 Vec의 중간 삽입은 O(n)이어도 연속된 메모리를 한 번에 옮기는 memmove라서, 요소 수가 아주 크지 않다면 실제로는 Vec 쪽이 빠른 경우가 많습니다. 또 Rust의 LinkedList는 안정 버전에서 커서 API가 없어 “알려진 노드 기준 삽입” 자체를 쓰기도 어렵습니다. 앞쪽에서 자주 pop/insert해야 하면 Vec 대신 VecDeque를 검토하세요.

use std::collections::VecDeque;
let mut q = VecDeque::new();
q.push_back(1);
q.push_front(0);  // Vec에서는 비싼 작업

HashMap과 BTreeMap 선택 기준

기준HashMapBTreeMap
키 순서없음(해시 순서)키 정렬 순으로 순회
평균 조회/삽입O(1) 수준(해시)O(log n)
키 타입Hash + EqOrd
용도 예캐시, 카운터, 일반 룩업범위 쿼리, 정렬된 키 나열, “가장 가까운 키”

HashMap: 빠른 단일 키 조회가 목적일 때. BTreeMap: range(..)로 부분 구간 순회하거나, 디버깅 시 결정적인 순서가 필요할 때 유리합니다.

use std::collections::BTreeMap;
let mut m = BTreeMap::new();
m.insert(10, "a");
m.insert(20, "b");
for (k, v) in m.range(15..=25) {
    println!("{k} -> {v}");
}

Entry API로 조회와 삽입을 한 번에

entry는 “키가 없으면 넣으며, 있으면 갱신”을 한 번의 해시 탐색으로 표현합니다. 앞서 단어 빈도 예제의 or_insert가 대표적입니다.

use std::collections::HashMap;
let mut map: HashMap<String, u32> = HashMap::new();
// 없을 때만 기본값 삽입
map.entry("key".into()).or_insert(0);
// 있으면 갱신, 없으면 새 값
map.entry("count".into())
    .and_modify(|c| *c += 1)
    .or_insert(1);
// 값을 계산해 넣기 (필요할 때만 비용 발생)
map.entry("expensive".into()).or_insert_with(|| {
    // 실제 코드에서는 여기서만 비싼 초기화를 수행
    42
});

or_insert/or_insert_with로 불필요한 할당·복사를 줄이며, and_modify로 가독성을 높일 수 있습니다.

다만 entry에는 키를 소유권째 넘겨야 한다는 비용이 있습니다. HashMap<String, u32>에서 map.entry(word.to_string())은 키가 이미 있어서 값만 올리면 되는 경우에도 매번 String을 할당합니다. 단어 빈도처럼 대부분이 기존 키 갱신인 핫 루프라면 if let Some(c) = map.get_mut(word) { *c += 1 } else { map.insert(word.to_string(), 1); }처럼 먼저 &str로 찾고, 없을 때만 할당하는 방식이 더 빠를 수 있습니다. 이 차이는 프로파일러에서 키 문자열 할당(String::from/to_string)이 상위에 보일 때 의미가 있고, 대부분의 코드에서는 entry의 간결함이 더 중요합니다.

capacity와 shrink_to_fit로 메모리 관리

  • Vec::with_capacity(n): push가 곧바로 재할당하지 않도록 미리 버퍼를 잡습니다. 크기를 대략 알 때 유효합니다. 용량이 부족할 때 현재 표준 라이브러리 구현은 용량을 두 배로 늘리므로(구체적인 성장 전략은 문서상 보장되지 않음) push의 평균 비용은 O(1)이지만, 재할당 순간에는 전체 요소를 복사합니다. 요소 수를 미리 안다면 이 복사를 없앨 수 있습니다.
  • len() vs capacity(): len은 요소 개수, capacity는 예약된 슬롯입니다. capacity - len이 곧 여유 공간입니다.
  • shrink_to_fit: 사용량이 줄어든 뒤 여분의 버퍼를 할당자에 돌려주고 싶을 때 호출합니다(할당자가 그 메모리를 OS에 즉시 반환하는지는 별개입니다). clear()는 요소만 지우고 용량은 그대로 두므로, 큰 버퍼를 재사용할 때는 오히려 clear()만 하는 편이 유리합니다. 매 호출마다 쓰기보다, 큰 맵/벡터를 비운 직후 등 구간에 쓰는 편이 낫습니다.
  • HashMap::shrink_to_fit: 해시 테이블도 마찬가지로, 요소가 많이 빠진 뒤에 고려합니다.
// 변수 선언 및 초기화
let mut v = Vec::with_capacity(1000);
for i in 0..10 {
    v.push(i);
}
v.shrink_to_fit(); // 실제 사용(10개)에 맞게 줄이기 시도

과도한 shrink_to_fit은 재할당 비용이 될 수 있으므로, 프로파일로 병목을 확인한 뒤 적용하는 것이 안전합니다.

다음 단계

같이 보면 좋은 글

자주 묻는 질문 (FAQ)

Q. HashMap에서 키가 있으면 갱신하고 없으면 삽입할 때 get과 insert를 따로 쓰면 안 되나요?

동작은 하지만 해시 탐색을 두 번 하게 되고, 빌림 규칙 때문에 get으로 얻은 참조를 쥔 채 insert를 호출하는 코드는 컴파일되지 않는 경우도 많습니다. entry API를 쓰면 한 번의 탐색으로 or_insert, and_modify를 이어 표현할 수 있습니다. 초기값 계산이 비싸다면 or_insert_with에 클로저를 넘겨 키가 없을 때만 비용이 들게 합니다.