快捷導(dǎo)航

Python?中的?list、tuple、set、dict的底層實現(xiàn)小結(jié)

更新時間：2025年03月20日 09:27:54 作者：星哲最開心

本文詳細(xì)介紹了Python中四種常用數(shù)據(jù)結(jié)構(gòu)——list、tuple、set和dict的底層實現(xiàn),包括它們的存儲方式、性能特點以及適用場景,感興趣的朋友一起看看吧

在 Python 中，list、tuple、set 和 dict 是四種非常常用的數(shù)據(jù)結(jié)構(gòu)。它們的底層實現(xiàn)各有特點，這些實現(xiàn)方式?jīng)Q定了它們的性能和使用場景。以下是對這四種數(shù)據(jù)結(jié)構(gòu)底層實現(xiàn)的詳細(xì)解釋：

1. list（列表）

list 是 Python 中最常用的數(shù)據(jù)結(jié)構(gòu)之一，它是一個 動態(tài)數(shù)組，用于存儲有序的元素集合。

底層實現(xiàn)

存儲方式：list 是一個 連續(xù)的內(nèi)存塊，用于存儲元素的引用（指針）。這意味著 list 中的元素可以是任意類型，因為存儲的是對象的引用，而不是對象本身。
動態(tài)擴(kuò)展：list 的大小是動態(tài)的。當(dāng)列表空間不足時，Python 會分配一個新的更大的內(nèi)存塊，并將舊數(shù)據(jù)復(fù)制到新內(nèi)存塊中。通常，新的內(nèi)存塊大小是當(dāng)前大小的 1.125 倍（具體倍數(shù)可能因 Python 版本而異）。
內(nèi)存管理：由于 list 是連續(xù)內(nèi)存，因此它支持快速的隨機(jī)訪問（通過索引訪問元素的時間復(fù)雜度為 O(1)）。但插入和刪除操作（尤其是非尾部操作）可能需要移動大量元素，時間復(fù)雜度為 O(n)。

性能特點

優(yōu)點：

支持快速的隨機(jī)訪問（通過索引）。
內(nèi)部實現(xiàn)簡單，適合存儲有序數(shù)據(jù)。

缺點：

插入和刪除操作（尤其是非尾部操作）效率較低。
內(nèi)存占用可能較高，因為需要預(yù)留額外空間以支持動態(tài)擴(kuò)展。

2. tuple（元組）

tuple 是一個 不可變的有序集合，用于存儲一組固定的數(shù)據(jù)。

底層實現(xiàn)

存儲方式：與 list 類似，tuple 也是通過 連續(xù)的內(nèi)存塊 存儲元素的引用。不同的是，tuple 是不可變的，這意味著它的大小和內(nèi)容在創(chuàng)建后不能被修改。
內(nèi)存分配：由于 tuple 是不可變的，Python 在創(chuàng)建 tuple 時會一次性分配足夠的內(nèi)存來存儲所有元素，而不需要考慮動態(tài)擴(kuò)展。
性能優(yōu)化：由于不可變性，tuple 在某些情況下比 list 更高效，尤其是在作為字典的鍵或集合的元素時，因為它們的哈希值是固定的。

性能特點

優(yōu)點：

不可變性保證了數(shù)據(jù)的安全性。
在某些場景下（如作為哈希表的鍵）比 list 更高效。

缺點：

不支持動態(tài)修改，靈活性較差。

3. set（集合）

set 是一個 無序的集合，用于存儲唯一的元素。它支持高效的成員查找、插入和刪除操作。

底層實現(xiàn)

存儲方式：set 的底層實現(xiàn)是基于 哈希表 的。每個元素通過哈希函數(shù)映射到一個唯一的哈希值，并存儲在哈希表中。
沖突解決：當(dāng)兩個元素的哈希值沖突時，Python 使用鏈表或 開放尋址法 來解決沖突。具體實現(xiàn)取決于 Python 的版本。
動態(tài)擴(kuò)展：與 list 類似，set 的大小也是動態(tài)的。當(dāng)哈希表的負(fù)載因子（元素數(shù)量與哈希表大小的比值）超過某個閾值時，哈希表會自動擴(kuò)展，重新分配更大的內(nèi)存空間并重新哈希所有元素。

性能特點

優(yōu)點：

成員查找、插入和刪除操作的時間復(fù)雜度為 O(1)。
自動去重，適合存儲唯一元素。

缺點：

不支持重復(fù)元素。
不支持有序訪問。

4. dict（字典）

dict 是一個 鍵值對的集合，用于存儲映射關(guān)系。它是 Python 中最強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)之一。

底層實現(xiàn)

存儲方式：dict 的底層實現(xiàn)也是基于 哈希表 的。每個鍵通過哈希函數(shù)映射到一個唯一的哈希值，并存儲在哈希表中。值則與鍵關(guān)聯(lián)存儲。
沖突解決：與 set 類似，dict 也使用鏈表或開放尋址法解決哈希沖突。
動態(tài)擴(kuò)展：當(dāng)哈希表的負(fù)載因子超過某個閾值時，dict 會自動擴(kuò)展，重新分配更大的內(nèi)存空間并重新哈希所有鍵值對。
鍵的唯一性：dict 的鍵必須是不可變類型（如整數(shù)、字符串、元組等），因為它們需要支持哈希操作。

性能特點

優(yōu)點：

鍵值對查找、插入和刪除操作的時間復(fù)雜度為 O(1)。
支持靈活的鍵值映射關(guān)系。

缺點：

鍵必須是不可變類型。
不支持有序訪問（Python 3.7+ 中的 dict 保持了插入順序，但這不是通過哈希表實現(xiàn)的，而是通過額外的機(jī)制）。

總結(jié)

數(shù)據(jù)結(jié)構(gòu)	底層實現(xiàn)	優(yōu)點	缺點
`list`	動態(tài)數(shù)組	隨機(jī)訪問快，支持動態(tài)擴(kuò)展	插入和刪除效率低，內(nèi)存占用可能較高
`tuple`	靜態(tài)數(shù)組	不可變，適合哈希	不支持動態(tài)修改
`set`	哈希表	成員查找、插入和刪除快，自動去重	不支持重復(fù)元素，不支持有序訪問
`dict`	哈希表	鍵值對查找、插入和刪除快	鍵必須是不可變類型，不支持有序訪問

擴(kuò)展閱讀

Python 官方文檔：數(shù)據(jù)模型
Python 源碼分析：可以參考 Python 源碼中的實現(xiàn)細(xì)節(jié)，特別是 listobject.c、tupleobject.c、setobject.c 和 dictobject.c 文件。
性能優(yōu)化：了解這些數(shù)據(jù)結(jié)構(gòu)的底層實現(xiàn)可以幫助你更好地選擇合適的數(shù)據(jù)結(jié)構(gòu)來優(yōu)化代碼性能。

如果你對某個數(shù)據(jù)結(jié)構(gòu)的底層實現(xiàn)有更具體的問題，歡迎繼續(xù)提問！

到此這篇關(guān)于Python 中的 list、tuple、set、dict的底層實現(xiàn)的理解的文章就介紹到這了,更多相關(guān)Python list、tuple、set、dict內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: