hopscotch map
v2.3.1
ไลบรารีแผนที่ hopscotch คือการนำ C++ ไปใช้ของแผนที่แฮชแบบรวดเร็วและชุดแฮชโดยใช้การกำหนดที่อยู่แบบเปิดและการแฮชแบบ hopscotch เพื่อแก้ไขการชนกัน เป็นโครงสร้างข้อมูลที่เป็นมิตรกับแคชซึ่งให้ประสิทธิภาพที่ดีกว่า std::unordered_map ในกรณีส่วนใหญ่ และมีความคล้ายคลึงกับ google::dense_hash_map อย่างใกล้ชิด ในขณะที่ใช้หน่วยความจำน้อยกว่าและมีฟังก์ชันการทำงานมากกว่า
ไลบรารีมีคลาสหลักดังต่อไปนี้: tsl::hopscotch_map , tsl::hopscotch_set , tsl::hopscotch_pg_map และ tsl::hopscotch_pg_set สองอันแรกเร็วกว่าและใช้พลังของนโยบายการเติบโตสองอัน สองอันสุดท้ายใช้นโยบายการเติบโตที่สำคัญแทน และสามารถรับมือได้ดีขึ้นด้วยฟังก์ชันแฮชที่ไม่ดี ใช้เวอร์ชันไพรม์หากมีโอกาสที่จะเกิดรูปแบบซ้ำในบิตล่างของแฮชของคุณ (เช่น คุณกำลังจัดเก็บพอยน์เตอร์ด้วยฟังก์ชันแฮชข้อมูลเฉพาะตัว) ดูนโยบายการเติบโตสำหรับรายละเอียด
นอกเหนือจากคลาสเหล่านี้แล้ว ไลบรารียังมี tsl::bhopscotch_map , tsl::bhopscotch_set , tsl::bhopscotch_pg_map และ tsl::bhopscotch_pg_set คลาสเหล่านี้มีข้อกำหนดเพิ่มเติมสำหรับคีย์ ซึ่งจะต้องเป็น LessThanComparable แต่คลาสเหล่านี้มีขอบเขตบนเชิงเส้นกำกับที่ดีกว่า โปรดดูรายละเอียดในตัวอย่าง อย่างไรก็ตาม หากคุณไม่มีข้อกำหนดเฉพาะ (ความเสี่ยงของการโจมตีแฮช DoS) tsl::hopscotch_map และ tsl::hopscotch_set ควรเพียงพอในกรณีส่วนใหญ่ และควรเป็นตัวเลือกเริ่มต้นของคุณเนื่องจากทำงานได้ดีกว่าโดยทั่วไป
คุณสามารถดูภาพรวมของการแฮชแบบ hopscotch และรายละเอียดการใช้งานบางส่วนได้ที่นี่
คุณสามารถดู เกณฑ์มาตรฐาน ของ tsl::hopscotch_map เทียบกับแผนที่แฮชอื่นๆ ได้ที่นี่ หน้านี้ยังให้คำแนะนำบางประการเกี่ยวกับโครงสร้างตารางแฮชที่คุณควรลองใช้สำหรับกรณีการใช้งานของคุณ (มีประโยชน์หากคุณหลงลืมไปเล็กน้อยกับการใช้งานตารางแฮชหลายตารางในเนมสเปซ tsl )
tsl::hopscotch_map จาก CMakeLists.txt ได้อีกด้วยfind ด้วยประเภทที่แตกต่างจาก Key (เช่น หากคุณมีแผนที่ที่ใช้ std::unique_ptr<foo> เป็นคีย์ คุณสามารถใช้ foo* หรือ std::uintptr_t เป็นพารามิเตอร์คีย์เพื่อ find โดยไม่ต้องสร้าง std::unique_ptr<foo> ดูตัวอย่าง)precalculated_hash ใน API)tsl::bhopscotch_map และ tsl::bhopscotch_set ให้กรณีที่แย่ที่สุดของ O(log n) ในการค้นหาและการลบ ทำให้คลาสเหล่านี้ทนทานต่อการโจมตีตารางแฮช Deny of Service (DoS) (ดูรายละเอียดในตัวอย่าง)-fno-exceptions บน Clang และ GCC โดยไม่มีตัวเลือก /EH บน MSVC หรือเพียงแค่กำหนด TSL_NO_EXCEPTIONS ) std::terminate ใช้แทนคำสั่ง throw เมื่อข้อยกเว้นถูกปิดใช้งานstd::unordered_map และ std::unordered_set อย่างใกล้ชิดstd::unordered_map tsl::hopscotch_map พยายามที่จะมีส่วนต่อประสานที่คล้ายกับ std::unordered_map แต่มีความแตกต่างบางประการ
erase จะทำให้ตัววนซ้ำทั้งหมดใช้ไม่ได้ (ดู API สำหรับรายละเอียด)operator*() และ operator->() ส่งคืนการอ้างอิงและตัวชี้ไปที่ const std::pair<Key, T> แทน std::pair<const Key, T> ทำให้ค่า T ไม่สามารถแก้ไขได้ ในการแก้ไขค่าคุณต้องเรียกใช้เมธอด value() ของตัววนซ้ำเพื่อรับการอ้างอิงที่ไม่แน่นอน ตัวอย่าง: 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
}bucket_size , bucket , ... ) ความแตกต่างเหล่านี้ยังใช้ระหว่าง std::unordered_set และ tsl::hopscotch_set
การรับประกันความปลอดภัยของเธรดและข้อยกเว้นจะเหมือนกับ std::unordered_map/set (เช่น เป็นไปได้ที่จะมีตัวอ่านหลายตัวโดยไม่มีตัวเขียน)
ไลบรารีรองรับนโยบายการเติบโตหลายรายการผ่านพารามิเตอร์เทมเพลต GrowthPolicy ห้องสมุดมีนโยบายสามประการให้ไว้ แต่คุณสามารถนำไปใช้เองได้อย่างง่ายดายหากจำเป็น
tsl::(b)hopscotch_map/set นโยบายนี้จะรักษาขนาดของอาร์เรย์ที่เก็บข้อมูลของตารางแฮชให้มีกำลัง 2 ข้อจำกัดนี้อนุญาตให้นโยบายหลีกเลี่ยงการใช้การดำเนินการแบบโมดูโลที่ช้าเพื่อแมปแฮชกับที่เก็บข้อมูล แทนที่จะเป็น hash % 2 n แต่จะใช้ hash & (2 n - 1) (ดูโมดูโลแบบเร็ว) รวดเร็ว แต่สิ่งนี้อาจทำให้เกิดการชนกันมากมายด้วยฟังก์ชันแฮชที่ไม่ดี เนื่องจากโมดูโลที่มีกำลังสองเท่านั้นที่จะปกปิดบิตที่สำคัญที่สุดในตอนท้ายtsl::(b)hopscotch_pg_map/set นโยบายจะรักษาขนาดของอาร์เรย์ที่เก็บข้อมูลของตารางแฮชให้เป็นจำนวนเฉพาะ เมื่อทำการแมปแฮชกับบัคเก็ต การใช้เลขเฉพาะเป็นโมดูโลจะส่งผลให้การกระจายแฮชทั่วทั้งบัคเก็ตดีขึ้น แม้ว่าจะมีฟังก์ชันแฮชที่ไม่ดีก็ตาม เพื่อให้คอมไพเลอร์เพิ่มประสิทธิภาพการดำเนินการแบบโมดูโล นโยบายจะใช้ตารางการค้นหาที่มีโมดูลัสเฉพาะค่าคงที่ (ดู API สำหรับรายละเอียด) ช้ากว่า tsl::hh::power_of_two_growth_policy แต่มีความปลอดภัยมากกว่า หากคุณพบว่าประสิทธิภาพไม่ดี ให้ตรวจสอบ overflow_size() หากไม่ใช่ศูนย์ คุณอาจเกิดการชนกันของแฮชจำนวนมาก เปลี่ยนฟังก์ชันแฮชเพื่อให้มีความสม่ำเสมอมากขึ้นหรือลองใช้นโยบายการเติบโตอื่น (ส่วนใหญ่เป็น tsl::hh::prime_growth_policy ) น่าเสียดายที่บางครั้งการป้องกันตัวเองจากการชนกันเป็นเรื่องยาก (เช่น การโจมตี DoS บนแผนที่แฮช) หากจำเป็น ให้ตรวจสอบ tsl::bhopscotch_map/set ซึ่งมีสถานการณ์กรณีที่เลวร้ายที่สุดของ O(log n) ในการค้นหาแทนที่จะเป็น O(n) ดูรายละเอียดในตัวอย่าง
หากต้องการใช้นโยบายของคุณเอง คุณจะต้องใช้อินเทอร์เฟซต่อไปนี้
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 ;
}หากต้องการใช้ hopscotch-map เพียงเพิ่มไดเร็กทอรีรวมลงในพาธรวมของคุณ มันเป็นห้องสมุด ส่วนหัวเท่านั้น
หากคุณใช้ CMake คุณยังสามารถใช้ tsl::hopscotch_map เป้าหมายที่ส่งออกจาก CMakeLists.txt พร้อมด้วย 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) หากโปรเจ็กต์ได้รับการติดตั้งผ่าน make install คุณสามารถใช้ find_package(tsl-hopscotch-map REQUIRED) แทน add_subdirectory
รหัสควรทำงานร่วมกับคอมไพเลอร์ที่เป็นไปตามมาตรฐาน C ++ 17
หากต้องการรันการทดสอบ คุณจะต้องมีไลบรารี Boost Test และ 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 API สามารถพบได้ที่นี่
วิธีการทั้งหมดยังไม่ได้จัดทำเป็นเอกสาร แต่จะจำลองพฤติกรรมของวิธีการใน std::unordered_map และ std::unordered_set ยกเว้นในกรณีที่ระบุไว้เป็นอย่างอื่น
# 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;
}
} การโอเวอร์โหลดที่แตกต่างกันทำให้สามารถใช้ประเภทอื่นนอกเหนือจาก Key ในการค้นหาและลบได้ ตราบใดที่ประเภทที่ใช้นั้นสามารถแฮชได้และเทียบเคียงได้กับ Key
หากต้องการเปิดใช้งานโอเวอร์โหลดต่างกันใน tsl::hopscotch_map/set รหัสที่ผ่านการรับรอง KeyEqual::is_transparent จะต้องถูกต้อง มันทำงานในลักษณะเดียวกับ std::map::find คุณสามารถใช้ std::equal_to<> หรือกำหนดวัตถุฟังก์ชันของคุณเองได้
ทั้ง KeyEqual และ Hash จะต้องสามารถจัดการกับประเภทที่แตกต่างกันได้
# 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;
} นอกจาก tsl::hopscotch_map และ tsl::hopscotch_set แล้ว ไลบรารียังมีตัวเลือก "ปลอดภัย" อีกสองตัว: tsl::bhopscotch_map และ tsl::bhopscotch_set (ทั้งหมดนี้มี pg เหมือนกัน)
การเพิ่มเติมทั้งสองนี้มีความซับซ้อนเชิงซีมโทติคกรณีที่เลวร้ายที่สุดของ O(log n) สำหรับการค้นหาและการลบ และกรณีที่แย่ที่สุดที่ตัดจำหน่ายของ O(log n) สำหรับการแทรก (ตัดจำหน่ายเนื่องจากความเป็นไปได้ของการปรับปรุงใหม่ซึ่งจะอยู่ใน O(n)) . แม้ว่าฟังก์ชันแฮชจะแมปองค์ประกอบทั้งหมดไปยังที่เก็บข้อมูลเดียวกัน แต่ O(log n) จะยังคงคงอยู่
สิ่งนี้ให้ความปลอดภัยจากการโจมตีตารางแฮชปฏิเสธการบริการ (DoS)
เพื่อให้บรรลุเป้าหมายนี้ เวอร์ชัน ที่ปลอดภัย จะใช้แผนผังการค้นหาแบบไบนารีสำหรับองค์ประกอบที่ล้น (ดูรายละเอียดการใช้งาน) และดังนั้นจึงจำเป็นต้องมีองค์ประกอบให้เป็น LessThanComparable จำเป็นต้องมีพารามิเตอร์เทมเพลต Compare เพิ่มเติม
# 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;
} รหัสนี้ได้รับอนุญาตภายใต้ใบอนุญาต MIT โปรดดูรายละเอียดในไฟล์ LICENSE
