KAL
Menu

HashMap

Pemetaan kunci-nilai, API Entry, dan kepemilikan kunci maupun nilai.

Daftar isi

Topik ini membahas HashMap<K, V>, yaitu koleksi Rust yang memetakan kunci ke nilai tanpa menelusuri isi satu per satu. Pembahasan mencakup pengisian dan pembacaan peta, perpindahan kepemilikan kunci maupun nilai ke dalam peta, pembaruan nilai dengan API Entry, serta syarat Eq dan Hash yang harus dipenuhi kunci, termasuk untuk kunci berupa struct buatan sendiri. Setelah membaca topik ini, data berpasangan seperti daftar nama dan nilai dapat disimpan dalam bentuk peta, dan kesalahan kepemilikan yang lazim saat memasukkan kunci dapat dihindari sejak kompilasi.

Membuat dan mengisi HashMap#

HashMap<K, V> menyimpan pasangan kunci dan nilai, dan satu kunci hanya menampung satu nilai terkini, yaitu nilai yang dimasukkan terakhir kali. Peta baru dibuat dengan HashMap::new, diisi dengan insert, dan dibaca dengan get. Berbeda dari pengindeksan vektor, get pada peta mengembalikan Option<&V> karena kunci yang dicari memang dapat tidak ada.

Pengindeksan dengan tanda kurung siku juga tersedia pada peta, dan perilakunya panik apabila kuncinya hilang. Pemanggilan insert dengan kunci yang sudah ada menimpa nilai lama, sedangkan remove mengeluarkan pasangan kunci-nilai dari peta. Program berikut menyimpan nilai ujian sekelompok peserta.

rust nilai-ujian.rs 
use std::collections::HashMap;

fn main() {
    let mut nilai = HashMap::new();

    nilai.insert(String::from("Ali"), 78);
    nilai.insert(String::from("Budi"), 85);
    nilai.insert(String::from("Citra"), 92);
    println!("jumlah peserta : {}", nilai.len());

    match nilai.get("Budi") {
        Some(n) => println!("nilai Budi     : {n}"),
        None => println!("nilai Budi     : tidak ada"),
    }

    if let Some(n) = nilai.get("Dewi") {
        println!("nilai Dewi     : {n}");
    } else {
        println!("nilai Dewi     : tidak ada");
    }

    nilai.insert(String::from("Ali"), 81);
    println!("nilai Ali      : {}", nilai["Ali"]);

    nilai.remove("Citra");
    println!("setelah remove : {} peserta", nilai.len());
}
text Keluaran 
jumlah peserta : 3
nilai Budi     : 85
nilai Dewi     : tidak ada
nilai Ali      : 81
setelah remove : 2 peserta

Pemanggilan get("Budi") menghasilkan Some(85) yang dibongkar oleh match, sedangkan get("Dewi") menghasilkan None karena Dewi tidak pernah dimasukkan. insert kedua dengan kunci Ali menimpa nilai 78 menjadi 81, dan pengindeksan nilai["Ali"] aman dipakai setelah penimpaan itu karena keberadaan kuncinya sudah pasti. Pengindeksan peta yang menemui kunci hilang menghentikan program dengan panic, sama seperti pengindeksan vektor pada indeks di luar batas, sehingga get tetap menjadi pilihan untuk kunci yang asalnya tidak pasti. Pemanggilan remove("Citra") kemudian menurunkan jumlah peserta menjadi dua.

Kepemilikan kunci dan nilai berpindah#

insert memindahkan kepemilikan kunci maupun nilai bertipe non-Copy ke dalam peta. Setelah insert(nama, 78) dengan nama bertipe String, variabel nama tidak lagi dapat dipakai karena isinya kini dimiliki peta. Tipe yang mengimplementasikan Copy, seperti bilangan bulat pada contoh tersebut, hanya disalin sehingga variabel aslinya tetap hidup. Perpindahan ini menjadikan peta pemilik sejati datanya, sehingga umur isinya tidak lagi bergantung pada variabel yang memasukkannya. Compiler menolak pemakaian variabel yang sudah dipindahkan, seperti pada program kecil berikut.

bash 
export PATH="$HOME/.cargo/bin:$PATH"
# buat program yang masih memakai kunci setelah kunci itu dipindahkan ke peta
printf 'use std::collections::HashMap;\n\nfn main() {\n    let nama = String::from("Ali");\n    let mut peta = HashMap::new();\n    peta.insert(nama, 78);\n    println!("panjang nama: {}", nama.len());\n}\n' > salah-milik.rs
# kompilasi ditolak karena kepemilikan kunci sudah berpindah ke peta
rustc --edition=2021 salah-milik.rs 2>&1 | sed -n '1,15p'
text Keluaran 
error[E0382]: borrow of moved value: `nama`
 --> salah-milik.rs:7:34
  |
