HashSet dan BTreeMap di Rust

HashSet adalah koleksi berisi nilai-nilai unik. Kalau kamu memasukkan nilai yang sama dua kali, nilai itu hanya disimpan sekali. Bayangkan daftar tamu di pintu masuk: penjaga pintu hanya peduli apakah namamu ada di daftar, bukan berapa kali nama itu ditulis.

Kamu sudah kenal Vec dan HashMap. Halaman ini menambahkan koleksi lain yang paling sering kamu butuhkan: HashSet, BTreeMap dan BTreeSet yang selalu terurut, serta VecDeque untuk antrean. Di bagian akhir ada tabel untuk membantumu memilih yang tepat.

Membuat HashSet

HashSet berada di std::collections, jadi kamu perlu baris use. Method insert mengembalikan bool: true kalau nilainya baru, false kalau nilainya sudah ada.

use std::collections::HashSet;

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

    println!("{}", tags.insert("rust"));
    println!("{}", tags.insert("web"));
    println!("{}", tags.insert("rust")); // sudah ada

    println!("{} tag unik", tags.len());
}

Output:

true
true
false
2 tag unik

▶ Coba sendiri

bool itu lebih berguna daripada kelihatannya. Ia menjawab pertanyaan “apakah aku pernah melihat ini sebelumnya?” sekaligus saat menambahkannya, jadi kamu tidak perlu pengecekan terpisah.

Mengecek dan menghapus nilai

contains memberi tahu apakah sebuah nilai ada di dalam set. remove mengeluarkan nilai itu dan, sama seperti insert, mengembalikan bool yang memberi tahu apakah memang ada yang dihapus.

use std::collections::HashSet;

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

    println!("apakah ben online? {}", online.contains("ben"));

    println!("ben dihapus: {}", online.remove("ben"));
    println!("ben dihapus lagi: {}", online.remove("ben"));

    println!("apakah ben online? {}", online.contains("ben"));
    println!("{} orang online", online.len());
}

Output:

apakah ben online? true
ben dihapus: true
ben dihapus lagi: false
apakah ben online? false
2 orang online

▶ Coba sendiri

Kenapa memakai set, bukan Vec, di sini? Memanggil contains pada Vec akan memeriksa setiap item satu per satu. HashSet langsung melompat ke jawabannya, sebesar apa pun ukurannya. Dengan sejuta pengguna, perbedaannya sangat besar.

Perhatian

HashSet tidak punya urutan tetap. Kalau kamu mencetaknya dengan {:?} atau melakukan perulangan padanya, urutannya bisa berubah dari satu kali run ke run berikutnya. Kalau kamu butuh urutan yang stabil untuk dicetak, salin nilainya ke Vec lalu urutkan, atau pakai BTreeSet (dibahas di bawah).

Menghapus duplikat dari Vec

Ini tugas yang sangat umum: kamu punya daftar dengan nilai berulang dan ingin setiap nilai muncul sekali saja. Ada dua cara yang bagus, tergantung apakah kamu peduli dengan urutan aslinya.

use std::collections::HashSet;

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

    // Cara 1: kumpulkan ke dalam set, lalu urutkan agar urutannya stabil
    let unique: HashSet<i32> = visits.iter().copied().collect();
    let mut sorted: Vec<i32> = unique.into_iter().collect();
    sorted.sort();
    println!("unik terurut: {:?}", sorted);

    // Cara 2: simpan kemunculan pertama setiap nilai, sesuai urutan asli
    let mut seen = HashSet::new();
    let mut in_order = visits.clone();
    in_order.retain(|x| seen.insert(*x));
    println!("urutan asli:  {:?}", in_order);
}

Output:

unik terurut: [1, 2, 3, 5]
urutan asli:  [3, 1, 2, 5]

▶ Coba sendiri

Cara 2 memanfaatkan bool dari insert. retain hanya menyimpan item ketika closure-nya mengembalikan true, dan insert hanya mengembalikan true saat pertama kali melihat sebuah nilai.

Operasi himpunan: union, intersection, difference

