Unordered container

unordered_map dan unordered_set, hashing, dan fungsi hash kustom.

Daftar isi

Topik ini membahas unordered container pada pustaka standar, yaitu std::unordered_map dan std::unordered_set, yang mengelola elemen berdasarkan nilai hash kuncinya. Pembahasan mencakup cara kerja hashing beserta istilah bucket dan rehash, contoh penggunaan, dan penulisan fungsi hash kustom untuk tipe buatan sendiri. Setelah membaca topik ini, pilihan antara container berbasis hash dan container terurut dapat diambil dengan memahami jaminan serta batasannya.

Peta berbasis hash#

Unordered container menyimpan elemen dalam sejumlah bucket, yaitu kelompok penyimpanan yang dipilih melalui fungsi hash. Fungsi hash mengubah kunci menjadi bilangan bertipe std::size_t, dan nilai tersebut menentukan bucket tempat elemen berada. Ketika dua kunci berbeda menghasilkan hash yang sama, kedua elemennya berbagi satu bucket, dan pustaka membedakannya menggunakan operator== milik kunci tersebut. Karena itu, tipe yang digunakan sebagai kunci unordered container harus menyediakan fungsi hash sekaligus perbandingan kesamaan.

Pencarian, penyisipan, dan penghapusan berjalan dalam $O(1)$ pada rata-rata, karena bucket yang dituju dapat dihitung langsung dari kunci. Kasus terburuknya adalah $O(n)$ , yaitu ketika seluruh elemen terkumpul dalam satu bucket akibat hash yang buruk. Kinerja rata-rata ini dijaga dengan load factor, yaitu rasio banyaknya elemen terhadap banyaknya bucket. Ketika load factor melewati batas maksimumnya, container melakukan rehash, yaitu memperbanyak bucket dan menempatkan ulang seluruh elemen, sehingga sesekali terjadi operasi yang lebih mahal.

Banyaknya bucket dapat ditinjau lewat bucket_count(), sedangkan batas load factor dapat diatur melalui max_load_factor(). Apabila banyaknya elemen sudah diperkirakan sejak awal, reserve(n) menyiapkan bucket untuk n elemen sekaligus, sehingga rehash yang menempatkan ulang seluruh elemen tidak terjadi di tengah pengisian. Kedua kendali ini bersifat penyetelan kinerja, bukan kewajiban, dan pustaka tetap menjamin kebenaran hasilnya tanpa keduanya.

Berbeda dari associative container terurut, urutan iterasi unordered container tidak ditentukan spesifikasinya. Urutan itu bergantung pada nilai hash, jumlah bucket, dan keputusan implementasi pustaka, sehingga dua program yang sama dapat mencetak elemen dengan urutan berbeda.

Penghitungan dengan unordered_map#

Contoh klasik peta berbasis hash adalah penghitung frekuensi, yaitu setiap kata yang ditemukan memperbesar nilai kuncinya. Program berikut menghitung enam kata ke dalam std::unordered_map, kemudian mencetak hasilnya menurut kunci yang terurut agar keluarannya deterministik.

cpp frekuensi-kata.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
    std::unordered_map<std::string, int> hitungan;
    std::string kata[] = {"algoritma", "variabel", "algoritma",
                          "fungsi", "variabel", "algoritma"};

    for (const std::string& k : kata) {
        ++hitungan[k];
    }

    std::cout << "Kata unik: " << hitungan.size() << '\n';

    // Urutan iterasi unordered_map tidak dijamin, sehingga kunci disalin
    // ke vector, diurutkan, dan dicetak menurut kunci yang terurut.
    std::vector<std::string> kunci;
    for (const auto& entri : hitungan) {
        kunci.push_back(entri.first);
    }
    std::sort(kunci.begin(), kunci.end());

    for (const std::string& k : kunci) {
        std::cout << k << " = " << hitungan[k] << '\n';
    }
    return 0;
}

text Keluaran

Kata unik: 3
algoritma = 3
fungsi = 1
variabel = 2

Penyalinan dan pengurutan kunci hanya diperlukan pada bagian yang mencetak. Penghitungannya sendiri tetap bekerja pada unordered map, sehingga setiap penambahan kata berjalan dalam $O(1)$ rata-rata tanpa pernah menyentuh vector.

unordered_set dan keanggotaan#

std::unordered_set menyimpan kunci tanpa nilai pendamping dan menolak duplikat, sama seperti std::set, tetapi tanpa jaminan urutan. Operasinya berupa insert(), erase(), count(), dan find(), dengan find() sebagai cara utama memeriksa keanggotaan karena berjalan dalam $O(1)$ rata-rata. Pola pemakaiannya cocok untuk daftar kata yang perlu dicek cepat, kumpulan data yang sudah diproses, dan tabel keanggotaan sementara di dalam perulangan.

Tipe bawaan seperti int, std::string, dan pointer sudah memiliki spesialisasi std::hash, sehingga std::unordered_set<int> dapat langsung dideklarasikan tanpa tambahan apa pun. Syaratnya hanya satu, yaitu tipe kunci memiliki operator== yang konsisten dengan fungsi hashnya, karena elemen yang terhimpit dalam satu bucket akhirnya dibandingkan satu per satu. Untuk tipe buatan sendiri, kedua bagian tersebut yang perlu disediakan, dan itulah pembahasan bagian berikutnya.