4 |     let nama = String::from("Ali");
  |         ---- move occurs because `nama` has type `String`, which does not implement the `Copy` trait
5 |     let mut peta = HashMap::new();
6 |     peta.insert(nama, 78);
  |                 ---- value moved here
7 |     println!("panjang nama: {}", nama.len());
  |                                  ^^^^ value borrowed here after move
  |
help: consider cloning the value if the performance cost is acceptable
  |
6 |     peta.insert(nama.clone(), 78);
  |                     ++++++++

Error E0382 menandai baris pemindahan dan baris pemakaian ulangnya, lalu menawarkan clone apabila variabel asli memang masih diperlukan di luar peta. Salinan melalui nama.clone() memberi peta salinan tersendiri sehingga variabel nama tetap hidup, sedangkan pemakaian tanpa clone tepat ketika variabel tersebut memang tidak dipakai lagi setelah dimasukkan. Kedua pilihan itu adalah pertukaran antara biaya penyalinan dan keleluasaan pemakaian, dan kebutuhan nyata pada program biasanya menentukan salah satunya dengan jelas.

Memperbarui nilai dengan API Entry#

Kasus yang sering muncul adalah memperbarui nilai pada kunci yang belum tentu ada, misalnya ketika menghitung frekuensi kata. Solusi yang memeriksa contains_key terlebih dahulu lalu memasukkan atau membaca melakukan pencarian dua kali pada kunci yang sama. API Entry menyatukan pencarian dan pembaruan dalam satu kunjungan: entry(kunci) mengembalikan enum Entry yang merepresentasikan keadaan kunci, kemudian or_default() mengisi nilai bawaan apabila kuncinya belum ada dan mengembalikan referensi mutable ke nilai yang ada maupun yang baru saja diisi. Varian or_insert(nilai) bekerja dengan cara yang sama dengan nilai awal yang ditentukan sendiri. Penghitung kata berikut memakai pola tersebut.

rust hitung-kata.rs 
use std::collections::HashMap;

fn main() {
    let laporan = "suhu naik pagi ini suhu turun sore ini";
    let mut hitung: HashMap<&str, i32> = HashMap::new();

    for kata in laporan.split_whitespace() {
        *hitung.entry(kata).or_default() += 1;
    }

    println!("kata unik : {}", hitung.len());

    let mut hasil: Vec<(&str, i32)> = hitung.iter().map(|(k, v)| (*k, *v)).collect();
    hasil.sort();
    for (kata, jumlah) in &hasil {
        println!("{kata} : {jumlah}");
    }
}
text Keluaran 
kata unik : 6
ini : 2
naik : 1
pagi : 1
sore : 1
suhu : 2
turun : 1

Setiap kata diambil dengan split_whitespace, kemudian entry(kata).or_default() menempatkan angka nol pada kata yang baru pertama kali ditemui, dan referensi nilainya dinaikkan satu melalui operator +=. Kata suhu dan ini yang muncul dua kali berakhir bernilai dua tanpa cabang khusus. Sebelum mencetak, isi peta dikumpulkan ke dalam vektor dan diurutkan terlebih dahulu, karena urutan iterasi HashMap memang tidak ditentukan. Pengurutan hasil menjamin keluaran yang sama pada setiap jalankan program.

Kunci struct dengan Eq dan Hash#

Peta hash menempatkan pasangan berdasarkan hasil hash kuncinya, sehingga kunci wajib mengimplementasikan trait Eq dan Hash. Tipe bawaan seperti String, &str, dan seluruh bilangan bulat sudah memenuhi kedua syarat itu, tetapi struct buatan sendiri belum memilikinya. Atribut #[derive(PartialEq, Eq, Hash)] menambahkan kedua implementasi secara otomatis dengan semantik perbandingan field demi field, dan Debug ikut ditambahkan agar kunci dapat dicetak pada keluaran. Program berikut memakai struct koordinat sebagai kunci catatan sensor.

rust kunci-struct.rs 
use std::collections::HashMap;

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