Set bisa digabungkan seperti lingkaran-lingkaran di diagram Venn. Setiap method mengembalikan iterator, jadi kita kumpulkan hasilnya ke dalam Vec lalu urutkan sebelum dicetak, supaya output-nya selalu sama.

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!("dikuasai keduanya:   {:?}", both);

    let mut either: Vec<_> = alice.union(&bob).collect();
    either.sort();
    println!("dikuasai salah satu: {:?}", either);

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

    let mut only_one: Vec<_> = alice.symmetric_difference(&bob).collect();
    only_one.sort();
    println!("hanya satu orang:    {:?}", only_one);
}

Output:

dikuasai keduanya:   ["go", "rust"]
dikuasai salah satu: ["go", "java", "python", "rust"]
hanya alice:         ["python"]
hanya satu orang:    ["java", "python"]

▶ Coba sendiri

difference hanya berlaku satu arah: alice.difference(&bob) artinya “bahasa yang dikuasai Alice tetapi tidak dikuasai Bob”. Kalau urutannya ditukar, kamu mendapat daftar milik Bob. symmetric_difference mencakup kedua sisi sekaligus: semua yang hanya dikuasai oleh salah satu dari mereka.

BTreeMap dan BTreeSet: selalu terurut

BTreeMap bekerja persis seperti HashMap, dan BTreeSet bekerja persis seperti HashSet. Bedanya: keduanya menyimpan key dalam keadaan terurut. Saat kamu melakukan perulangan padanya, key-nya selalu keluar berurutan.

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

fn main() {
    let text = "ini budi ini ibu budi ini bapak budi";

    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!("terendah: {:?}", scores.first());
    println!("tertinggi: {:?}", scores.last());
    println!("semua: {:?}", scores);
}

Output:

bapak: 1
budi: 3
ibu: 1
ini: 3
terendah: Some(58)
tertinggi: Some(95)
semua: {58, 72, 88, 95}

▶ Coba sendiri

API entry di sini sama dengan yang kamu temui di halaman HashMap. Karena map-nya adalah BTreeMap, kata-katanya keluar dalam urutan abjad tanpa langkah pengurutan tambahan.

Mana yang sebaiknya kamu pilih?

• Pilih HashMap / HashSet sebagai default. Pencariannya biasanya lebih cepat.
• Pilih BTreeMap / BTreeSet kalau kamu butuh datanya berurutan: mencetak laporan yang terurut, mencari key terkecil atau terbesar, atau mengambil rentang key tertentu.

VecDeque: antrean

VecDeque (dibaca “vec dek”) adalah daftar yang bisa kamu tambah dan kurangi dengan cepat di kedua ujungnya. Karena itu, VecDeque pilihan alami untuk antrean: yang pertama masuk, pertama keluar, seperti orang yang antre.

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!("melayani {person}, {} masih menunggu", line.len());
    }
}

Output:

melayani ana, 2 masih menunggu
melayani ben, 1 masih menunggu
melayani chen, 0 masih menunggu

▶ Coba sendiri

Kamu bisa saja memakai Vec::remove(0) untuk ini, tetapi cara itu menggeser semua item lain satu posisi. pop_front pada VecDeque tidak melakukannya, jadi tetap cepat walaupun antreannya panjang.

Koleksi mana yang sebaiknya kupakai?

Koleksi	Pakai saat kamu butuh…	Contoh
Vec<T>	Daftar berurutan yang diakses berdasarkan posisi	Baris-baris sebuah file, daftar skor
HashMap<K, V>	Pencarian nilai yang cepat berdasarkan key	Username → profil pengguna
HashSet<T>	Nilai unik dan pengecekan cepat “apakah ini ada di sini?”	Halaman yang sudah dikunjungi, kata terlarang
BTreeMap<K, V>	Key → value, dengan key yang selalu terurut	Jumlah kata yang dicetak urut abjad
VecDeque<T>	Menambah/menghapus di kedua ujung	Antrean tugas atau pesan

Kalau ragu, mulai saja dengan Vec. Ganti kalau kamu sadar sering mencarinya berulang-ulang (pakai set atau map) atau sering menghapus dari depan (pakai VecDeque).

Kesalahan umum

