Rust HashSet과 BTreeMap

해시셋(HashSet)은 중복 없는 값들의 모음이에요. 같은 값을 두 번 넣어도 한 번만 저장돼요. 입구의 손님 명단을 떠올려 보세요. 문지기는 이름이 명단에 있는지 없는지만 신경 쓰지, 몇 번 적혀 있는지는 신경 쓰지 않아요.

Vec과 HashMap은 이미 알고 있죠. 이 페이지에서는 그다음으로 자주 쓰게 될 컬렉션들을 소개해요. HashSet, 항상 정렬된 BTreeMap과 BTreeSet, 그리고 큐로 쓰는 VecDeque예요. 마지막에는 어떤 컬렉션을 골라야 할지 도와주는 표도 있어요.

HashSet 만들기

HashSet은 std::collections에 있어서 use 줄이 필요해요. insert 메서드는 bool을 돌려줘요. 새로운 값이면 true, 이미 있던 값이면 false예요.

use std::collections::HashSet;

fn main() {
    let mut tags = HashSet::new();

    println!("{}", tags.insert("rust"));
    println!("{}", tags.insert("web"));
    println!("{}", tags.insert("rust")); // 이미 있음

    println!("중복 없는 태그 {}개", tags.len());
}

실행 결과:

true
true
false
중복 없는 태그 2개

▶ 직접 실행해 보기

이 bool은 생각보다 쓸모가 많아요. 값을 넣는 바로 그 단계에서 “이거 전에 본 적 있나?“에 대한 답도 알려 주니까, 따로 확인할 필요가 없어요.

값 확인하고 삭제하기

contains는 값이 집합에 들어 있는지 알려 줘요. remove는 값을 빼내는데, insert처럼 실제로 무언가가 삭제됐는지를 bool로 알려 줘요.

use std::collections::HashSet;

fn main() {
    let mut online: HashSet<&str> = HashSet::from(["ana", "ben", "chen"]);

    println!("ben이 접속 중인가요? {}", online.contains("ben"));

    println!("ben 삭제: {}", online.remove("ben"));
    println!("ben 다시 삭제: {}", online.remove("ben"));

    println!("ben이 접속 중인가요? {}", online.contains("ben"));
    println!("접속 중인 사람: {}명", online.len());
}

실행 결과:

ben이 접속 중인가요? true
ben 삭제: true
ben 다시 삭제: false
ben이 접속 중인가요? false
접속 중인 사람: 2명

▶ 직접 실행해 보기

여기서 Vec 대신 집합을 쓰는 이유가 뭘까요? Vec에서 contains를 확인하면 모든 요소를 하나하나 살펴봐요. HashSet은 크기가 아무리 커져도 곧바로 답을 찾아요. 사용자가 백만 명이라면 이 차이는 어마어마해요.

주의

HashSet에는 정해진 순서가 없어요. {:?}로 출력하거나 반복문으로 순회하면, 실행할 때마다 순서가 바뀔 수 있어요. 출력할 때 순서가 일정해야 한다면, 값을 Vec에 복사해서 정렬하거나 BTreeSet(아래에서 다뤄요)을 쓰세요.

Vec에서 중복 제거하기

정말 자주 하는 작업이에요. 중복이 있는 목록에서 각 값을 한 번씩만 남기고 싶을 때죠. 원래 순서가 중요한지에 따라 좋은 방법이 두 가지 있어요.

use std::collections::HashSet;

fn main() {
    let visits = vec![3, 1, 3, 2, 1, 5, 2];

    // 방법 1: 집합으로 모은 다음, 순서를 고정하려고 정렬하기
    let unique: HashSet<i32> = visits.iter().copied().collect();
    let mut sorted: Vec<i32> = unique.into_iter().collect();
    sorted.sort();
    println!("정렬된 중복 제거: {:?}", sorted);

    // 방법 2: 각 값이 처음 나온 것만 원래 순서대로 남기기
    let mut seen = HashSet::new();
    let mut in_order = visits.clone();
    in_order.retain(|x| seen.insert(*x));
    println!("원래 순서 유지: {:?}", in_order);
}

