Module ১০ · unordered_set আর unordered_map: hashing, collision আর anti-hash test
ভেতরের কথা: bucket-এর chain, prime সংখ্যার bucket আর anti-hash test
Proপড়া
Kenji-র contest solution সংখ্যাগুলো রাখত একটা unordered_set<long long>-এ, আর 85,000টা এলোমেলো সংখ্যা ঢুকে যেত 10 ms-এর মধ্যেই। Contest শেষ হওয়ার পরে এক প্রতিদ্বন্দ্বী একটা test যোগ করল: 85,000টা সংখ্যা, প্রত্যেকটা 85,229-এর গুণিতক। ওই test-এ Compiler Explorer-এ একই insert-গুলো নিল 15.5 থেকে 19.2 সেকেন্ড। একই container, একই সংখ্যক key, তবু হাজার গুণেরও বেশি ধীর। Maria ঠিক সেই প্রশ্নটা করে, যার উত্তর এই lesson: "কিন্তু কেন? একটা সংখ্যার গুণিতক একটা hash table-কে ভেঙে দেয় কী করে?"
আপনার জন্য এই lesson টা খোলা কি না দেখা হচ্ছে…
ভেতরের কথা: bucket-এর chain, prime সংখ্যার bucket আর anti-hash test এর ভেতরে কী আছে
- সব node জুড়ে একটাই list, আর bucket-গুলো সেই list-এর ভেতরে দেখায়
- একটা node: একটা link, key-টা, আর কখনো কখনো hash code
- বড় হওয়া: অন্তত দ্বিগুণ, আর একটা prime সংখ্যা
- Rehash প্রতিটা node নতুন করে link করে, কিছুই copy করে না
- Performance lab: unordered_map বনাম map
- Anti-hash test: একটা bucket-কে তাক করা key
- বাঁচার দুইটা উপায়: কারও জানা নেই এমন একটা seed, নয়তো একটা tree
- স্থির hash, যত চালাকই হোক, বাঁচার উপায় না