Memasukkan struct buatanmu sendiri ke HashSet tanpa derive yang tepat. HashSet perlu meng-hash nilainya dan membandingkan apakah dua nilai sama. Struct buatanmu tidak bisa melakukan itu secara otomatis:

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`

Compiler memberi tahu bahwa Point belum mengimplementasikan trait Eq dan Hash. Solusinya cukup satu baris di atas struct: #[derive(PartialEq, Eq, Hash)]. Untuk BTreeSet, kamu juga perlu PartialOrd dan Ord, supaya ia tahu cara mengurutkannya. Lihat Trait yang sering dipakai untuk arti masing-masing.

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 }); // duplikat, diabaikan
    println!("{} kotak sudah dikunjungi", visited.len());
}

Output:

2 kotak sudah dikunjungi

▶ Coba sendiri

Latihan

1. Pengulangan pertama

Dari kata-kata ["merah", "biru", "hijau", "biru", "merah"], cetak kata pertama yang muncul untuk kedua kalinya. Petunjuk: insert mengembalikan false kalau nilainya sudah ada di set, dan break menghentikan perulangan.

Lihat solusi

use std::collections::HashSet;

fn main() {
    let words = ["merah", "biru", "hijau", "biru", "merah"];
    let mut seen = HashSet::new();

    for word in words {
        if !seen.insert(word) {
            println!("Pengulangan pertama: {word}");
            break;
        }
    }
}

Output:

Pengulangan pertama: biru

▶ Coba sendiri

!seen.insert(word) bisa dibaca “insert-nya gagal”, artinya “aku sudah pernah melihat kata ini”. "biru" adalah kata pertama yang berulang. "merah" juga berulang, tetapi belakangan.

2. Huruf secara berurutan

Hitung berapa kali setiap huruf muncul di "mississippi", lalu cetak jumlahnya dalam urutan abjad. Petunjuk: pakai BTreeMap dengan trik entry(...).or_insert(0) yang sama seperti di bagian BTreeMap, dan lakukan perulangan pada word.chars().

Lihat solusi

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

Output:

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

▶ Coba sendiri

Dengan HashMap, keempat baris ini bisa keluar dalam urutan apa saja. BTreeMap menjaga key-nya tetap terurut, jadi i, m, p, s selalu tercetak sesuai abjad.

Ringkasan

• HashSet menyimpan nilai unik. insert dan remove mengembalikan bool yang memberi tahu apakah ada yang berubah.
• contains pada set itu cepat, bahkan untuk set yang sangat besar. Pada Vec, ia memeriksa setiap item.
• union, intersection, difference, dan symmetric_difference menjalankan operasi himpunan. Urutkan hasilnya sebelum dicetak.
• BTreeMap dan BTreeSet menjaga key tetap terurut; pakai keduanya kalau urutan itu penting.
• VecDeque adalah pilihan utama untuk antrean: push_back untuk masuk antrean, pop_front untuk keluar.

Kuis singkat

Kuis singkat

1. Apa yang dikembalikan set.insert(x) kalau x sudah ada di set?

true Sebuah error false Nilai yang lama

2. Kamu ingin mencetak jumlah kata dalam urutan abjad tanpa mengurutkannya sendiri. Map mana yang paling cocok?

HashMap BTreeMap Vec VecDeque

3. Kenapa mencetak HashSet dengan {:?} bisa memberi output berbeda di setiap run?

HashSet tidak punya urutan tetap {:?} itu acak Set kehilangan nilai seiring waktu Itu hanya terjadi di mode debug

4. Koleksi mana yang paling cocok untuk antrean first-in, first-out (pertama masuk, pertama keluar)?

HashSet BTreeSet HashMap VecDeque

Skor: 0 / 4

Bacaan lebih lanjut

• Ikhtisar std::collections — dokumentasi standard library (bahasa Inggris): panduan lebih panjang untuk memilih koleksi, lengkap dengan kecepatan setiap operasinya.
• HashSet — Rust by Example (bahasa Inggris): contoh yang bisa dijalankan untuk union, intersection, dan difference.
• HashSet — dokumentasi standard library (bahasa Inggris): semua method set, termasuk is_subset dan retain.
• BTreeMap — dokumentasi standard library (bahasa Inggris): map yang terurut, termasuk range untuk mengambil sebagian rentang key.
• VecDeque — dokumentasi standard library (bahasa Inggris): semua method antrean, seperti push_front, pop_back, dan front.