Ini adalah bagian kedua dalam seri tentang memilih wadah asosiatif (kamus) yang paling sesuai dalam C++23. Pada bagian pertama, kita membahas wadah yang diurutkan , dan pada bagian ini, kita akan membahas wadah yang tidak diurutkan secara terperinci.

Kontainer yang tidak diurutkan

Kontainer ini tidak menyediakan urutan yang pasti untuk kuncinya. Selain itu, urutan kunci dapat berubah dengan setiap modifikasi, jadi program tidak boleh bergantung padanya. Kontainer semacam itu selalu diimplementasikan sebagai peta hash.

Umumnya, ketika menambahkan, menghapus, atau mencari kunci, peta hash pertama-tama menghitung beberapa nilai hash integral dari kunci itu menggunakan fungsi hash. Hash (atau lebih tepatnya bagiannya) kemudian digunakan sebagai indeks ke dalam array pra-alokasi yang berdekatan. Setiap entri dalam array ini disebut bucket . Beberapa entri dalam array itu akan kosong, beberapa akan berisi satu elemen, dan beberapa mungkin memetakan ke lebih dari satu elemen karena tabrakan hash. Ini terjadi ketika kunci yang berbeda memiliki nilai hash yang menunjuk ke indeks array yang sama. Peta hash menggunakan berbagai strategi untuk menangani tabrakan hash (lihat artikel Wikipedia ini ). Jumlah elemen dalam peta hash dibagi dengan ukuran total array disebut faktor beban . Semakin tinggi faktor beban, semakin besar kemungkinan tabrakan hash dengan setiap elemen yang baru dimasukkan.

Berbeda dengan kontainer yang diurutkan, peta hash tidak mendukung kueri rentang, operasi peringkat/pilih, iterasi atas kunci secara berurutan, dan pencarian kunci yang lebih kecil/lebih besar dari kunci yang diberikan. Sebagai gantinya, peta hash mencapai kinerja terbaik yang dapat dicapai: kompleksitas waktu operasi pencarian/penyisipan/penghapusan diamortisasi O(1) . Saya katakan "diamortisasi" di sini, karena ketika jumlah elemen menjadi terlalu besar, peta hash perlu melakukan hash ulang terhadap isinya untuk mengurangi faktor beban (yang secara efektif mengembangkan array bucket). Kompleksitas waktu dari hash ulang adalah O(n) . Namun, hal itu diharapkan jarang terjadi, jadi rata-rata, setiap operasi masih O(1) . Alasan lain untuk kinerja yang berpotensi berkurang adalah fungsi hash dengan distribusi yang buruk, yang akan meningkatkan frekuensi tabrakan.

Peta hash standar

Dimulai dengan C++11, pustaka standar menyediakan peta hash berikut: std::unordered_map ( tautan ), std::unordered_set ( tautan ), std::unordered_multimap ( tautan ), dan std::unordered_multiset ( tautan ). Peta mengaitkan kunci dengan nilai, sementara set hanya menyimpan kunci dan berguna untuk memeriksa apakah kunci tersebut ada dalam wadah, tetapi tidak mengambil nilai terkait. Beberapa wadah memungkinkan penyimpanan beberapa kunci duplikat.

Semua kontainer standar yang tidak berurutan berbasis node dan menggunakan Rantai terpisah untuk menangani tabrakan hash, yang berarti, kontainer menyimpan setiap pasangan kunci atau nilai kunci dalam node daftar tertaut yang terpisah. Memori untuk setiap node baru dialokasikan secara individual, yang tidak terlalu efisien. Hal ini juga membuat struktur data tidak ramah terhadap cache CPU, karena setiap akses kunci memerlukan pengalihan tambahan. Berikut ini adalah tampilan struktur internal unordered_map :

