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程式設計
字典與集合
|
79
字典與集合如何運作?
字典與集合使用
雜湊表
hash table
)達成它們的
O(1)
查詢與插入,之所以有這種效
率,是因為它們巧妙地運用雜湊函式,將任意鍵(亦即,字串或物件)轉換成串列索
引,該雜湊函式與串列稍後被用來即時判斷任何特定資料片段究竟位在何處,而不需要
進行搜尋。透過將資料的鍵轉換成某種能夠像串列索引那樣運用的東西,我們可以得到
與串列相同的效能。另外,代替必須經由數字索引參照資料(數字索引本身隱含著某種
資料順序),我們可以透過這個任意鍵參照它。
插入與擷取
為了從頭開始建立雜湊表,我們首先配置一些記憶體,類似我們為陣列所做的那樣。對
陣列來說,如果我們想要插入資料,只要找出最小的未使用的 bucket,並將資料插入那
裡即可(必要時,重新調整尺寸)。就雜湊表而言,我們必須先釐清,在這個連續記憶
體區塊裡,資料要放在哪裡。
新資料的安置視兩個特性而定︰鍵的雜湊值,以及該值跟其他物件的比較。這是因為當
我們插入資料時,鍵會先被 hashed(雜湊化)與 masked(遮罩處理),好讓它變成陣
列裡的有效索引
2
mask(遮罩)確保雜湊值(可以是任何整數)落在被配置的 bucket
數量內。因此,如果我們已經配置了 8 個記憶體區塊,而我們的雜湊值是
28975
,我們
將該 bucket 視為位在索引
28975
&
0b111
=
7
的位置。不過,如果我們的字典已經成長到
需要 512 個記憶體區塊,遮罩就會變成
0b111111111
(並且,在此案例裡,我們會將該
bucket
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