hopscotch map
v2.3.1
مكتبة خريطة الحجلة هي تطبيق C++ لخريطة التجزئة السريعة ومجموعة التجزئة باستخدام العنونة المفتوحة وتجزئة الحجلة لحل التصادمات. إنها بنية بيانات صديقة لذاكرة التخزين المؤقت وتقدم أداء أفضل من 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 كافيين في معظم الحالات ويجب أن يكونا اختيارك الافتراضي حيث أن أداءهما أفضل بشكل عام.
يمكن العثور على نظرة عامة على تجزئة الحجلة وبعض تفاصيل التنفيذ هنا.
يمكن العثور هنا على معيار 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) عند عمليات البحث والحذف مما يجعل هذه الفئات مقاومة لهجمات رفض الخدمة (DoS) على جدول التجزئة (انظر التفاصيل في المثال).-fno-exceptions في Clang وGC، بدون خيار /EH على MSVC أو ببساطة عن طريق تحديد TSL_NO_EXCEPTIONS ). يتم استخدام std::terminate لاستبدال تعليمات throw عند تعطيل الاستثناءات.std::unordered_map و std::unordered_set .std::unordered_map يحاول tsl::hopscotch_map الحصول على واجهة مشابهة لـ std::unordered_map ، ولكن توجد بعض الاختلافات.
erase ، تؤدي إلى إبطال جميع التكرارات (راجع واجهة برمجة التطبيقات لمزيد من التفاصيل).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 . تحافظ هذه السياسة على حجم مصفوفة الجرافة الخاصة بجدول التجزئة إلى قوة اثنين. يسمح هذا القيد للسياسة بتجنب استخدام عملية modulo البطيئة لتعيين تجزئة إلى مجموعة، بدلاً من hash % 2 n ، فإنها تستخدم hash & (2 n - 1) (راجع modulo السريع). سريع ولكن هذا قد يتسبب في الكثير من التصادمات مع وظيفة التجزئة الضعيفة حيث أن المودولو الذي يتمتع بقوة اثنين يخفي فقط البتات الأكثر أهمية في النهاية.tsl::(b)hopscotch_pg_map/set . تحافظ السياسة على حجم مجموعة المجموعة الخاصة بجدول التجزئة إلى رقم أولي. عند تعيين تجزئة إلى مجموعة، فإن استخدام رقم أولي كمعيار سيؤدي إلى توزيع أفضل للتجزئة عبر المجموعات حتى مع وجود وظيفة تجزئة ضعيفة. للسماح للمترجم بتحسين تشغيل الوحدة النمطية، تستخدم السياسة جدول بحث يحتوي على وحدات أولية ثابتة (راجع واجهة برمجة التطبيقات لمزيد من التفاصيل). أبطأ من 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 ;
}لاستخدام خريطة الحجلة، ما عليك سوى إضافة دليل التضمين إلى مسار التضمين الخاص بك. إنها مكتبة رأسية فقط .
إذا كنت تستخدم 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 يمكن العثور على واجهة برمجة التطبيقات هنا.
لم يتم توثيق كافة التوابع بعد، لكنها تكرر سلوك تلك الموجودة في 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، راجع ملف الترخيص للحصول على التفاصيل.