실행 결과:

정렬된 중복 제거: [1, 2, 3, 5]
원래 순서 유지: [3, 1, 2, 5]

▶ 직접 실행해 보기

방법 2는 insert가 돌려주는 bool을 활용해요. retain은 클로저가 true를 돌려줄 때만 요소를 남기고, insert는 어떤 값을 처음 봤을 때만 true를 돌려주거든요.

집합 연산: 합집합, 교집합, 차집합

집합은 벤 다이어그램의 원처럼 조합할 수 있어요. 각 메서드는 반복자를 돌려주기 때문에, 결과를 Vec으로 모은 다음 출력하기 전에 정렬해서 매번 같은 결과가 나오게 해요.

use std::collections::HashSet;

fn main() {
    let alice: HashSet<&str> = HashSet::from(["rust", "python", "go"]);
    let bob: HashSet<&str> = HashSet::from(["go", "java", "rust"]);

    let mut both: Vec<_> = alice.intersection(&bob).collect();
    both.sort();
    println!("둘 다 아는 언어: {:?}", both);

    let mut either: Vec<_> = alice.union(&bob).collect();
    either.sort();
    println!("둘 중 한 명이라도 아는 언어: {:?}", either);

    let mut only_alice: Vec<_> = alice.difference(&bob).collect();
    only_alice.sort();
    println!("alice만 아는 언어: {:?}", only_alice);

    let mut only_one: Vec<_> = alice.symmetric_difference(&bob).collect();
    only_one.sort();
    println!("한 명만 아는 언어: {:?}", only_one);
}

실행 결과:

둘 다 아는 언어: ["go", "rust"]
둘 중 한 명이라도 아는 언어: ["go", "java", "python", "rust"]
alice만 아는 언어: ["python"]
한 명만 아는 언어: ["java", "python"]

▶ 직접 실행해 보기

difference(차집합)는 한 방향이에요. alice.difference(&bob)은 “Alice는 알지만 Bob은 모르는 것”이에요. 둘을 바꾸면 Bob 쪽 목록이 나와요. symmetric_difference(대칭 차집합)는 양쪽을 한꺼번에 본 거예요. 둘 중 한 명만 아는 모든 것이죠.

BTreeMap과 BTreeSet: 항상 정렬된 상태

BTreeMap은 HashMap과 똑같이 동작하고, BTreeSet은 HashSet과 똑같이 동작해요. 차이점은 키를 항상 정렬된 상태로 유지한다는 거예요. 순회하면 매번 키가 순서대로 나와요.

use std::collections::{BTreeMap, BTreeSet};

fn main() {
    let text = "the cat sat on the mat the end";

    let mut counts: BTreeMap<&str, u32> = BTreeMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    for (word, count) in &counts {
        println!("{word}: {count}");
    }

    let scores: BTreeSet<u32> = BTreeSet::from([72, 95, 58, 88]);
    println!("최저점: {:?}", scores.first());
    println!("최고점: {:?}", scores.last());
    println!("전체: {:?}", scores);
}

실행 결과:

cat: 1
end: 1
mat: 1
on: 1
sat: 1
the: 3
최저점: Some(58)
최고점: Some(95)
전체: {58, 72, 88, 95}

▶ 직접 실행해 보기

entry API는 HashMap 페이지에서 본 것과 같아요. 맵이 BTreeMap이라서, 따로 정렬하지 않아도 단어가 알파벳순으로 나와요.

어느 쪽을 골라야 할까요?

• 기본은 HashMap / HashSet이에요. 보통 찾기가 더 빨라요.
• 데이터를 순서대로 다뤄야 할 때는 BTreeMap / BTreeSet을 고르세요. 정렬된 보고서를 출력하거나, 가장 작은 키나 가장 큰 키를 찾거나, 키의 범위를 가져올 때요.

