Unduh hopscotch map - unduh kode sumber hopscotch map

Implementasi C++ dari peta hash cepat dan kumpulan hash menggunakan hashing hopscotch

Pustaka peta hopscotch adalah implementasi C++ dari peta hash cepat dan kumpulan hash menggunakan pengalamatan terbuka dan hashing hopscotch untuk menyelesaikan tabrakan. Ini adalah struktur data ramah cache yang menawarkan kinerja lebih baik daripada std::unordered_map dalam banyak kasus dan sangat mirip dengan google::dense_hash_map sambil menggunakan lebih sedikit memori dan menyediakan lebih banyak fungsi.

Perpustakaan menyediakan kelas-kelas utama berikut: tsl::hopscotch_map , tsl::hopscotch_set , tsl::hopscotch_pg_map dan tsl::hopscotch_pg_set . Dua kebijakan pertama lebih cepat dan menggunakan kebijakan pertumbuhan kekuatan dua, sedangkan dua kebijakan terakhir menggunakan kebijakan pertumbuhan prima dan mampu mengatasi fungsi hash yang buruk dengan lebih baik. Gunakan versi prime jika ada kemungkinan pola berulang di bit bawah hash Anda (misalnya, Anda menyimpan pointer dengan fungsi hash identitas). Lihat GrowthPolicy untuk detailnya.

Selain kelas-kelas ini perpustakaan juga menyediakan tsl::bhopscotch_map , tsl::bhopscotch_set , tsl::bhopscotch_pg_map dan tsl::bhopscotch_pg_set . Kelas-kelas ini memiliki persyaratan tambahan untuk kuncinya, yaitu LessThanComparable , tetapi mereka memberikan batas atas asimtotik yang lebih baik, lihat detailnya dalam contoh. Meskipun demikian, jika Anda tidak memiliki persyaratan khusus (risiko serangan hash DoS), tsl::hopscotch_map dan tsl::hopscotch_set sudah cukup dalam banyak kasus dan harus menjadi pilihan default Anda karena kinerjanya lebih baik secara umum.

Ikhtisar hashing hopscotch dan beberapa detail implementasi dapat ditemukan di sini.

Tolok ukur tsl::hopscotch_map terhadap peta hash lainnya dapat ditemukan di sini. Halaman ini juga memberikan beberapa saran tentang struktur tabel hash mana yang harus Anda coba untuk kasus penggunaan Anda (berguna jika Anda agak bingung dengan beberapa implementasi tabel hash di namespace tsl ).

Fitur utama

Pustaka khusus header, cukup tambahkan direktori penyertaan ke jalur penyertaan Anda dan Anda siap berangkat. Jika Anda menggunakan CMake, Anda juga dapat menggunakan target yang diekspor tsl::hopscotch_map dari CMakeLists.txt.
Tabel hash cepat, lihat patokan untuk beberapa angka.
Dukungan untuk kunci/nilai yang dapat dibangun hanya-pindah dan non-default.
Dukungan untuk pencarian heterogen yang memungkinkan penggunaan find dengan tipe yang berbeda dari Key (misalnya jika Anda memiliki peta yang menggunakan std::unique_ptr<foo> sebagai kunci, Anda dapat menggunakan foo* atau std::uintptr_t sebagai parameter kunci untuk find tanpa membuat std::unique_ptr<foo> , lihat contoh).
Tidak perlu mencadangkan nilai sentinel apa pun dari kunci.
Kemungkinan untuk menyimpan nilai hash pada sisipan untuk pengulangan dan pencarian yang lebih cepat jika fungsi hash atau kunci yang setara mahal untuk dihitung (lihat parameter templat StoreHash).
Jika hash diketahui sebelum pencarian, dimungkinkan untuk meneruskannya sebagai parameter untuk mempercepat pencarian (lihat parameter precalculated_hash di API).
tsl::bhopscotch_map dan tsl::bhopscotch_set menyediakan kasus terburuk O(log n) pada pencarian dan penghapusan yang membuat kelas-kelas ini tahan terhadap serangan tabel hash Deny of Service (DoS) (lihat detail dalam contoh).
Pustaka dapat digunakan dengan pengecualian dinonaktifkan (melalui opsi -fno-exceptions di Clang dan GCC, tanpa opsi /EH di MSVC atau cukup dengan mendefinisikan TSL_NO_EXCEPTIONS ). std::terminate digunakan sebagai pengganti instruksi throw ketika pengecualian dinonaktifkan.
API sangat mirip dengan std::unordered_map dan std::unordered_set .

Perbedaan dibandingkan dengan `std::unordered_map`

tsl::hopscotch_map mencoba memiliki antarmuka yang mirip dengan std::unordered_map , tetapi ada beberapa perbedaan.

