Python 內置數據結構

Python 內置了強大的數據結構，比如列表、元組、字典，讓 Python 開發者處理數據時可以信手拈來，但是正是因為 Python 做了太多，讓我們忽視了很多細節，本文通過解析 CPython 源碼，介紹 Python 的內置數據結構的設計與實現。

Python 序列類型概覽

Python 標準庫用 C 實現了豐富的序列類型。根據存放的內容可以分為容器序列和扁平序列：

容器序列：list、tuple、collections.deque扁平序列：str、bytes、bytearray、memoryview、array.array

簡單講，容器序列存放的是對任意對象的引用；扁平序列存放的是值，也就是說扁平序列只能存放字元、位元組、數值等基礎類型。接下來我們從 CPython 實現的角度出發，詳細講解 Python 中最常見的兩種序列——列表和元組。

序列之列表

list 作為 Python 中最常用的內置數據結構，運用十分廣泛且靈活。首先 list 是個可變序列，可以自由增加或刪除元素，其次 list 可以存放任意類型的元素，光這兩個特點就足夠程序員開心的了。下面看看 list 是如何實現的。

列表的實現

首先看看 CPython 中對 list 結構的定義，其對象介面定義在 中：

其中 由下面的 定義，而其中的 記錄的是實際使用的內存的數量； 指向了列表所在內存的首地址； 則記錄了當前列表中可存放的所有元素的數量總和。

每一次需要申請內存的時候，總會申請大塊內存，將申請的內存大小記錄在 中，而實際使用的內存大小記錄在 中。這樣做就很高效的實現了內存管理，可以頻繁地進行插入、刪除等操作。

list 的所有操作都是通過指針 實現的。指針指向存儲對象的內存地址，也就實現了存放任意類型的元素這一功能。list 的實現定義在 中，代碼就不貼出來了，鏈接：https://github.com/python/cpython/blob/master/Objects/listobject.c。

CPython 在列表中維護了一個緩衝池 ，裡面存放了可用的 list 對象，總長度為 80。創建列表前先在這個緩衝池中查找可用對象，如果有直接喚醒，對其 分配空間；如果沒有則另外申請內存，再對其 分配空間。相對應的，銷毀 list 時，先銷毀其 指向的空間，再檢查 中是否有空間，如果有將其放入以供下次使用；如果沒有直接銷毀。

正如前面所說，list 的所有操作都是通過 實現的，那麼基於 C 中指針的了解，不難理解列表的索引、修改等操作，這裡不贅述。

需要注意的是，insert 和 append 操作都對列表當前的使用內存產生影響。所以在插入元素前調用 函數來調整內存。調整過程為：

當 時，直接賦值，即 ；

否則調用 重新分配內存並縮小 ，以實現內存空間的最大利用。

而 insert 和 append 的區別在於：insert 將 i (需要插入的位置) 向後的元素向後順移，再在 i 處插入；append 在 處插入。

而刪除操作，需要遍歷整個列表，找到滿足條件的元素時，將其刪除，並將後面位置的元素前移一位。

了解了列表的基本操作之後，我們知道列表的索引、修改和 append 操作的複雜度為 ，而 insert 和刪除需要遍歷，複雜度為 。

序列之元組

Python 中的元組以其不可變特徵聞名，可以理解成是一個不可變的列表，下面看看元組的底層實現。

元組的實現

元組的結構定義在 中：

與列表類似， 中的 記錄元組長度（一經創建不可改變）； 是存放元組元素的指針數組。

元組的相關操作定義在 中，鏈接：https://github.com/python/cpython/blob/master/Objects/tupleobject.c。 中也維護了一個元組緩衝池 ，定義如下，但是長度只有 20。這個緩衝池與列表不一樣的是，數組中每個元素指向的是一個單鏈表的頭指針，這個鏈表中元組對象的 指向下一個元組，且每個元組長度一致。而 記錄的是這個鏈表的長度，最長為 2000。

元組的創建與列表類似，先從緩衝區中查找是否有可用對象，有則提取頭指針，同時 對應減一；沒有則另外開闢內存。刪除元組的時候，先判斷緩衝區對應的鏈表長度是否超過最大長度，沒有就將其放入單鏈表頭；超過則直接銷毀。元組一經建立不可改變，所以沒有其他賦值操作。

從以上分析可以看出，元組的緩衝區僅對長度小於 20 的元組做了優化。元組的元素索引也是通過指針讀取，這一點跟列表一致。而與列表相比，元組中沒有 ，可以看出相同元素的列表比元組耗內存。

由於元組是通過指針數組 存儲的，換句話說，元組儲存了元素的地址。元組的不可變在於其記錄的內存地址不可變，而該地址中存儲的內容是可以改變的（除非該地址中的內容本身也是不可變的）。

對序列的操作

Python 的序列一般都支持切片、+、* 等操作，基礎操作這裡不做介紹，只介紹一個特殊的操作——增量賦值及其可能引發的 bug 。

增量賦值

增量賦值是指 和 操作，其表現如何取決於左邊的操作對象。 相當於調用特殊方法 ，如果此對象沒有實現 方法則會調用 。

而 是就地加法（不會創建新變數），對於可變序列而言， 相當於對 直接調用 ；如果沒有實現 ，就相當於 ，而此過程是 創建出一個新對象，再賦值給 。