fn main() {
    let mut catatan = HashMap::new();
    catatan.insert(Koordinat { x: 3, y: 4 }, "sensor suhu");
    catatan.insert(Koordinat { x: 10, y: 2 }, "sensor cahaya");

    let dicari = Koordinat { x: 10, y: 2 };
    match catatan.get(&dicari) {
        Some(keterangan) => println!("{:?} => {}", dicari, keterangan),
        None => println!("{:?} => tidak ada", dicari),
    }
}
text Keluaran 
Koordinat { x: 10, y: 2 } => sensor cahaya

Nilai Koordinat { x: 10, y: 2 } ditemukan karena PartialEq membandingkan isi field-nya, bukan alamat memorinya, sehingga dua nilai yang dibuat terpisah tetap dianggap kunci yang sama. Hash menghasilkan hash yang sama untuk nilai yang sama pula, dan konsistensi antara keduanya adalah syarat yang dijaga derive. Tanpa derive tersebut, kompilasi gagal dengan error yang menyebut trait yang kurang, seperti berikut.

bash 
export PATH="$HOME/.cargo/bin:$PATH"
# buat program yang memakai struct sebagai kunci tanpa derive Eq dan Hash
printf 'use std::collections::HashMap;\n\nstruct Poin {\n    x: i32,\n    y: i32,\n}\n\nfn main() {\n    let mut peta = HashMap::new();\n    peta.insert(Poin { x: 1, y: 2 }, "sensor");\n    println!("{}", peta.len());\n}\n' > salah-trait.rs
# kompilasi ditolak karena kunci HashMap wajib mengimplementasikan Eq dan Hash
rustc --edition=2021 salah-trait.rs 2>&1 | sed -n '1,14p'
text Keluaran 
error[E0277]: the trait bound `Poin: Eq` is not satisfied
  --> salah-trait.rs:10:10
   |
10 |     peta.insert(Poin { x: 1, y: 2 }, "sensor");
   |          ^^^^^^ ------------------- `Poin` doesn't satisfy the trait bound
   |          |
   |          the trait `Eq` is not implemented for `Poin`
   |
note: required by a bound in `HashMap::<K, V, S, A>::insert`
  --> /rustc/58cf8f9c35b355199727627d07ae34a4e2846d67/library/std/src/collections/hash/map.rs:1332:4
help: consider annotating `Poin` with `#[derive(Eq)]`
   |
 3 + #[derive(Eq)]
 4 | struct Poin {

Error pertama menyebut Eq tidak diimplementasikan untuk Poin disertai saran menambahkan derive, dan error kedua yang serupa menyebut Hash setelahnya. Perbaikannya satu baris pada deklarasi struct, yaitu #[derive(PartialEq, Eq, Hash)], sebagaimana dipakai program kunci-struct.rs di atas. Kesalahan ini murni urusan kompilasi, sehingga tidak ada cara memasukkan kunci tanpa Eq dan Hash secara tidak sengaja.

Kesalahan umum#

Menganggap insert tidak menimpa. Pemanggilan insert dengan kunci yang sudah ada langsung mengganti nilai lamanya, dan nilai lama itu dikembalikan sebagai Option<V> yang sering diabaikan. Deteksi kunci ganda karenanya memeriksa nilai kembalian tersebut, bukan memanggil contains_key lebih dahulu yang menambah satu pencarian. Pola entry dengan or_insert menjadi pilihan ketika nilai lama justru ingin dipertahankan.

Mengiterasi HashMap untuk keluaran berurutan. Urutan iterasi peta hash tidak ditentukan dan berubah antar-jalankan, sehingga keluaran yang dicetak langsung dari iter() tidak stabil. Kumpulkan hasilnya ke vektor lalu urutkan, atau gunakan BTreeMap yang iterasinya selalu mengikuti urutan kunci.

Ringkasan#

  • HashMap<K, V> memetakan kunci ke nilai: insert mengisi dan menimpa, get mengembalikan Option<&V>, remove mengeluarkan, dan iter menghasilkan pasangan (&K, &V).
  • Kunci dan nilai bertipe non-Copy berpindah kepemilikannya ke dalam peta, sehingga variabel aslinya tidak dapat dipakai lagi.
  • API Entry dengan or_default() atau or_insert() memperbarui nilai dalam satu kunjungan, termasuk untuk kunci yang belum ada.
  • Kunci wajib mengimplementasikan Eq dan Hash, dan struct kunci mendapatkannya melalui #[derive(PartialEq, Eq, Hash)].
  • Urutan iterasi HashMap tidak ditentukan, sehingga keluaran berurutan memerlukan pengurutan hasil atau BTreeMap.

Referensi#