Penghapusan lewat erase() hanya menyentuh elemen yang dituju, sedangkan elemen lainnya tetap utuh. Apabila kunci yang dihapus ternyata tidak ada, bentuk erase(k) mengembalikan banyaknya elemen yang benar-benar terhapus, yaitu nol, sehingga penghapusan dapat dipanggil tanpa memeriksa keberadaannya lebih dahulu.

Fungsi hash kustom#

Tipe buatan sendiri tidak otomatis punya fungsi hash, sehingga unordered container perlu diberi tahu cara menghitungnya. Cara pertama adalah menyertakan functor hash sebagai parameter template kedua, sebagaimana diperlihatkan program berikut untuk tipe Titik yang memuat dua koordinat. Nilai hash digabung dari kedua koordinat melalui perkalian dan penjumlahan. Elemen yang sama harus selalu menghasilkan hash yang sama, sedangkan kunci berbeda boleh saja menghasilkan hash yang sama karena tabrakan diperbolehkan.

cpp titik-hash.cpp

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <unordered_set>
#include <vector>

struct Titik {
    int x;
    int y;

    bool operator==(const Titik& lain) const {
        return x == lain.x && y == lain.y;
    }
    bool operator<(const Titik& lain) const {
        return x != lain.x ? x < lain.x : y < lain.y;
    }
};

// Fungsi hash kustom: menggabungkan kedua koordinat menjadi satu bilangan.
struct HashTitik {
    std::size_t operator()(const Titik& t) const {
        return static_cast<std::size_t>(t.x * 31 + t.y * 17);
    }
};

int main() {
    std::unordered_set<Titik, HashTitik> himpunan;

    Titik daftar[] = {{2, 1}, {0, 3}, {2, 1}, {1, 2}};
    for (const Titik& t : daftar) {
        himpunan.insert(t);
    }

    std::cout << "Titik unik: " << himpunan.size() << '\n';
    std::cout << "Hash {2, 1} = " << HashTitik{}(Titik{2, 1}) << '\n';

    // Urutan iterasi tidak dijamin, sehingga disalin lalu diurutkan
    // menurut koordinatnya sebelum dicetak.
    std::vector<Titik> urut(himpunan.begin(), himpunan.end());
    std::sort(urut.begin(), urut.end());
    for (const Titik& t : urut) {
        std::cout << "(" << t.x << ", " << t.y << ")\n";
    }
    return 0;
}

text Keluaran

Titik unik: 3
Hash {2, 1} = 79
(0, 3)
(1, 2)
(2, 1)

Nilai hash 79 berasal dari perhitungan $2 \times 31 + 1 \times 17$ , dan nilainya konstan karena perhitungan itu tertulis sendiri dalam program. Dua titik yang sama tidak disisipkan dua kali, sehingga ukuran himpunannya tiga. Cara kedua yang memberikan hasil serupa adalah menspesialisasi std::hash<Titik>, sehingga tipe tersebut dapat dipakai tanpa parameter template tambahan, dan keduanya dipilih menurut selera organisasi kode.

Kesalahan umum#

Tiga kesalahan berikut sering muncul pada pemakaian unordered container.

Mengandalkan urutan iterasi. Urutannya tidak dijamin standar, sehingga kode yang membandingkan hasil cetakan atau menyimpan urutan itu langsung berisiko memberi hasil berbeda antar-pembangunan. Urutkan kuncinya lebih dahulu bila urutan diperlukan.
Menulis fungsi hash yang buruk, misalnya yang selalu mengembalikan nol atau yang mengabaikan sebagian anggota data. Semua elemen berkumpul dalam satu bucket sehingga operasinya meluruh menjadi $O(n)$ , dan kunci yang berbeda tetapi menghasilkan hash sama hanya dapat dibedakan lewat operator== yang lambat.
Mengira unordered map selalu lebih cepat dari map terurut. Rata-ratanya memang $O(1)$ , tetapi kasus terburuknya $O(n)$ , rehash menambah biaya sesekali, dan urutan terurutnya hilang. Untuk kunci yang perlu dicetak terurut atau dicari berdasarkan rentang, associative container terurut tetap pilihan yang lebih tepat.

Ringkasan#

Unordered container menyimpan elemen dalam bucket yang dipilih lewat fungsi hash, dan keanggotaannya diperiksa dengan operator==, sehingga pencarian berjalan $O(1)$ rata-rata dan $O(n)$ pada kasus terburuk.
Urutan iterasinya tidak dijamin standar, sehingga keluaran yang stabil diperoleh dengan menyalin kunci ke std::vector, mengurutkannya, lalu mencetak menurut kunci tersebut.
Tipe buatan sendiri menyediakan functor hash atau spesialisasi std::hash beserta operator==, dengan syarat objek yang sama selalu menghasilkan hash yang sama.

Referensi#

std::unordered_map — cppreference.com — Dokumentasi unordered_map beserta load factor dan jaminan kompleksitasnya.
std::unordered_set — cppreference.com — Dokumentasi unordered_set dan operasi keanggotaannya.
std::hash — cppreference.com — Daftar tipe yang telah terspesialisasi hash dan cara menambahkannya.
Unordered associative containers — libstdc++ manual, GNU — Penjelasan unordered container menurut implementasi GNU C++.