與 一樣，只是背後的特殊方法是 。總體來說，可變序列都實現了 和 方法，所以 和 都是就地加法。

然而，對某些元組使用增量賦值，會產生神奇的事情，看個 ：

如果元組中有可變類型的變數，再對元組中的這個可變對象進行增量賦值的時候，會提示元組不支持賦值，但實際又賦值成功了。

這是因為增量賦值不是原子操作，這行代碼的執行順序是：

執行操作

將第一步執行的結果賦值給

由於 是可變列表，所以第一步可以執行成功， 的值已經發生改變；但第二步是個賦值操作，由於元組是不可變的，所以報錯。

上述這種邊界情況十分罕見，為了避免這種情況出現，還是避免出現在元組中放入可變序列這種操作。

字典

Python 中另外一種十分重要的數據結構就是字典，在各種程序中被廣泛使用。而 Python 也對其進行了高度優化。為了更好的使用字典，我們來剖析字典的內部構造。

字典的結構

字典是基於散列表實現的，其結構定義在 中：

其中， 記錄了字典中元素的個數； 記錄了字典版本，每次字典有修改該值都會變；指針 指向一個 類型的對象； 記錄的是字典的 值，而我們根據這個值是否為 None 來判斷字典的類型（ combined/split ）。

的結構如下：

其中， 記錄了 hash 表 的大小； 表示在 hash 表中查找元素的方法； 記錄的是 中可用的數量； 記錄的是 中已用的數量； 是真正的 hash 表； 是一組 對象的數組，其定義如下。

由於對象的屬性都是通過字典的形式存儲，會導致很多對象的屬性都是鍵一樣但值不一樣。Python 針對這一特性對字典的內存管理做了優化。將字典分成 combined 和 split。

combined 型字典中， ，字典的值存放在 的 的 中；split 型字典中， ，字典的值存放在 中。

而 數組的 index 是根據 的 獲取的，有4種狀態：

Unused. index == -1.

Active. index >= 0, mekey != NULL and mevalue != NULL

Dummy. index == -2 (combined only)

Pending. index >= 0, key != NULL, and value == NULL (split only)

顯然，對於 Unused 和 Dummy 類型的 slot， 中沒有再浪費內存；同時，還會根據需要索引的 的數量動態的決定用什麼類型的變數來表示 index。再來說說 split 類型的字典，這種字典的 key 是共享的，有個引數計數器 來維護當前被引用的個數，其 value 值以數組的形式存放在 中，這樣就避免同一個 key 多次儲存 value ，節省了內存，也使得同一個 key 值的 value 以更緊湊的方式存儲在內存中。

字典的實現原理

基於對字典結構的認知，我們再來看看字典的實現原理。關於字典的操作源代碼鏈接：https://github.com/python/cpython/blob/master/Objects/dictobject.c

(1) 創建字典

字典中也維護了一個緩衝池 ，長度為 80。創建字典的邏輯也類似，先在緩衝池中查找可用的字典，有則直接使用，沒有則走申請內存的邏輯。在某些特定情況(比如對象的屬性賦值)下，會將字典初始化為 split 型。

字典在每次 新鍵值對前，都會檢查 中可用的空間，必要時重新分配以保證至少有三分之一是可用的。在插入新鍵值對時，先計算 key 的 hash 值，再用這個 hash 值根據一套完整的演算法計算出 數組的 index。最後對應變數記錄數據。

(2) 字典的索引

字典的索引也是根據 key 的 hash 值來獲得的，計算出 hash 值後，將該值的最低幾位數字當做偏移量，在 hash 表中查找 index，若找到的 為空，則拋錯；若不為空，檢查 是否等於 key，相等則對應的 即為所求，不相等則發生 hash 碰撞，為了解決 hash 衝突問題，演算法會在 hash 值中另外再取幾位，然後用特殊的方法處理一下，把新得到的數字再當作索引來尋找，重複以上步驟。可用圖表示如下：

字典的特徵

通過以上對字典的實現原理的分析，不難得出以下結論：

key 必須是可散列的。即滿足以下條件：

支持 函數，且得到的值是唯一的；

支持通過 方法來檢測相等性；

若 為真，則 也為真；

字典在內存上的開銷巨大

由於字典使用了 hash 表，而 hash 表又必須是稀疏的，這導致它在空間上的效率低下。而用元組取代字典可以節省相當的內存開銷，原因有二：1. 避免了 hash 表所消耗的內存；2. 無需把記錄中欄位的名字在每個元素里都存一遍。

鍵查詢很快

dict 的實現是典型的空間換時間，只要字典能被裝在內存里，就可以提供無視數據量大小的快速訪問。

鍵的次序取決於添加順序

當往 dict 里添加新鍵而又發生散列衝突的時候，新鍵可能會被安排存放到另一個位置。

往字典里添加新鍵可能會改變已有鍵的順序

無論何時往字典里添加新的鍵，Python 解釋器都可能做出為字典擴容的決定。擴容導致的結果就是要新建一個更大的散列表，並把字典里已有的元素添加到新表裡。這個過程中可能會發生新的散列衝突，導致新散列表中鍵的次序變化。所以最好不要對字典同時進行迭代和修改。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！