VecDeque: 큐

VecDeque(“벡 덱”이라고 읽어요)는 양쪽 끝 모두에서 빠르게 넣고 뺄 수 있는 목록이에요. 그래서 큐(queue)로 쓰기에 딱 좋아요. 줄 서서 기다리는 사람들처럼, 먼저 들어온 것이 먼저 나가요.

use std::collections::VecDeque;

fn main() {
    let mut line: VecDeque<&str> = VecDeque::new();
    line.push_back("ana");
    line.push_back("ben");
    line.push_back("chen");

    while let Some(person) = line.pop_front() {
        println!("{person} 차례예요. 아직 {}명이 기다리고 있어요", line.len());
    }
}

실행 결과:

ana 차례예요. 아직 2명이 기다리고 있어요
ben 차례예요. 아직 1명이 기다리고 있어요
chen 차례예요. 아직 0명이 기다리고 있어요

▶ 직접 실행해 보기

Vec::remove(0)으로도 할 수는 있어요. 하지만 그러면 나머지 요소를 전부 한 칸씩 옮겨야 해요. VecDeque의 pop_front는 그럴 필요가 없어서, 줄이 길어도 계속 빨라요.

어떤 컬렉션을 써야 할까요?

컬렉션	이럴 때 쓰세요	예시
Vec<T>	순서가 있는 목록을 위치로 접근할 때	파일의 각 줄, 점수 목록
HashMap<K, V>	키로 값을 빠르게 찾을 때	사용자 이름 → 사용자 프로필
HashSet<T>	중복 없는 값과 “여기 들어 있나?“를 빠르게 확인할 때	방문한 페이지, 금지어
BTreeMap<K, V>	키 → 값이면서 키가 정렬돼 있어야 할 때	알파벳순으로 출력하는 단어 수 세기
VecDeque<T>	양쪽 끝에서 넣고 뺄 때	작업이나 메시지의 큐

잘 모르겠다면 Vec으로 시작하세요. 같은 목록을 계속 검색하고 있다면(집합이나 맵으로), 앞에서 자주 빼고 있다면(VecDeque로) 그때 바꾸면 돼요.

자주 하는 실수

알맞은 derive 없이 직접 만든 구조체를 HashSet에 넣기. HashSet은 값을 해시하고 서로 같은지 비교할 수 있어야 해요. 여러분이 만든 구조체는 그걸 자동으로 해 주지 않아요.

use std::collections::HashSet;

struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
}

error[E0277]: the trait bound `Point: Eq` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Eq` is not implemented for `Point`

error[E0277]: the trait bound `Point: Hash` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Hash` is not implemented for `Point`

컴파일러는 “Point에 Eq 트레이트와 Hash 트레이트가 구현되어 있지 않다”고 말하고 있어요. 해결 방법은 구조체 위에 #[derive(PartialEq, Eq, Hash)] 한 줄을 추가하는 거예요. BTreeSet이라면 정렬하는 방법을 알아야 하니까 PartialOrd와 Ord도 필요해요. 각각이 무슨 뜻인지는 자주 쓰는 트레이트를 참고하세요.

use std::collections::HashSet;

#[derive(PartialEq, Eq, Hash)]
struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
    visited.insert(Point { x: 1, y: 0 });
    visited.insert(Point { x: 0, y: 0 }); // 중복이라 무시됨
    println!("방문한 칸: {}개", visited.len());
}

실행 결과:

방문한 칸: 2개

▶ 직접 실행해 보기

연습 문제

1. 처음으로 반복되는 단어

단어 목록 ["빨강", "파랑", "초록", "파랑", "빨강"]에서 두 번째로 나타나는 첫 단어를 출력해 보세요. 힌트: insert는 값이 이미 집합에 있으면 false를 돌려주고, break로 반복문을 멈출 수 있어요.

