Hash Table
হ্যাশ টেবিল
Key-কে hash function দিয়ে array index-এ বসানো key-value store — গড়ে O(1) lookup, insert, delete; collision সামলায় chaining বা open addressing।
also: hashtable, hash map
মূল ভাবনা এক লাইনে:
index = hash(key) % capacityদুই key এক index-এ পড়লে সেটা collision; সামলানোর দুই রাস্তা:
| কৌশল | পদ্ধতি | গড় lookup |
|---|---|---|
| Chaining | প্রতি bucket-এ linked list | O(1 + α) |
| Open addressing | ভরা slot পেলে পরের probe | O(1/(1−α)) |
এখানে α হলো load factor — entry সংখ্যা ÷ bucket সংখ্যা। α বাড়লে chain/probe লম্বা হয়, তাই threshold ছুঁলে table বড় করে সব entry rehash করতে হয়।
Worst case (সব key এক bucket-এ) O(n); ভালো hash function আর ঠিক সময়ে resize-ই ওই গড় O(1)-টা ধরে রাখে।