資料結構›Ch8 雜湊第 2 題／共 37 題
2. Hash Table、Load Factor、Separate Chaining
#DS-08-002易Hash TableLoad FactorSeparate Chaining
Most hash table implementations (such as Java's HashMap) resize the underlying array when the load factor exceeds a certain threshold (typically 0.75). Why is this resizing operation necessary for a hash table that uses separate chaining?
參考答案與解析
答案 (C)：separate chaining 下，負載因子 α 越高代表平均每個桶裡串接的元素越多，若不擴容，串列長度會隨資料量線性增長，find/insert 的平均時間會從 O(1) 慢慢退化成 O(n)；擴容（重新雜湊到更大的表）就是為了把平均串列長度壓回常數，維持 O(1) 平均存取時間。(A)(B)(D)(E) 都不是 separate chaining 需要擴容的真正原因（chaining 本身允許 α>1，不會「無法插入」；也不會重新排序或保證記憶體連續）。
📄 台大115
▤完整推導請見《WH 資工筆記 · 資料結構》Ch8 雜湊