정답 보기

use std::collections::HashSet;

fn main() {
    let words = ["빨강", "파랑", "초록", "파랑", "빨강"];
    let mut seen = HashSet::new();

    for word in words {
        if !seen.insert(word) {
            println!("처음으로 반복된 단어: {word}");
            break;
        }
    }
}

실행 결과:

처음으로 반복된 단어: 파랑

▶ 직접 실행해 보기

!seen.insert(word)는 “넣기에 실패했다”, 즉 “이건 전에 본 적이 있다”라는 뜻으로 읽으면 돼요. 처음으로 반복되는 단어는 "파랑"이에요. "빨강"도 반복되지만 더 나중이에요.

2. 알파벳순으로 글자 세기

"mississippi"에서 각 글자가 몇 번 나오는지 세고, 알파벳순으로 출력해 보세요. 힌트: BTreeMap 절에서 본 entry(...).or_insert(0) 요령을 BTreeMap에 그대로 쓰고, word.chars()를 순회하세요.

정답 보기

use std::collections::BTreeMap;

fn main() {
    let word = "mississippi";
    let mut counts = BTreeMap::new();

    for letter in word.chars() {
        *counts.entry(letter).or_insert(0) += 1;
    }

    for (letter, count) in &counts {
        println!("{letter}: {count}");
    }
}

실행 결과:

i: 4
m: 1
p: 2
s: 4

▶ 직접 실행해 보기

HashMap이었다면 이 네 줄이 어떤 순서로든 나올 수 있어요. BTreeMap은 키를 정렬된 상태로 유지하니까, i, m, p, s가 매번 알파벳순으로 출력돼요.

정리

• HashSet은 중복 없는 값을 저장해요. insert와 remove는 무언가 바뀌었는지를 bool로 알려 줘요.
• 집합의 contains는 집합이 아주 커도 빨라요. Vec에서는 모든 요소를 확인해요.
• union, intersection, difference, symmetric_difference로 집합 연산을 해요. 출력하기 전에 결과를 정렬하세요.
• BTreeMap과 BTreeSet은 키를 정렬된 상태로 유지해요. 순서가 중요할 때 쓰세요.
• 큐에는 VecDeque가 제격이에요. push_back으로 줄에 서고, pop_front로 줄에서 나가요.

이해도 점검

이해도 점검

1. x가 이미 집합에 있을 때 set.insert(x)는 무엇을 돌려주나요?

true 에러 false 이전 값

2. 직접 정렬하지 않고도 단어 수를 알파벳순으로 출력하고 싶어요. 어떤 맵이 가장 잘 맞을까요?

HashMap BTreeMap Vec VecDeque

3. HashSet을 {:?}로 출력하면 실행할 때마다 결과가 다를 수 있는 이유는 무엇인가요?

HashSet에는 정해진 순서가 없어서 {:?}가 무작위라서 시간이 지나면 집합에서 값이 사라져서 디버그 모드에서만 일어나는 일이라서

4. 먼저 들어온 것이 먼저 나가는 큐에는 어떤 컬렉션이 가장 좋을까요?

HashSet BTreeSet HashMap VecDeque

점수: 0 / 4

더 알아보기

• std::collections 개요 — 표준 라이브러리 문서 (영어): 컬렉션을 고르는 방법을 각 연산의 속도와 함께 더 자세히 안내해요.
• HashSet — Rust by Example (영어): union, intersection, difference 예제를 직접 실행해 볼 수 있어요.
• HashSet — 표준 라이브러리 문서 (영어): is_subset, retain을 포함한 모든 집합 메서드를 볼 수 있어요.
• BTreeMap — 표준 라이브러리 문서 (영어): 정렬된 맵과, 키의 일부 구간을 가져오는 range를 설명해요.
• VecDeque — 표준 라이브러리 문서 (영어): push_front, pop_back, front 같은 큐 메서드를 모두 볼 수 있어요.