HashSet và BTreeMap trong Rust

HashSet là một collection gồm các giá trị không trùng lặp. Đưa cùng một giá trị vào hai lần thì nó chỉ được lưu một lần. Hãy nghĩ đến danh sách khách mời ở cửa: anh bảo vệ chỉ quan tâm tên bạn có trong danh sách hay không, chứ không quan tâm nó được ghi bao nhiêu lần.

Bạn đã biết Vec và HashMap. Bài này giới thiệu thêm những collection khác mà bạn sẽ dùng thường xuyên nhất: HashSet, BTreeMap và BTreeSet luôn được sắp xếp, và VecDeque cho hàng đợi. Ở cuối bài có một bảng giúp bạn chọn đúng loại.

Tạo một HashSet

HashSet nằm trong std::collections, nên bạn cần một dòng use. Phương thức insert trả về một bool: true nếu giá trị là mới, false nếu nó đã có sẵn.

use std::collections::HashSet;

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

    println!("{}", tags.insert("rust"));
    println!("{}", tags.insert("web"));
    println!("{}", tags.insert("rust")); // đã có sẵn

    println!("{} thẻ không trùng nhau", tags.len());
}

Kết quả:

true
true
false
2 thẻ không trùng nhau

▶ Tự chạy thử

Cái bool đó hữu ích hơn vẻ ngoài của nó. Nó trả lời câu hỏi “mình đã gặp cái này chưa?” ngay trong bước thêm vào, nên bạn không cần một phép kiểm tra riêng.

Kiểm tra và xóa giá trị

contains cho bạn biết một giá trị có trong tập hợp hay không. remove lấy nó ra và, giống insert, trả về một bool cho biết có thứ gì thật sự bị xóa không.

use std::collections::HashSet;

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

    println!("ben có online không? {}", online.contains("ben"));

    println!("đã xóa ben: {}", online.remove("ben"));
    println!("xóa ben lần nữa: {}", online.remove("ben"));

    println!("ben có online không? {}", online.contains("ben"));
    println!("{} người đang online", online.len());
}

Kết quả:

ben có online không? true
đã xóa ben: true
xóa ben lần nữa: false
ben có online không? false
2 người đang online

▶ Tự chạy thử

Vì sao dùng tập hợp thay vì Vec ở đây? Gọi contains trên một Vec sẽ xem xét từng phần tử, lần lượt từng cái. Một HashSet nhảy thẳng tới câu trả lời, dù nó lớn đến đâu. Với một triệu người dùng, khác biệt đó là rất lớn.

Chú ý

HashSet không có thứ tự cố định. Nếu bạn in nó bằng {:?} hoặc duyệt qua nó, thứ tự có thể thay đổi giữa các lần chạy. Khi cần một thứ tự ổn định để in, hãy chép các giá trị sang một Vec rồi sắp xếp, hoặc dùng BTreeSet (giới thiệu bên dưới).

Loại bỏ phần tử trùng lặp khỏi Vec

Một việc rất hay gặp: bạn có một danh sách có phần tử lặp lại và muốn mỗi giá trị chỉ xuất hiện một lần. Có hai cách tốt, tùy vào việc bạn có quan tâm đến thứ tự ban đầu hay không.

use std::collections::HashSet;

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

    // Cách 1: gom vào một tập hợp, rồi sắp xếp để có thứ tự ổn định
    let unique: HashSet<i32> = visits.iter().copied().collect();
    let mut sorted: Vec<i32> = unique.into_iter().collect();
    sorted.sort();
    println!("đã sắp xếp: {:?}", sorted);

    // Cách 2: giữ lần xuất hiện đầu tiên của mỗi giá trị, theo thứ tự ban đầu
    let mut seen = HashSet::new();
    let mut in_order = visits.clone();
    in_order.retain(|x| seen.insert(*x));
    println!("thứ tự gốc: {:?}", in_order);
}

Kết quả:

đã sắp xếp: [1, 2, 3, 5]
thứ tự gốc: [3, 1, 2, 5]

▶ Tự chạy thử

Cách 2 dùng cái bool mà insert trả về. retain chỉ giữ một phần tử khi closure trả về true, và insert chỉ trả về true ở lần đầu tiên nó gặp một giá trị.

Phép toán tập hợp: hợp, giao, hiệu

Các tập hợp có thể kết hợp với nhau như những vòng tròn trong biểu đồ Venn. Mỗi phương thức trả về một iterator, nên ta gom kết quả vào một Vec và sắp xếp trước khi in để lần nào cũng cho ra cùng một kết quả.

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!("cả hai biết:       {:?}", both);

    let mut either: Vec<_> = alice.union(&bob).collect();
    either.sort();
    println!("ít nhất một người: {:?}", either);

    let mut only_alice: Vec<_> = alice.difference(&bob).collect();
    only_alice.sort();
    println!("chỉ alice:         {:?}", only_alice);

    let mut only_one: Vec<_> = alice.symmetric_difference(&bob).collect();
    only_one.sort();
    println!("chỉ một người:     {:?}", only_one);
}