Di sebelah kiri, ada array bucket, yang dialokasikan sebelumnya ke beberapa ukuran tetap ( 8 dalam contoh kita). Awalnya, semua bucket kosong. Saat kita mulai menambahkan elemen ke peta hash, beberapa bucket akan terisi. Dalam contoh di atas, ada elemen dengan kunci 10 (yang masuk ke bucket 1 ), dan dua elemen dengan kunci 50 dan 256 , keduanya berakhir di bucket yang sama 3 karena nilai hashnya bertabrakan. Ada juga elemen dengan kunci 3 , yang masuk ke bucket 6 Setiap bucket menunjuk ke linked list, yang idealnya berisi tidak lebih dari satu elemen. Bucket 0 , 2 , 4 , 5 , dan 7 kosong dan menunjuk ke nullptr .

Mari kita asumsikan kita perlu menemukan nilai untuk kunci 256 .

• Pertama, peta menghitung hash kunci dan mendapatkan sisanya saat membagi nilai hash dengan jumlah total bucket ( 8 dalam kasus kami). Dalam contoh kami, nilai sisanya adalah 3 .
• Kemudian, peta mulai membaca elemen-elemen dari daftar tertaut yang ditunjuk oleh bucket 3 .
• Elemen pertama memiliki kunci 50 , yang tidak sama dengan 256 yang kita cari, jadi peta akan terus berulang. Elemen berikutnya memiliki kunci 256 , yang merupakan kunci yang kita butuhkan. Nilai yang sesuai adalah xyz .
• Jika kunci tidak ada dalam kamus, peta akan menuju ke bucket kosong atau mengulang daftar tertaut hingga akhir. Dalam kedua kasus, peta akan mengembalikan iterator end , yang menunjukkan bahwa kunci tidak ada.

Anda mungkin memperhatikan bahwa elemen terakhir dari setiap daftar menunjuk ke elemen pertama dari daftar berikutnya. Hal ini dilakukan dalam beberapa implementasi untuk meningkatkan efisiensi iterasi. Daripada memeriksa bucket demi bucket saat mengiterasi semua elemen hash map, kita dapat menggunakan koneksi tersebut untuk melompat dari satu linked list yang tidak kosong ke yang lain dengan lebih cepat.

Jika kita terus menambahkan lebih banyak elemen ke peta hash di atas, pada titik tertentu faktor beban akan menjadi terlalu tinggi (misalnya, 80%), dan peta hash akan memutuskan untuk melakukan hash ulang. Ia akan mengembangkan array yang telah dialokasikan sebelumnya (misalnya dari 8 menjadi 16 elemen), menghitung ulang hash untuk semua elemen yang ada, dan memasukkan elemen ke dalam bucket baru.

Kontainer standar menyediakan jaminan stabilitas referensi dan iterator, tetapi lebih lemah daripada yang ditawarkan oleh kontainer yang dipesan. Referensi ke elemen yang ada tidak pernah dibatalkan. Iterator ke elemen yang ada dapat dibatalkan hanya jika penambahan elemen baru menyebabkan pengulangan, atau jika pengulangan dipicu secara manual:

 #include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> map{ {"test", 123}, {"xyz", 456}, {"abc", 10} }; auto& value = map["abc"]; auto valueIt = map.find("abc"); // Might cause a rehash if the load factor // is too high map.emplace("zzz", 1000); // Triggers the rehash manually map.rehash(1000); // References remain valid in any case: std::cout << value << "\n"; // Iterators are invalidated: the line below // is undefined behavior and might crash std::cout << valueIt->second << "\n"; }

Sejak C++17, kontainer yang tidak berurutan memungkinkan manipulasi node: dimungkinkan untuk mengambil node dari satu peta dan memindahkannya ke peta lain tanpa menyalin kunci dan nilainya:

 #include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> map1{ {"test", 123}, {"xyz", 456}, {"abc", 10} }; // Take the node from map1: auto node = map1.extract("xyz"); // We can even change its key // (we can also change the value // if needed): node.key() = "xyzxyz"; std::unordered_map<std::string, int> map2; // Insert the node into another map: map2.insert(std::move(node)); // Prints "xyzxyz: 456": for (const auto& [k, v] : map2) { std::cout << k << ": " << v << "\n"; } }

Inilah yang terjadi pada program di atas:

