দুটি স্বতন্ত্র কী একই বাকেটে হ্যাশ করতে পারে — একটি সংঘর্ষ। হ্যাশ টেবিলগুলি সংঘর্ষ সমাধান করে এবং বাকেটগুলি ভিড় হওয়ার আগে পুনরায় আকার পরিবর্তন করে গড়ে O(1) থাকে, যা লোড ফ্যাক্টর দ্বারা নিয়ন্ত্রিত হয়।
Separate chaining: each bucket holds a list
[3] -> ("cat",9) -> ("rat",2) # both hashed to 3
Open addressing: probe to the next free slot
hash=3 taken -> try 4 -> try 5 ... (linear probing)
load factor α = number_of_entries / number_of_buckets
α rises -> more collisions -> slower lookups
When α exceeds a threshold (e.g. 0.75):
-> allocate a bigger array (usually 2x)
-> REHASH every existing key into new buckets
# Conceptual resize
def _resize(self):
old = self.buckets
self.buckets = [None] * (len(old) * 2)
for entry in all_entries(old):
self._insert(entry.key, entry.value) # rehash into new array
| অপারেশন | গড় | সবচেয়ে খারাপ |
|---|---|---|
| অনুসন্ধান / সন্নিবেশ / মুছে ফেলা | O(1) | O(n) |
| একক পুনরায় আকার পরিবর্তন | — | O(n) |
| সন্নিবেশ (বিলম্বিত, পুনরায় আকার পরিবর্তনের সাথে) | O(1) | — |
একটি পুনরায় আকার পরিবর্তন O(n) কিন্তু খুব কমই ঘটে, তাই এটি প্রতিটি সন্নিবেশের জন্য O(1) বিলম্বিত হয়।
এই অভ্যন্তরীণ বিবরণগুলি ব্যাখ্যা করে কেন হ্যাশ ম্যাপগুলি গড়ে দ্রুত কিন্তু O(n) এ স্পাইক করতে পারে — কর্মক্ষমতা-সংবেদনশীল কোড এবং বিরোধী-ইনপুট (হ্যাশ-ফ্লাডিং) প্রতিরক্ষার জন্য গুরুত্বপূর্ণ।
লোড ফ্যাক্টর বোঝা প্রকৃত লাইব্রেরি দ্বারা প্রকাশিত মেমরি/গতি টিউনিং নবগুলি ব্যাখ্যা করে।