上一節說過， 擴展或收縮哈希表需要將?`ht[0]`?里面的所有鍵值對 rehash 到?`ht[1]`?里面， 但是， 這個 rehash 動作并不是一次性、集中式地完成的， 而是分多次、漸進式地完成的。 這樣做的原因在于， 如果?`ht[0]`?里只保存著四個鍵值對， 那么服務器可以在瞬間就將這些鍵值對全部 rehash 到?`ht[1]`?； 但是， 如果哈希表里保存的鍵值對數量不是四個， 而是四百萬、四千萬甚至四億個鍵值對， 那么要一次性將這些鍵值對全部 rehash 到?`ht[1]`?的話， 龐大的計算量可能會導致服務器在一段時間內停止服務。 因此， 為了避免 rehash 對服務器性能造成影響， 服務器不是一次性將?`ht[0]`?里面的所有鍵值對全部 rehash 到?`ht[1]`?， 而是分多次、漸進式地將?`ht[0]`?里面的鍵值對慢慢地 rehash 到?`ht[1]`?。 以下是哈希表漸進式 rehash 的詳細步驟： 1. 為?`ht[1]`?分配空間， 讓字典同時持有?`ht[0]`?和?`ht[1]`?兩個哈希表。 2. 在字典中維持一個索引計數器變量?`rehashidx`?， 并將它的值設置為?`0`?， 表示 rehash 工作正式開始。 3. 在 rehash 進行期間， 每次對字典執行添加、刪除、查找或者更新操作時， 程序除了執行指定的操作以外， 還會順帶將?`ht[0]`?哈希表在?`rehashidx`?索引上的所有鍵值對 rehash 到?`ht[1]`?， 當 rehash 工作完成之后， 程序將?`rehashidx`?屬性的值增一。 4. 隨著字典操作的不斷執行， 最終在某個時間點上，?`ht[0]`?的所有鍵值對都會被 rehash 至?`ht[1]`?， 這時程序將?`rehashidx`?屬性的值設為?`-1`?， 表示 rehash 操作已完成。 漸進式 rehash 的好處在于它采取分而治之的方式， 將 rehash 鍵值對所需的計算工作均灘到對字典的每個添加、刪除、查找和更新操作上， 從而避免了集中式 rehash 而帶來的龐大計算量。 圖 4-12 至圖 4-17 展示了一次完整的漸進式 rehash 過程， 注意觀察在整個 rehash 過程中， 字典的?`rehashidx`?屬性是如何變化的。       ## 漸進式 rehash 執行期間的哈希表操作 因為在進行漸進式 rehash 的過程中， 字典會同時使用?`ht[0]`?和?`ht[1]`?兩個哈希表， 所以在漸進式 rehash 進行期間， 字典的刪除（delete）、查找（find）、更新（update）等操作會在兩個哈希表上進行： 比如說， 要在字典里面查找一個鍵的話， 程序會先在?`ht[0]`?里面進行查找， 如果沒找到的話， 就會繼續到?`ht[1]`?里面進行查找， 諸如此類。 另外， 在漸進式 rehash 執行期間， 新添加到字典的鍵值對一律會被保存到?`ht[1]`?里面， 而?`ht[0]`?則不再進行任何添加操作： 這一措施保證了?`ht[0]`?包含的鍵值對數量會只減不增， 并隨著 rehash 操作的執行而最終變成空表。