Strategi lain untuk menangani tabrakan hash disebut pengalamatan terbuka . Dalam peta hash pengalamatan terbuka, setiap keranjang menyimpan paling banyak satu elemen. Jika keranjang sudah terisi, elemen dengan nilai hash yang sama akan masuk ke keranjang lain yang kosong. Peta hash tersebut mencoba mengelompokkan elemen dalam blok memori yang berdekatan untuk meningkatkan efisiensi dan membuat struktur data lebih ramah terhadap cache CPU. Pustaka standar C++ tidak menyediakan peta hash pengalamatan terbuka, tetapi ada banyak alternatif pihak ketiga.

Peta hash pihak ketiga

Boost.Unordered adalah pustaka hebat yang menyediakan berbagai implementasi peta hash.

Ada boost::unordered_set , boost::unordered_map , boost::unordered_multiset , dan boost::unordered_multimap , yang merupakan analog untuk kontainer std , dan semua yang tertulis di atas berlaku untuk kontainer tersebut. Kontainer ini menggunakan struktur internal yang sedikit lebih kompleks dengan "kelompok bucket" untuk meningkatkan efisiensi iterasi.

Pustaka ini juga menyediakan boost::unordered_node_set , boost::unordered_node_map , boost::unordered_flat_set , dan boost::unordered_flat_map , yang merupakan wadah pengalamatan terbuka. Struktur internalnya berbeda dari varian pengalamatan terbuka:

Anda dapat membaca lebih lanjut tentang struktur internal dalam posting blog ini .

Kontainer berbasis node ( boost::unordered_node_set , boost::unordered_node_map ) masih menggunakan node, yang ditunjuk oleh bucket. Kontainer ini menyediakan iterator dan stabilitas referensi yang sama yang dijamin seperti kontainer std dan juga menyediakan API yang sama untuk manipulasi node (misalnya metode extract ).

Dalam kontainer datar ( boost::unordered_flat_set , boost::unordered_flat_map ), kunci dan nilai disimpan langsung dalam array bucket. Kontainer datar adalah yang paling efisien, tetapi memberikan jaminan yang paling lemah: iterator dan referensi ke semua elemen tidak valid saat terjadi pengulangan. API manipulasi node tidak disediakan sama sekali. Kontainer datar mungkin menggunakan lebih banyak memori daripada yang berbasis node, terutama jika kunci atau nilai sizeof besar.

Pustaka pihak ketiga lain yang menerapkan kontainer pengalamatan terbuka adalah Folly F14 (disediakan oleh Meta). Ada beberapa varian kamus yang sangat mirip dengan kontainer pustaka Boost yang dijelaskan di atas:

• folly::F14NodeSet sama dengan boost::unordered_node_set , folly::F14NodeMap sama dengan boost::unordered_node_map .
• folly::F14ValueSet sama dengan boost::unordered_flat_set , dan folly::F14ValueMap sama dengan boost::unordered_flat_map .
• folly::F14VectorMap / folly::F14VectorSet menyimpan kunci/nilai yang dikemas dalam array yang bersebelahan, dan keranjang berisi indeks ke dalam array tersebut.
• folly::F14FastMap / folly::F14FastSet adalah kelas umum. Kelas ini memilih implementasi yang paling efisien (baik F14Value atau F14Vector ) berdasarkan parameter yang Anda tentukan (seperti tipe kunci dan nilai).

Fitur efisiensi ekstra yang menarik dari hash map F14 adalah prehashing . Misalnya, jika Anda perlu mencari kunci yang sama beberapa kali, dan hashing-nya mahal (misalnya kunci berupa string), Anda dapat melakukan prehash sekali, lalu menggunakan F14HashToken di semua panggilan hash map nanti untuk menghindari rehashing kunci yang sama beberapa kali. Titik awalnya adalah metode prehash ( tautan ).

Anda dapat membaca lebih lanjut tentang struktur internal kontainer hash F14 di postingan blog FB ini .

Pustaka Abseil Swiss Tables (disediakan oleh Google) juga mengimplementasikan kontainer hash datar dan berbasis node pengalamatan terbuka: absl::flat_hash_map , absl::flat_hash_set , absl::node_hash_map , absl::node_hash_set . Keduanya mirip dengan Boost dan F14. Anda dapat membaca lebih lanjut tentang keduanya di sini dan di sini .

