unordered_map C++: pencarian cepat dengan hash map

Kalau urutan tidak penting

Kamu baru saja melihat std::map, yang menjaga key-nya tetap terurut memakai balanced tree dan memberi operasi O(log n). Tapi mengurutkan itu ada biayanya, dan sering kali kamu tidak peduli dalam urutan apa key-nya keluar. Kamu hanya ingin bertanya "apakah key ini ada, dan berapa nilainya?" secepat mungkin.

Untuk itulah std::unordered_map ada. Ia adalah hash table: setiap key dimasukkan ke fungsi hash untuk menentukan di mana key itu disimpan, sehingga penambahan, pencarian, dan penghapusan rata-rata O(1), bukan O(log n). Gantinya, urutan iterasinya tidak ditentukan: key-key keluar dalam urutan apa pun yang kebetulan dimiliki bucket-nya.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> stock = {
        {"apple", 12},
        {"banana", 7},
        {"cherry", 30}
    };

    cout << "bananas: " << stock["banana"] << "\n";
    stock["apple"] += 5;
    cout << "apples now: " << stock["apple"] << "\n";
}

Antarmukanya sengaja dibuat hampir sama dengan map, jadi sering kali kamu bisa menukar keduanya hanya dengan mengubah tipenya. Sertakan <unordered_map> (bukan <map>), dan key-nya akan keluar tidak terurut.

Menambah dan memperbarui

Ada beberapa cara memasukkan entri, dan tidak semuanya berperilaku sama. Dua yang paling sering kamu pakai adalah operator[] dan insert:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> votes;

    votes["alice"] = 3;              // create or overwrite
    votes["alice"] = 5;              // overwrites -> 5
    votes.insert({"bob", 2});        // inserts only if "bob" is absent
    votes.insert({"bob", 99});       // ignored, "bob" already exists

    cout << "alice: " << votes["alice"] << "\n";   // 5
    cout << "bob:   " << votes["bob"] << "\n";      // 2, not 99
}

Perbedaan utamanya: operator[] menimpa nilai yang sudah ada, sedangkan insert membiarkan key yang sudah ada tanpa perubahan. Kalau kamu memakai C++17, insert_or_assign(key, value) memberimu perilaku "isi nilai ini apa pun yang terjadi", dan try_emplace(key, args...) membuat nilai di tempatnya hanya kalau key-nya baru, berguna untuk nilai yang mahal dibuat.

Jebakan operator[]: menambahkan saat membaca

Ini bug unordered_map yang paling umum, jadi ia mendapat bagiannya sendiri. m[key] bukan sekadar membaca. Kalau key-nya tidak ada, ia membuat nilai default dan menambahkannya (int menjadi 0, string menjadi ""), lalu mengembalikan reference. Jadi kode yang kelihatannya hanya mencari diam-diam memperbesar map:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen;
    seen["x"] = 1;

    // We only meant to CHECK for "y", but [] inserted it:
    if (seen["y"] == 0) {
        cout << "y looked missing...\n";
    }

    cout << "size is now " << seen.size() << "\n";   // 2, not 1!
}

seen["y"] membuat entri "y" -> 0 hanya karena disebut. Untuk mengecek keberadaan tanpa mengubah map, pakai count (mengembalikan 0 atau 1) atau find:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen{{"x", 1}};

    if (seen.count("y")) {
        cout << "found y\n";
    } else {
        cout << "no y, size still " << seen.size() << "\n";   // 1
    }

    // C++20: contains() reads cleaner than count()
    if (seen.contains("x")) cout << "x is here\n";
}

Aturan praktisnya: pakai [] hanya kalau kamu memang ingin membuat atau memperbarui. Untuk membaca saja, pakai count, contains (C++20), atau find.

find dan at: pencarian yang aman

find mengembalikan iterator ke entrinya, atau end() kalau key-nya tidak ada. Ia tidak pernah menambahkan apa pun, dan memungkinkan kamu menjangkau key sekaligus nilainya lewat it->first dan it->second dalam satu pencarian:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> prices = {{"pen", 2}, {"mug", 9}};

    auto it = prices.find("mug");
    if (it != prices.end()) {
        cout << it->first << " costs " << it->second << "\n";
    } else {
        cout << "not found\n";
    }
}

Kalau kamu tahu key-nya seharusnya ada dan ingin program gagal dengan tegas kalau ternyata tidak, pakai at. Berbeda dengan [], at tidak menambahkan apa pun: ia melempar std::out_of_range untuk key yang tidak ada:

int p = prices.at("pen");   // fine
int q = prices.at("hat");   // throws std::out_of_range - key absent

Jadi kamu punya tiga gaya pencarian: [] (menambahkan), at (melempar exception), dan find/count (melaporkan keberadaan tanpa menyentuh map). Pilih yang cara gagalnya sesuai dengan maksudmu.

Iterasi dan penghapusan

Range-based for loop dengan structured binding adalah cara rapi untuk menelusuri setiap entri. Ingat bahwa urutannya acak, jadi jangan pernah mengandalkannya:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 7}, {"green", 2}};

    for (const auto& [team, score] : wins) {
        cout << team << ": " << score << "\n";   // order is unspecified
    }
}

Untuk menghapus entri, erase langsung menerima sebuah key dan mengembalikan berapa yang dihapus (0 atau 1). Ada satu jebakan penting: menghapus sambil melakukan iterasi pada unordered_map hanya membuat iterator elemen yang dihapus menjadi tidak valid, jadi pakai nilai kembalian erase(it) untuk maju dengan aman:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 1}, {"green", 2}};

    // Drop every team with a score below 3
    for (auto it = wins.begin(); it != wins.end(); ) {
        if (it->second < 3)
            it = wins.erase(it);   // erase returns the next valid iterator
        else
            ++it;
    }

    cout << "remaining entries: " << wins.size() << "\n";
}

Menulis gaya wins.erase(it++) atau ++it setelah erase(it) biasa adalah jebakan klasik dangling iterator: iterator yang dihapus sudah mati, jadi selalu ambil iterator yang dikembalikan erase.

map atau unordered_map?

Keduanya menyimpan pasangan key-value dengan API yang mirip, jadi pilihannya bergantung pada apa yang kamu butuhkan:

// std::map            -> sorted keys, O(log n), range queries (lower_bound)
// std::unordered_map  -> no order,    O(1) avg, fastest plain lookup

Pakai unordered_map kalau kamu hanya butuh pencarian cepat berdasarkan key dan urutan tidak relevan (menghitung frekuensi kata, caching, menghapus duplikat). Pilih map kalau kamu butuh key dalam urutan terurut, ingin iterasi berurutan, atau melakukan query rentang. Ada dua catatan untuk unordered_map: O(1)-nya adalah rata-rata, dan hash yang buruk bisa menurunkannya; selain itu, tipe key buatan sendiri butuh spesialisasi hash atau hash functor, sedangkan map hanya butuh operator<.

Berikutnya: set

Sekarang kamu sudah melihat kedua jenis container key-value. Tapi kadang kamu sama sekali tidak butuh nilai, kamu hanya peduli apakah sesuatu ada, seperti kumpulan tag unik atau ID yang sudah dikunjungi. Berikutnya kita akan membahas std::set (dan saudaranya yang berbasis hash, unordered_set), yang hanya menyimpan key dan otomatis menjaganya tetap unik.