卷別

資料結構與演算法

選擇

國立臺灣大學 2026 · 考試 · 第 15 題

(4 points) 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 important for a hash table that uses separate chaining?

(A)
Saturation: To prevent the table from reaching a load factor of 1.0, at which point inserting a new element would be impossible.
(B)
Ordering: To resort the keys alphabetically during the transfer, enabling the use of binary search for faster lookups.
(C)
Complexity: To prevent the average length of the linked lists (collision chains) from growing linearly with the number of elements, thereby maintaining $O(1)$ average access time.
(D)
Uniqueness: To redistribute the keys across a larger range so that all existing collisions are permanently eliminated.
(E)
Memory continuity: To ensure that all elements in the linked lists are stored in adjacent memory addresses, minimizing CPU cache misses and fragmentation.

標準解析

AI 已複查