Pustaka ankerl yang kurang dikenal ( github ) mengklaim sangat efisien dalam sebagian besar skenario. Penulis pustaka ini menyediakan hasil benchmark yang luas untuk banyak peta hash dalam berbagai kasus penggunaan ( posting blog ). Anda dapat mengikuti hasil ini, tetapi jangan terlalu percaya. Selalu uji peta hash yang Anda pilih di lingkungan produksi. Benchmark selalu sintetis dan tidak mencakup kasus ketika CPU dan memori melakukan pekerjaan lain selain operasi peta hash. Benchmark juga tidak mencakup kasus ketika berbagai bagian memori peta hash tidak berada dalam cache CPU, yang akan sering terjadi dalam program nyata.

Kualitas fungsi hash

Kualitas fungsi hash penting untuk menjaga kompleksitas waktu operasi pencarian O(1) . Pemetaan hash datar sangat sensitif terhadap kualitas fungsi hash. Fungsi hash yang ideal dapat didefinisikan seperti ini: jika satu bit dalam kunci berubah, nilai hash yang sesuai akan mengubah setengah bitnya secara acak. Fungsi hash seperti itu disebut avalanching .

Sayangnya, beberapa implementasi pustaka standar C++ dari fungsi hash integer dan pointer tidak mengalami avalanching. Misalnya, libstdc++ cukup mengembalikan nilai pointer atau integer secara langsung tanpa transformasi tambahan: github .

Tabel hash tingkat lanjut, seperti implementasi boost dan F14 , mengatasi masalah ini dengan memperkenalkan sifat hash_is_avalanching . Jika fungsi hash tidak menyatakan dirinya sebagai avalanching, tabel hash akan melakukan langkah pencampuran tambahan untuk meningkatkan kualitas hash. Ini memerlukan biaya tambahan. Jika Anda mengimplementasikan fungsi hash kustom, dan Anda tahu bahwa kualitasnya bagus, Anda dapat menandainya sebagai avalanching seperti yang ditunjukkan dalam contoh ini . Boost menggunakan nama properti is_avalanching , dan properti F14 diberi nama folly_is_avalanching . Idealnya, Anda harus menambahkan keduanya.

Jika Anda menggunakan tipe kunci yang didukung secara bawaan (misalnya string , int , pointer) dan fungsi hash default yang disediakan oleh boost atau F14 , kunci tersebut akan ditandai dengan benar sebagaimana diperlukan, dan Anda tidak perlu memikirkan hal ini kecuali Anda memutuskan untuk mengimplementasikan tipe kunci kustom, yang akan memerlukan fungsi hash kustom.

Keamanan benang

Semua kontainer di atas pada umumnya tidak aman untuk thread, dan Anda harus menerapkan sinkronisasi eksternal (misalnya, menggunakan mutex) jika satu thread dapat mengubah peta hash saat thread lain mengaksesnya.

Jika semua thread hanya membaca peta, sinkronisasi tidak diperlukan. Pastikan Anda hanya memanggil metode yang ditandai dengan const . Semua metode non- const dapat mengubah kontainer. Perlu diingat bahwa operator[] bukan const dan akan mengubah kontainer. Kesalahan umum dalam kode multithread adalah:

 std::unordered_map<std::string, bool> map; // ... if (map["key"]) { // ... }

