MIT 6.006 Introduction to Algorithms 9.1
9. Table Doubling, Karp-Rabin
提要
上一堂課，我們提到，Hashing with Chaining 如果控制得好（Table Size m = O ( n )），我們可以得到 Search Time Cost = O ( 1 )
但在實際應用情況，n 其實是不斷在變化的，隨著你對 Dictionary 做 Insert / Delete，都會使 n 變大變小。這也是我們這堂課要克服的。
結論
為了保持 Insert / Delete / Search Time Cost = O ( 1 )的特性，必須動態調整 Table Size m，並依據 Table Doubling 去調整：
Table Doubling
- 當 n = m 時，創建新的 Table Size m’ = 2 * m
- 當 n = m / 4 時，創建新的 Table Size m’ = m / 2
動態調整 Table Size m
隨著 Dictionary 不停的 Insert Object，n 越來越大，當 n = m 時，我們需要一個新的 Table 來存放資料。我們需要做grow table：
Grow Table
- make a new table T’, size = m’
- build new hash method h’
- Rehash for item in the old table T and insert to T’
每次更動 Table size，你所需花的成本可不少（整個 Table 重新做一次 Hashing…），這會使整體的 cost 提高，我們不希望這樣。
我們必須謹慎決定新的 Table Size m’ 應該是多少？才能保持最好的效率（不用每次insert就需要grow）。
但我們希望，除非必要，否則不要變動 size。
Grow Table Cost = O ( n + m + m’ )
需要花費 m’ 時間建立新的 Table，並且 run 過 m 個 slot 以及 n 個 chaining 取值並填入資料。
新的 Table Size m’ 要多少比較合理？
假設有 n 個 Insert 動作，m’ 應該要是多少有最佳解？
舉下面兩個例子：
- m’ = m + 1 （極端的例子，每次 insert 都要重構一次 table）
- m’ = 2 * m
從上面的計算來看，當 m’ = 2m ：
Total Grow Table Costs = O( n ) 是最好的結果。
因為有 n 次的 insert ，平均每次 insert 是 O( 1 ) 的 constant grow cost：
Average Grow Table Cost = O( n ) / n = O( 1 )
當然這只是單純考慮到 Insert 的動作，我們還必須考慮到 delete 動作。
Delete Operation
隨著 Dictionary 不停的 Delete Object，n 越來越小，當 n 變小多少時做 shrink table，才有最好的效果？（Average Shrink Table Cost = O( 1 )）
Shrink Table
- m’ = m / 2
答案是：當 m = n / 4 時（證明須參考教科書，影片未描述）
Table Doubling 定義
當 n = m 時，調整 Table Size m’ = 2 * m
當 n = m / 4 時，調整 Table Size m’ = m / 2
花費每次不一樣，那平均呢？
在一般使用下，Dictionary 在 Insert / Delete / Search 都是 O( 1 )。但由於需要維護 Table Size m = O( n )，所以在 n = m 時需要做grow Table，這會使單次的成本提高為 O( n + m + m’ )。導致每次的動作 cost 其實不太一樣。
如果將這些額外的花費取平均來看呢？
從上面的最佳解答 Table Doubling 的條件下，我們還是可以達到：
Average Operation Cost = O( 1 ) Amortization
平均花費 Amortization T( n )：
1. T ( n ) are average cost where average for all operation
2. It Take T( n ) cost per operation ( k times operation take ≤ k * T(n) time)
這些昂貴的成本只有在某幾次需要，其他時間情況下都很快速，所以平均下來還是很快！