Kết quả:

cả hai biết:       ["go", "rust"]
ít nhất một người: ["go", "java", "python", "rust"]
chỉ alice:         ["python"]
chỉ một người:     ["java", "python"]

▶ Tự chạy thử

difference (hiệu) chỉ đi một chiều: alice.difference(&bob) là “những gì Alice biết mà Bob không biết”. Đảo hai bên thì bạn nhận được danh sách của Bob. symmetric_difference (hiệu đối xứng) là cả hai phía cùng lúc: mọi thứ mà chỉ một trong hai người biết. union là phép hợp, còn intersection là phép giao.

BTreeMap và BTreeSet: luôn được sắp xếp

BTreeMap hoạt động giống hệt HashMap, và BTreeSet hoạt động giống hệt HashSet. Điểm khác: chúng giữ các khóa đã được sắp xếp. Khi duyệt qua chúng, bạn luôn nhận các khóa theo thứ tự.

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!("thấp nhất: {:?}", scores.first());
    println!("cao nhất: {:?}", scores.last());
    println!("tất cả: {:?}", scores);
}

Kết quả:

cat: 1
end: 1
mat: 1
on: 1
sat: 1
the: 3
thấp nhất: Some(58)
cao nhất: Some(95)
tất cả: {58, 72, 88, 95}

▶ Tự chạy thử

Câu ví dụ được giữ tiếng Anh vì BTreeMap sắp xếp khóa theo từng byte, nên các chữ tiếng Việt có dấu sẽ không ra đúng thứ tự bảng chữ cái tiếng Việt. API entry chính là cái bạn đã gặp trong bài HashMap. Vì map là BTreeMap, các từ được in theo thứ tự bảng chữ cái mà không cần thêm bước sắp xếp nào.

Bạn nên chọn loại nào?

• Mặc định hãy chọn HashMap / HashSet. Tra cứu thường nhanh hơn.
• Chọn BTreeMap / BTreeSet khi bạn cần dữ liệu theo thứ tự: in một báo cáo đã sắp xếp, tìm khóa nhỏ nhất hoặc lớn nhất, hoặc lấy một khoảng khóa.

VecDeque: một hàng đợi

VecDeque (đọc là “vec deck”) là một danh sách mà bạn thêm vào và lấy ra nhanh ở cả hai đầu. Điều đó khiến nó là lựa chọn tự nhiên cho hàng đợi (queue): vào trước, ra trước, giống như mọi người xếp hàng.

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!("đang phục vụ {person}, còn {} người chờ", line.len());
    }
}

Kết quả:

đang phục vụ ana, còn 2 người chờ
đang phục vụ ben, còn 1 người chờ
đang phục vụ chen, còn 0 người chờ

▶ Tự chạy thử

Bạn có thể dùng Vec::remove(0) cho việc này, nhưng nó phải dịch mọi phần tử còn lại sang một vị trí. pop_front trên VecDeque thì không, nên nó vẫn nhanh dù hàng có dài đến đâu.

Nên dùng collection nào?

Collection	Dùng khi bạn cần…	Ví dụ
Vec<T>	Một danh sách có thứ tự, truy cập theo vị trí	Các dòng của một file, danh sách điểm số
HashMap<K, V>	Tra cứu nhanh một giá trị theo khóa	Tên người dùng → hồ sơ người dùng
HashSet<T>	Giá trị không trùng lặp và kiểm tra nhanh “có trong này không?”	Các trang đã ghé, các từ bị cấm
BTreeMap<K, V>	Khóa → giá trị, với khóa luôn được sắp xếp	Bảng đếm từ in theo thứ tự bảng chữ cái
VecDeque<T>	Thêm/bớt ở cả hai đầu	Hàng đợi công việc hoặc tin nhắn

Khi còn phân vân, hãy bắt đầu với Vec. Chuyển sang loại khác khi bạn thấy mình phải tìm kiếm trong nó hết lần này đến lần khác (dùng set hoặc map) hoặc phải xóa ở đầu danh sách rất nhiều (dùng VecDeque).

Lỗi thường gặp