Pembatalan iterator saat penyisipan tidak berperilaku sama. Secara umum, operasi apa pun yang mengubah tabel hash, kecuali erase , akan membatalkan semua iterator (lihat API untuk detailnya).
Referensi dan penunjuk ke kunci atau nilai di peta tidak valid dengan cara yang sama seperti iterator ke nilai kunci ini saat dimasukkan.
Untuk iterator, operator*() dan operator->() mengembalikan referensi dan pointer ke const std::pair<Key, T> alih-alih std::pair<const Key, T> , sehingga nilai T tidak dapat dimodifikasi. Untuk mengubah nilai, Anda harus memanggil metode value() dari iterator untuk mendapatkan referensi yang bisa diubah. Contoh:

tsl::hopscotch_map< int , int > map = {{ 1 , 1 }, { 2 , 1 }, { 3 , 1 }};
for ( auto it = map.begin(); it != map.end(); ++it) {
    // it->second = 2; // Illegal
    it. value () = 2 ; // Ok
}

Tipe move-only harus memiliki konstruktor perpindahan nothrow (dengan pengalamatan terbuka, tidak mungkin untuk mempertahankan jaminan pengecualian yang kuat pada pengulangan jika konstruktor perpindahan dapat melakukan throw).
Tidak ada dukungan untuk beberapa metode terkait bucket (seperti bucket_size , bucket , ...).

Perbedaan ini juga berlaku antara std::unordered_set dan tsl::hopscotch_set .

Jaminan keamanan thread dan pengecualian sama dengan std::unordered_map/set (yaitu dimungkinkan untuk memiliki banyak pembaca tanpa penulis).

Kebijakan pertumbuhan

Pustaka ini mendukung berbagai kebijakan pertumbuhan melalui parameter templat GrowthPolicy . Tiga kebijakan disediakan oleh perpustakaan tetapi Anda dapat dengan mudah menerapkan kebijakan Anda sendiri jika diperlukan.

tsl::hh::kebijakan_kekuasaan_dua_pertumbuhan_. Kebijakan default yang digunakan oleh tsl::(b)hopscotch_map/set . Kebijakan ini menjaga ukuran susunan keranjang tabel hash menjadi pangkat dua. Batasan ini memungkinkan kebijakan menghindari penggunaan operasi modulo lambat untuk memetakan hash ke bucket, alih-alih hash % 2 ⁿ , kebijakan ini menggunakan hash & (2 ⁿ - 1) (lihat modulo cepat). Cepat tetapi ini dapat menyebabkan banyak tabrakan dengan fungsi hash yang buruk karena modulo dengan kekuatan dua pada akhirnya hanya menutupi bit paling signifikan.
tsl::hh::prime_growth_policy. Kebijakan default yang digunakan oleh tsl::(b)hopscotch_pg_map/set . Kebijakan ini menjaga ukuran susunan keranjang tabel hash tetap pada bilangan prima. Saat memetakan hash ke sebuah bucket, menggunakan bilangan prima sebagai modulo akan menghasilkan distribusi hash yang lebih baik di seluruh bucket bahkan dengan fungsi hash yang buruk. Untuk memungkinkan kompiler mengoptimalkan operasi modulo, kebijakan menggunakan tabel pencarian dengan modulo bilangan prima konstan (lihat API untuk detailnya). Lebih lambat dari tsl::hh::power_of_two_growth_policy tetapi lebih aman.
tsl::hh::mod_growth_policy. Kebijakan ini mengembangkan peta dengan faktor pertumbuhan yang dapat disesuaikan dan dimasukkan ke dalam parameter. Kemudian cukup gunakan operator modulo untuk memetakan hash ke bucket. Lebih lambat namun lebih fleksibel.

Jika Anda mengalami kinerja yang buruk, periksa overflow_size() , jika bukan nol, Anda mungkin mengalami banyak tabrakan hash. Ubah fungsi hash untuk sesuatu yang lebih seragam atau coba kebijakan pertumbuhan lain (terutama tsl::hh::prime_growth_policy ). Sayangnya kadang-kadang sulit untuk menjaga diri terhadap tabrakan (misalnya serangan DoS pada peta hash). Jika perlu, periksa juga tsl::bhopscotch_map/set yang menawarkan skenario terburuk O(log n) pada pencarian alih-alih O(n), lihat detailnya dalam contoh.

