Ini adalah bagian kedua dalam seri tentang memilih wadah asosiatif (kamus) yang paling sesuai dalam C++23. , dan pada bagian ini, kita akan membahas wadah yang tidak diurutkan secara terperinci. Pada bagian pertama, kita membahas wadah yang diurutkan 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 . 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 ). Jumlah elemen dalam peta hash dibagi dengan ukuran total array disebut . Semakin tinggi faktor beban, semakin besar kemungkinan tabrakan hash dengan setiap elemen yang baru dimasukkan. bucket artikel Wikipedia ini faktor beban 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 . 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 . Namun, hal itu diharapkan jarang terjadi, jadi rata-rata, setiap operasi masih . Alasan lain untuk kinerja yang berpotensi berkurang adalah fungsi hash dengan distribusi yang buruk, yang akan meningkatkan frekuensi tabrakan. diamortisasi O(1) O(n) O(1) Peta hash standar Dimulai dengan C++11, pustaka standar menyediakan peta hash berikut: ( ), ( ), ( ), dan ( ). mengaitkan kunci dengan nilai, sementara hanya menyimpan kunci dan berguna untuk memeriksa apakah kunci tersebut ada dalam wadah, tetapi tidak mengambil nilai terkait. wadah memungkinkan penyimpanan beberapa kunci duplikat. std::unordered_map tautan std::unordered_set tautan std::unordered_multimap tautan std::unordered_multiset tautan Peta set Beberapa Semua kontainer standar yang tidak berurutan berbasis node dan menggunakan 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 : Rantai terpisah unordered_map Di sebelah kiri, ada array bucket, yang dialokasikan sebelumnya ke beberapa ukuran tetap ( 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 (yang masuk ke bucket ), dan dua elemen dengan kunci dan , keduanya berakhir di bucket yang sama karena nilai hashnya bertabrakan. Ada juga elemen dengan kunci , yang masuk ke bucket Setiap bucket menunjuk ke linked list, yang idealnya berisi tidak lebih dari satu elemen. Bucket , , , , dan kosong dan menunjuk ke . 8 10 1 50 256 3 3 6 0 2 4 5 7 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 ( dalam kasus kami). Dalam contoh kami, nilai sisanya adalah . 8 3 Kemudian, peta mulai membaca elemen-elemen dari daftar tertaut yang ditunjuk oleh bucket . 3 Elemen pertama memiliki kunci , yang tidak sama dengan yang kita cari, jadi peta akan terus berulang. Elemen berikutnya memiliki kunci , yang merupakan kunci yang kita butuhkan. Nilai yang sesuai adalah . 50 256 256 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 , yang menunjukkan bahwa kunci tidak ada. end 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 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 menjadi elemen), menghitung ulang hash untuk semua elemen yang ada, dan memasukkan elemen ke dalam bucket baru. faktor beban 8 16 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 . 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. pengalamatan terbuka Peta hash pihak ketiga adalah pustaka hebat yang menyediakan berbagai implementasi peta hash. Boost.Unordered Ada , , , dan , yang merupakan analog untuk kontainer , 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. boost::unordered_set boost::unordered_map boost::unordered_multiset boost::unordered_multimap std Pustaka ini juga menyediakan , , , dan , yang merupakan wadah pengalamatan terbuka. Struktur internalnya berbeda dari varian pengalamatan terbuka: boost::unordered_node_set boost::unordered_node_map boost::unordered_flat_set boost::unordered_flat_map Anda dapat membaca lebih lanjut tentang struktur internal . dalam posting blog ini Kontainer berbasis node ( , ) masih menggunakan node, yang ditunjuk oleh bucket. Kontainer ini menyediakan iterator dan stabilitas referensi yang sama yang dijamin seperti kontainer dan juga menyediakan API yang sama untuk manipulasi node (misalnya metode ). boost::unordered_node_set boost::unordered_node_map std extract Dalam kontainer datar ( , ), 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 besar. boost::unordered_flat_set boost::unordered_flat_map sizeof Pustaka pihak ketiga lain yang menerapkan kontainer pengalamatan terbuka adalah (disediakan oleh Meta). Ada beberapa varian kamus yang sangat mirip dengan kontainer pustaka Boost yang dijelaskan di atas: Folly F14 sama dengan , sama dengan . folly::F14NodeSet boost::unordered_node_set folly::F14NodeMap boost::unordered_node_map sama dengan , dan sama dengan . folly::F14ValueSet boost::unordered_flat_set folly::F14ValueMap boost::unordered_flat_map / menyimpan kunci/nilai yang dikemas dalam array yang bersebelahan, dan keranjang berisi indeks ke dalam array tersebut. folly::F14VectorMap folly::F14VectorSet / adalah kelas umum. Kelas ini memilih implementasi yang paling efisien (baik atau ) berdasarkan parameter yang Anda tentukan (seperti tipe kunci dan nilai). folly::F14FastMap folly::F14FastSet F14Value F14Vector Fitur efisiensi ekstra yang menarik dari hash map F14 adalah . 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 di semua panggilan hash map nanti untuk menghindari rehashing kunci yang sama beberapa kali. Titik awalnya adalah metode ( ). prehashing F14HashToken prehash tautan Anda dapat membaca lebih lanjut tentang struktur internal kontainer hash F14 di . postingan blog FB ini (disediakan oleh Google) juga mengimplementasikan kontainer hash datar dan berbasis node pengalamatan terbuka: , , , . Keduanya mirip dengan Boost dan F14. Anda dapat membaca lebih lanjut tentang keduanya dan . Pustaka Abseil Swiss Tables absl::flat_hash_map absl::flat_hash_set absl::node_hash_map absl::node_hash_set di sini di sini Pustaka yang kurang dikenal ( ) mengklaim sangat efisien dalam sebagian besar skenario. Penulis pustaka ini menyediakan hasil benchmark yang luas untuk banyak peta hash dalam berbagai kasus penggunaan ( ). 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. ankerl github posting blog Kualitas fungsi hash Kualitas fungsi hash penting untuk menjaga kompleksitas waktu operasi pencarian . 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 . O(1) avalanching Sayangnya, beberapa implementasi pustaka standar C++ dari fungsi hash integer dan pointer tidak mengalami avalanching. Misalnya, cukup mengembalikan nilai pointer atau integer secara langsung tanpa transformasi tambahan: . libstdc++ github Tabel hash tingkat lanjut, seperti implementasi dan , mengatasi masalah ini dengan memperkenalkan sifat . 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 . Boost menggunakan nama properti , dan properti F14 diberi nama . Idealnya, Anda harus menambahkan keduanya. boost F14 hash_is_avalanching contoh ini is_avalanching folly_is_avalanching Jika Anda menggunakan tipe kunci yang didukung secara bawaan (misalnya , , pointer) dan fungsi hash default yang disediakan oleh atau , 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. string int boost F14 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 . Semua metode non- dapat mengubah kontainer. Perlu diingat bahwa bukan dan akan mengubah kontainer. Kesalahan umum dalam kode multithread adalah: const const operator[] const std::unordered_map<std::string, bool> map; // ... if (map["key"]) { // ... } Dalam kode di atas, tujuannya adalah untuk memeriksa apakah nilai yang sesuai dengan adalah . Namun, akan tersebut ke jika belum ada. Nilai yang baru ditambahkan akan ditetapkan ke default ( 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: key true map["key"] menambahkan key map false 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, dan tidak mengubah peta, dan pencarian menjadi aman untuk thread. Jika tujuannya hanya untuk memeriksa apakah kunci tersebut ada di peta, Anda cukup memanggil . find end map.contains("key") Peta tak berurutan yang aman untuk thread Ada beberapa implementasi peta hash yang aman untuk thread. Salah satu opsi adalah dan dari . Kontainer Boost menyediakan API berbasis kunjungan yang sangat berbeda dari API yang disediakan oleh pustaka standar C++. boost::concurrent_flat_set boost::concurrent_flat_map pustaka Boost.Unordered Pilihan lainnya adalah ( ). Folly mencoba menjaga API-nya sedekat mungkin dengan kontainer standar C++ yang tidak berurutan. folly::ConcurrentHashMap github adalah pustaka kontainer bebas-kunci yang menyediakan beberapa implementasi peta hash bebas-kunci (misalnya , , , , ). 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 MichaelHashMap SkipListMap SkipListSet FeldmanHashMap FeldmanHashSet 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 , jika tidak, gunakan . peta kumpulan Jika perlu menyimpan kunci duplikat di peta, gunakan kontainer. beberapa Jika Anda memerlukan jaminan iterator dan stabilitas referensi yang seketat mungkin, gunakan kontainer berbasis node , , , atau (seperti , , , atau ). dan kemungkinan besar akan menjadi yang paling efisien. std boost folly abseil std::unordered_map boost::unordered_map boost::unordered_node_map folly::F14NodeMap boost::unordered_node_... folly 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 atau ). boost::unordered_flat_map folly::F14FastMap Kontainer datar menggunakan lebih banyak memori daripada kontainer berbasis node, terutama jika kunci dan/atau nilainya besar. Jika penggunaan memori menjadi masalah, gunakan kontainer berbasis node sebagai gantinya. sizeof 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.
