Skip to Main Content
高效能PYTHON程式設計
book

高效能PYTHON程式設計

by Micha Gorelick, Ian Ozsvald
August 2015
Intermediate to advanced content levelIntermediate to advanced
384 pages
7h 42m
Chinese
GoTop Information, Inc.
Content preview from 高效能PYTHON程式設計
字典與集合
|
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
)來說,雜湊值僅僅奠基於它們所代表之數值的位元值。
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

流畅的Python

流畅的Python

Luciano Ramalho
手把手教会你linux

手把手教会你linux

桑德.范.乌格特

Publisher Resources

ISBN: 9789863477105