Untuk menerapkan kebijakan Anda sendiri, Anda harus mengimplementasikan antarmuka berikut.

 struct custom_policy {
    // Called on hash table construction and rehash, min_bucket_count_in_out is the minimum buckets
    // that the hash table needs. The policy can change it to a higher number of buckets if needed 
    // and the hash table will use this value as bucket count. If 0 bucket is asked, then the value
    // must stay at 0.
    explicit custom_policy (std:: size_t & min_bucket_count_in_out);
    
    // Return the bucket [0, bucket_count()) to which the hash belongs. 
    // If bucket_count() is 0, it must always return 0.
    std:: size_t bucket_for_hash (std:: size_t hash) const noexcept ;
    
    // Return the number of buckets that should be used on next growth
    std:: size_t next_bucket_count () const ;
    
    // Maximum number of buckets supported by the policy
    std:: size_t max_bucket_count () const ;
    
    // Reset the growth policy as if the policy was created with a bucket count of 0.
    // After a clear, the policy must always return 0 when bucket_for_hash() is called.
    void clear () noexcept ;
}

Instalasi

Untuk menggunakan peta hopscotch, cukup tambahkan direktori penyertaan ke jalur penyertaan Anda. Ini adalah perpustakaan khusus header .

Jika Anda menggunakan CMake, Anda juga dapat menggunakan target yang diekspor tsl::hopscotch_map dari CMakeLists.txt dengan target_link_libraries .

 # Example where the hopscotch-map project is stored in a third-party directory
add_subdirectory (third-party/hopscotch-map)
target_link_libraries (your_target PRIVATE tsl::hopscotch_map)

Jika proyek telah diinstal melalui make install , Anda juga dapat menggunakan find_package(tsl-hopscotch-map REQUIRED) alih-alih add_subdirectory .

Kode harus bekerja dengan kompiler yang memenuhi standar C++17.

Untuk menjalankan pengujian, Anda memerlukan pustaka Boost Test dan CMake.

git clone https://github.com/Tessil/hopscotch-map.git
cd hopscotch-map/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_hopscotch_map_tests

Penggunaan

API dapat ditemukan di sini.

Semua metode belum didokumentasikan, namun meniru perilaku yang ada di std::unordered_map dan std::unordered_set , kecuali jika ditentukan lain.

Contoh

# include < cstdint >
# include < iostream >
# include < string >
# include < tsl/hopscotch_map.h >
# include < tsl/hopscotch_set.h >

int main () {
    tsl::hopscotch_map<std::string, int > map = {{ " a " , 1 }, { " b " , 2 }};
    map[ " c " ] = 3 ;
    map[ " d " ] = 4 ;
    
    map. insert ({ " e " , 5 });
    map. erase ( " b " );
    
    for ( auto it = map. begin (); it != map. end (); ++it) {
        // it->second += 2; // Not valid.
        it. value () += 2 ;
    }
    
    // {d, 6} {a, 3} {e, 7} {c, 5}
    for ( const auto & key_value : map) {
        std::cout << " { " << key_value. first << " , " << key_value. second << " } " << std::endl;
    }
    
        
    if (map. find ( " a " ) != map. end ()) {
        std::cout << " Found " a " . " << std::endl;
    }
    
    const std:: size_t precalculated_hash = std::hash<std::string>()( " a " );
    // If we already know the hash beforehand, we can pass it in parameter to speed-up lookups.
    if (map. find ( " a " , precalculated_hash) != map. end ()) {
        std::cout << " Found " a " with hash " << precalculated_hash << " . " << std::endl;
    }
    
    
    /*
     * Calculating the hash and comparing two std::string may be slow. 
     * We can store the hash of each std::string in the hash map to make 
     * the inserts and lookups faster by setting StoreHash to true.
     */ 
    tsl::hopscotch_map<std::string, int , std::hash<std::string>, 
                       std::equal_to<std::string>,
                       std::allocator<std::pair<std::string, int >>,
                       30 , true > map2;
                       
    map2[ " a " ] = 1 ;
    map2[ " b " ] = 2 ;
    
    // {a, 1} {b, 2}
    for ( const auto & key_value : map2) {
        std::cout << " { " << key_value. first << " , " << key_value. second << " } " << std::endl;
    }
    
    
    
    
    tsl::hopscotch_set< int > set;
    set. insert ({ 1 , 9 , 0 });
    set. insert ({ 2 , - 1 , 9 });
    
    // {0} {1} {2} {9} {-1}
    for ( const auto & key : set) {
        std::cout << " { " << key << " } " << std::endl;
    }
}

Pencarian heterogen

Kelebihan beban heterogen memungkinkan penggunaan tipe lain selain Key untuk operasi pencarian dan penghapusan selama tipe yang digunakan dapat di-hash dan sebanding dengan Key .

Untuk mengaktifkan kelebihan beban heterogen di tsl::hopscotch_map/set , ID yang memenuhi syarat KeyEqual::is_transparent harus valid. Cara kerjanya sama seperti untuk std::map::find . Anda dapat menggunakan std::equal_to<> atau menentukan objek fungsi Anda sendiri.

Baik KeyEqual dan Hash harus mampu menangani tipe yang berbeda.