Dalam kode di atas, tujuannya adalah untuk memeriksa apakah nilai yang sesuai dengan key adalah true . Namun, map["key"] akan menambahkan key tersebut ke map jika belum ada. Nilai yang baru ditambahkan akan ditetapkan ke default ( false dalam contoh di atas). Ini berarti, kode tersebut tidak aman untuk thread, dan tidak terlalu optimal. Cara yang lebih efisien dan aman untuk thread untuk memeriksa kondisi yang sama adalah sebagai berikut:

 if (auto it = map.find("key"); it != map.end() && it->second == true) { // ... }

• Di sini, pertama-tama kita mendapatkan iterator ke elemen yang diidentifikasi oleh "kunci".
• Kami kemudian memeriksa apakah elemen tersebut ada di peta ( it != map.end() ).
• Jika demikian, kami akhirnya memeriksa nilainya ( it->second == true ).

Dalam contoh ini, find dan end tidak mengubah peta, dan pencarian menjadi aman untuk thread. Jika tujuannya hanya untuk memeriksa apakah kunci tersebut ada di peta, Anda cukup memanggil map.contains("key") .

Peta tak berurutan yang aman untuk thread

Ada beberapa implementasi peta hash yang aman untuk thread.

• Salah satu opsi adalah boost::concurrent_flat_set dan boost::concurrent_flat_map dari pustaka Boost.Unordered . Kontainer Boost menyediakan API berbasis kunjungan yang sangat berbeda dari API yang disediakan oleh pustaka standar C++.
• Pilihan lainnya adalah folly::ConcurrentHashMap ( github ). Folly mencoba menjaga API-nya sedekat mungkin dengan kontainer standar C++ yang tidak berurutan.
• libcds adalah pustaka kontainer bebas-kunci yang menyediakan beberapa implementasi peta hash bebas-kunci (misalnya MichaelHashMap , SkipListMap , SkipListSet , FeldmanHashMap , FeldmanHashSet ). Pustaka ini belum diperbarui selama beberapa waktu dan tidak menyediakan dokumentasi terperinci, tetapi saya tetap membagikannya karena kontainer yang ditawarkannya unik. Jika kasus penggunaan Anda menyiratkan pertentangan tinggi pada peta hash, cobalah kamus bebas-kunci ini yang ditawarkan oleh libcds .
• Jika efisiensi bukan masalah, Anda dapat menyinkronkan akses ke peta yang tidak aman untuk thread menggunakan mutex. Atau, Anda dapat sepenuhnya menghindari akses bersamaan, yang seringkali lebih efisien daripada menggunakan kontainer yang aman untuk thread atau menambahkan sinkronisasi.

Yang mana yang harus saya gunakan?

Mari kita lihat poin-poin ringkasan yang menjelaskan cara memilih wadah yang paling cocok.

• Jika Anda perlu mengaitkan kunci dengan nilai, pilih peta , jika tidak, gunakan kumpulan .
• Jika perlu menyimpan kunci duplikat di peta, gunakan beberapa kontainer.
• Jika Anda memerlukan jaminan iterator dan stabilitas referensi yang seketat mungkin, gunakan kontainer berbasis node std , boost , folly , atau abseil (seperti std::unordered_map , boost::unordered_map , boost::unordered_node_map , atau folly::F14NodeMap ). boost::unordered_node_... dan folly kemungkinan besar akan menjadi yang paling efisien.
• Jika stabilitas iterator dan referensi tidak penting (yang artinya, Anda tidak menyimpan iterator, referensi, atau pointer ke elemen peta/set secara eksternal atau tidak mengharapkannya tetap valid setelah peta dimodifikasi), maka pilih wadah datar (seperti boost::unordered_flat_map atau folly::F14FastMap ).
• Kontainer datar menggunakan lebih banyak memori daripada kontainer berbasis node, terutama jika sizeof kunci dan/atau nilainya besar. Jika penggunaan memori menjadi masalah, gunakan kontainer berbasis node sebagai gantinya.
• Kontainer F14 menyediakan fungsi pra-hashing untuk efisiensi ekstra. Jika Anda mencari/menambahkan/menghapus kunci yang identik beberapa kali, F14 akan memungkinkan penghematan biaya hashing dengan melakukan pra-hashing kunci.
• Semua poin di atas berlaku untuk penggunaan kontainer single-threaded (atau akses baca multi-threaded tanpa modifikasi bersamaan). Jika modifikasi multi-threaded diperlukan, pilih salah satu opsi thread-safe yang tercantum di atas. Opsi tersebut dapat menunjukkan kinerja yang bervariasi dalam kode produksi yang sebenarnya, jadi pertimbangkan untuk mengujinya dalam aplikasi Anda dan membandingkan hasilnya.