Load Factor
লোড ফ্যাক্টর
Hash table-এ entry সংখ্যাকে bucket সংখ্যা দিয়ে ভাগ — α = n/m বাড়লে collision আর probe chain বাড়ে, তাই fixed threshold-এ resize হয়।
also: load factor alpha, fill ratio
α = n / m n = entry সংখ্যা, m = bucket সংখ্যা| α | অর্থ |
|---|---|
| α ≈ 0 | bucket প্রায় ফাঁকা, memory নষ্ট |
| α > 1 | open addressing-এ অসম্ভব — slot-এর চেয়ে entry বেশি |
| α → 1 | chain/probe লম্বা, lookup ধীর |
Chaining-এ গড় successful lookup প্রায় 1 + α/2; open addressing-এ linear probing ছোট α-তেই খরচ বাড়াতে শুরু করে। তাই Python dict α > 2/3, Java HashMap α > 0.75 হলে resize করে।
Resize মানে পুরো table rehash — এক operation-এর দৃষ্টিতে দামি, কিন্তু capacity doubling করলে amortized cost O(1)-ই থাকে।