
字典與集合
|
83
重調尺寸
隨著越來越多項目被插入雜湊表,表格本身必須重新調整尺寸才能夠容納那些資料。可
以證明,不超過 2/3 滿的表格會有最佳的空間效益,同時不會有過多的雜湊衝突發生。
因此,當表格到達這個臨界點時,它會被增長。為了這麼做,更大的表格被配置(亦
即,記憶體裡有更多 bucket 被保留),遮罩被調整,以適應新表格,並且舊表格的所有
元素被重新插入新表格。這需要重新計算索引,因為變更的遮罩會改變最後的索引。因
此,重新調整成更大尺寸的雜湊表可能是一項十分昂貴的工作!然而,因為只有在表
格太小時才需要重調尺寸,而不是每次插入都要做,所以插入的攤餘成本(amortized
cost)仍然是
O(1)
。
預設上,字典或集合的最小尺寸是 8(亦即,如果你只儲存 3 個值,Python 仍然會配置
8 個元素)。在重調尺寸時,bucket 的數量呈 4 倍增加,直到 50,000 個元素,之後,就
呈 2 倍增加。以下是可能的尺寸︰
8, 32, 128, 512, 2048, 8192, 32768, 131072, 262144, ...
注意,重調尺寸可能會讓雜湊表變大或變小,也就是說,如果雜湊表中有夠多元素被刪
除,那麼表格的尺寸就能夠被縮小,不過,重調尺寸
只會在插入期間發生
。
雜湊函式與 Entropy
Python 裡的物件一般是可雜湊化的,因為它們已經內建相關聯的
__hash__
與
__cmp__
函
式。對數值型別(
int
與
float
)來說,雜湊值僅僅奠基於它們所代表之數值的位元值。