Đưa struct của bạn vào HashSet mà không derive đúng trait. HashSet cần băm (hash) các giá trị và so sánh chúng bằng nhau. Struct của bạn không tự động làm được điều đó:

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`

Rustc báo rằng Point chưa triển khai trait Eq và Hash. Cách sửa chỉ là một dòng phía trên struct: #[derive(PartialEq, Eq, Hash)]. Với BTreeSet bạn còn cần thêm PartialOrd và Ord, để nó biết cách sắp xếp. Xem bài Các trait thông dụng để biết mỗi trait này có nghĩa là gì.

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 }); // trùng, bị bỏ qua
    println!("đã ghé {} ô", visited.len());
}

Kết quả:

đã ghé 2 ô

▶ Tự chạy thử

Đi xa hơn

Cần một hàng đợi (vào trước, ra trước) hay “luôn đưa tôi phần tử lớn nhất tiếp theo”? Bài VecDeque và BinaryHeap giới thiệu hai collection được tạo ra cho đúng việc đó.

Luyện tập

1. Từ lặp lại đầu tiên

Cho các từ ["đỏ", "xanh", "vàng", "xanh", "đỏ"], hãy in ra từ đầu tiên xuất hiện lần thứ hai. Gợi ý: insert trả về false khi giá trị đã có trong tập hợp, và break dừng vòng lặp.

Xem lời giải

use std::collections::HashSet;

fn main() {
    let words = ["đỏ", "xanh", "vàng", "xanh", "đỏ"];
    let mut seen = HashSet::new();

    for word in words {
        if !seen.insert(word) {
            println!("Từ lặp lại đầu tiên: {word}");
            break;
        }
    }
}

Kết quả:

Từ lặp lại đầu tiên: xanh

▶ Tự chạy thử

!seen.insert(word) được đọc là “thêm vào thất bại”, nghĩa là “mình đã gặp từ này rồi”. "xanh" là từ đầu tiên bị lặp lại. "đỏ" cũng lặp lại, nhưng muộn hơn.

2. Các chữ cái theo thứ tự

Đếm xem mỗi chữ cái xuất hiện bao nhiêu lần trong "mississippi", và in kết quả theo thứ tự bảng chữ cái. Gợi ý: dùng BTreeMap với cùng mẹo entry(...).or_insert(0) trong phần BTreeMap, và duyệt qua word.chars().

Xem lời giải

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}");
    }
}

Kết quả:

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

▶ Tự chạy thử

Với HashMap, bốn dòng này có thể ra theo bất kỳ thứ tự nào. BTreeMap giữ các khóa đã sắp xếp, nên i, m, p, s lần nào cũng được in theo thứ tự bảng chữ cái.

Tóm tắt

• HashSet lưu các giá trị không trùng lặp. insert và remove trả về một bool cho biết có gì thay đổi không.
• contains trên tập hợp rất nhanh, kể cả với tập hợp khổng lồ. Trên Vec thì nó kiểm tra từng phần tử.
• union, intersection, difference và symmetric_difference thực hiện phép toán tập hợp. Hãy sắp xếp kết quả trước khi in.
• BTreeMap và BTreeSet giữ khóa luôn được sắp xếp; dùng chúng khi thứ tự quan trọng.
• VecDeque là hàng đợi nên dùng: push_back để vào hàng, pop_front để rời hàng.

Kiểm tra nhanh

Kiểm tra nhanh

1. set.insert(x) trả về gì nếu x đã có trong tập hợp?

true Một lỗi false Giá trị cũ

2. Bạn muốn in bảng đếm từ theo thứ tự bảng chữ cái mà không phải tự sắp xếp. Map nào phù hợp nhất?

HashMap BTreeMap Vec VecDeque

3. Vì sao in một HashSet bằng {:?} có thể cho kết quả khác nhau ở mỗi lần chạy?

HashSet không có thứ tự cố định {:?} là ngẫu nhiên Tập hợp mất dần giá trị theo thời gian Chỉ xảy ra ở chế độ debug

4. Collection nào tốt nhất cho một hàng đợi vào trước, ra trước?

HashSet BTreeSet HashMap VecDeque

Điểm: 0 / 4

Đọc thêm

• Tổng quan std::collections — tài liệu thư viện chuẩn (tiếng Anh): hướng dẫn chi tiết hơn về cách chọn collection, kèm tốc độ của từng thao tác.
• HashSet — Rust by Example (tiếng Anh): một ví dụ chạy được về union, intersection và difference.
• HashSet — tài liệu thư viện chuẩn (tiếng Anh): mọi phương thức của tập hợp, gồm cả is_subset và retain.
• BTreeMap — tài liệu thư viện chuẩn (tiếng Anh): map đã sắp xếp, gồm cả range để lấy một đoạn khóa.
• VecDeque — tài liệu thư viện chuẩn (tiếng Anh): mọi phương thức của hàng đợi, như push_front, pop_back và front.