# include < functional >
# include < iostream >
# include < string >
# include < tsl/hopscotch_map.h >


struct employee {
    employee ( int id, std::string name) : m_id(id), m_name(std::move(name)) {
    }
    
    // Either we include the comparators in the class and we use `std::equal_to<>`...
    friend bool operator ==( const employee& empl, int empl_id) {
        return empl. m_id == empl_id;
    }
    
    friend bool operator ==( int empl_id, const employee& empl) {
        return empl_id == empl. m_id ;
    }
    
    friend bool operator ==( const employee& empl1, const employee& empl2) {
        return empl1. m_id == empl2. m_id ;
    }
    
    
    int m_id;
    std::string m_name;
};

// ... or we implement a separate class to compare employees.
struct equal_employee {
    using is_transparent = void ;
    
    bool operator ()( const employee& empl, int empl_id) const {
        return empl. m_id == empl_id;
    }
    
    bool operator ()( int empl_id, const employee& empl) const {
        return empl_id == empl. m_id ;
    }
    
    bool operator ()( const employee& empl1, const employee& empl2) const {
        return empl1. m_id == empl2. m_id ;
    }
};

struct hash_employee {
    std:: size_t operator ()( const employee& empl) const {
        return std::hash< int >()(empl. m_id );
    }
    
    std:: size_t operator ()( int id) const {
        return std::hash< int >()(id);
    }
};


int main () {
    // Use std::equal_to<> which will automatically deduce and forward the parameters
    tsl::hopscotch_map<employee, int , hash_employee, std::equal_to<>> map; 
    map. insert ({ employee ( 1 , " John Doe " ), 2001 });
    map. insert ({ employee ( 2 , " Jane Doe " ), 2002 });
    map. insert ({ employee ( 3 , " John Smith " ), 2003 });

    // John Smith 2003
    auto it = map. find ( 3 );
    if (it != map. end ()) {
        std::cout << it-> first . m_name << " " << it-> second << std::endl;
    }

    map. erase ( 1 );



    // Use a custom KeyEqual which has an is_transparent member type
    tsl::hopscotch_map<employee, int , hash_employee, equal_employee> map2;
    map2. insert ({ employee ( 4 , " Johnny Doe " ), 2004 });

    // 2004
    std::cout << map2. at ( 4 ) << std::endl;
}

Serangan Tolak Layanan (DoS).

Selain tsl::hopscotch_map dan tsl::hopscotch_set , perpustakaan menyediakan dua opsi "aman" lagi: tsl::bhopscotch_map dan tsl::bhopscotch_set (semuanya dengan rekan pg ).

Kedua penambahan ini memiliki kompleksitas asimtotik kasus terburuk sebesar O(log n) untuk pencarian dan penghapusan dan kasus terburuk yang diamortisasi sebesar O(log n) untuk penyisipan (diamortisasi karena kemungkinan pengulangan yang akan berada di O(n)) . Bahkan jika fungsi hash memetakan semua elemen ke keranjang yang sama, O(log n) akan tetap berlaku.

Ini memberikan keamanan terhadap serangan tabel hash Deny of Service (DoS).

Untuk mencapai hal ini, versi aman menggunakan pohon pencarian biner untuk elemen yang meluap (lihat detail implementasi) dan karenanya memerlukan elemen tersebut LessThanComparable . Parameter templat Compare tambahan diperlukan.

# include < chrono >
# include < cstdint >
# include < iostream >
# include < tsl/hopscotch_map.h >
# include < tsl/bhopscotch_map.h >

/*
 * Poor hash function which always returns 1 to simulate
 * a Deny of Service attack.
 */
struct dos_attack_simulation_hash {
    std:: size_t operator ()( int id) const {
        return 1 ;
    }
};

int main () {
    /*
     * Slow due to the hash function, insertions are done in O(n).
     */
    tsl::hopscotch_map< int , int , dos_attack_simulation_hash> map;
    
    auto start = std::chrono::high_resolution_clock::now ();
    for ( int i= 0 ; i < 10000 ; i++) {
        map. insert ({i, 0 });
    }
    auto end = std::chrono::high_resolution_clock::now ();
    
    // 110 ms
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    std::cout << duration. count () << " ms " << std::endl;
    
    
    
    
    /*
     * Faster. Even with the poor hash function, insertions end-up to
     * be O(log n) in average (and O(n) when a rehash occurs).
     */
    tsl::bhopscotch_map< int , int , dos_attack_simulation_hash> map_secure;
    
    start = std::chrono::high_resolution_clock::now ();
    for ( int i= 0 ; i < 10000 ; i++) {
        map_secure. insert ({i, 0 });
    }
    end = std::chrono::high_resolution_clock::now ();
    
    // 2 ms
    duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    std::cout << duration. count () << " ms " << std::endl;
}