關(guān)于Python字典的底層實(shí)現(xiàn)原理
字典是否是有序
在Python3.6之前，字典是無序的，但是Python3.7+，字典是有序的。
在3.6中，字典有序是一個(gè)implementation detail，在3.7才正式成為語言特性，因此3.6中無法確保100%有序。
字典的查詢、添加、刪除的時(shí)間復(fù)雜度
字典的查詢、添加、刪除的平均時(shí)間復(fù)雜度都是O(1)，相比列表與元祖，性能更優(yōu)。
字典的實(shí)現(xiàn)原理
Python3.6之前的無序字典
字典底層是維護(hù)一張哈希表，可以把哈希表看成一個(gè)列表，哈希表中的每一個(gè)元素又存儲了哈希值（hash）、鍵（key）、值（value）3個(gè)元素。
enteies = [
['--', '--', '--'],
[hash, key, value],
['--', '--', '--'],
['--', '--', '--'],
[hash, key, value],
]
帶入具體的數(shù)值來介紹
# 給字典添加一個(gè)值，key為hello，value為word
# my_dict['hello'] = 'word'
# hash表初始如下
enteies = [
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
]
hash_value = hash('hello') # 假設(shè)值為 12343543
index = hash_value & ( len(enteies) - 1) # 假設(shè)index值計(jì)算后等于3
# 下面會將值存在enteies中
enteies = [
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
[12343543, 'hello', 'word'], # index=3
['--', '--', '--'],
]
# 繼續(xù)向字典中添加值
# my_dict['color'] = 'green'
hash_value = hash('color') # 假設(shè)值為 同樣為12343543
index = hash_value & ( len(enteies) - 1) # 假設(shè)index值計(jì)算后同樣等于3
# 下面會將值存在enteies中
enteies = [
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
[12343543, 'hello', 'word'], # 由于index=3的位置已經(jīng)被占用，且key不一樣，所以判定為hash沖突，繼續(xù)向下尋找
[12343543, 'color', 'green'], # 找到空余位置，則保存
]
enteies表是稀疏的，隨著我們插入的值不同，enteies表會越來越稀疏（enteies也是一個(gè)會動態(tài)擴(kuò)展長度的，每一此擴(kuò)展長度，都會重新計(jì)算所有key的hash值），所以新的字典實(shí)現(xiàn)就隨之出現(xiàn)。
Python3.7+后的新的實(shí)現(xiàn)方式
Python3.7+帶入數(shù)據(jù)演示
# 給字典添加一個(gè)值，key為hello，value為word
# my_dict['hello'] = 'word'
# 假設(shè)是一個(gè)空列表，hash表初始如下
indices = [None, None, None, None, None, None]
enteies = []
hash_value = hash('hello') # 假設(shè)值為 12343543
index = hash_value & ( len(indices) - 1) # 假設(shè)index值計(jì)算后等于3
# 會找到indices的index為3的位置
indices = [None, None, None, 0, None, None]
# 此時(shí)enteies會插入第一個(gè)元素
enteies = [
[12343543, 'hello', 'word']
]
# 我們繼續(xù)向字典中添加值
my_dict['haimeimei'] = 'lihua'
hash_value = hash('haimeimei') # 假設(shè)值為 34323545
index = hash_value & ( len(indices) - 1) # 假設(shè)index值計(jì)算后等于 0
# 會找到indices的index為0的位置
indices = [1, None, None, 0, None, None]
# 此時(shí)enteies會插入第一個(gè)元素
enteies = [
[12343543, 'hello', 'word'],
[34323545, 'haimeimei', 'lihua']
]
查詢字典
# 下面是一個(gè)字典與字典的存儲
more_dict = {'name': '張三', 'sex': '男', 'age': 10, 'birth': '2019-01-01'}
# 數(shù)據(jù)實(shí)際存儲
indices = [None, 2, None, 0, None, None, 1, None, 3]
enteies = [
[34353243, 'name', '張三'],
[34354545, 'sex', '男'],
[23343199, 'age', 10],
[00956542, 'birth', '2019-01-01'],
]
print(more_dict['age']) # 當(dāng)我們執(zhí)行這句時(shí)
hash_value = hash('age') # 假設(shè)值為 23343199
index = hash_value & ( len(indices) - 1) # index = 1
entey_index = indices[1] # 數(shù)據(jù)在enteies的位置是2
value = enteies[entey_index] # 所以找到值為 enteies[2]
時(shí)間復(fù)雜度
字典的平均時(shí)間復(fù)雜度是O(1)，因?yàn)樽值涫峭ㄟ^哈希算法來實(shí)現(xiàn)的，哈希算法不可避免的問題就是hash沖突，Python字典發(fā)生哈希沖突時(shí)，會向下尋找空余位置，直到找到位置。
如果在計(jì)算key的hash值時(shí)，如果一直找不到空余位置，則字典的時(shí)間復(fù)雜度就變成了O(n)了。
常見的哈希沖突解決方法
1 開放尋址法（open addressing）
開放尋址法中，所有的元素都存放在散列表里，當(dāng)產(chǎn)生哈希沖突時(shí)，通過一個(gè)探測函數(shù)計(jì)算出下一個(gè)候選位置，如果下一個(gè)獲選位置還是有沖突，那么不斷通過探測函數(shù)往下找，直到找個(gè)一個(gè)空槽來存放待插入元素。
2 再哈希法
這個(gè)方法是按順序規(guī)定多個(gè)哈希函數(shù)，每次查詢的時(shí)候按順序調(diào)用哈希函數(shù)，調(diào)用到第一個(gè)為空的時(shí)候返回不存在，調(diào)用到此鍵的時(shí)候返回其值。
3 鏈地址法
將所有關(guān)鍵字哈希值相同的記錄都存在同一線性鏈表中，這樣不需要占用其他的哈希地址，相同的哈希值在一條鏈表上，按順序遍歷就可以找到。
4 公共溢出區(qū)
其基本思想是：所有關(guān)鍵字和基本表中關(guān)鍵字為相同哈希值的記錄，不管他們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。
總結(jié)
以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
Python中urllib+urllib2+cookielib模塊編寫爬蟲實(shí)戰(zhàn)
這篇文章主要介紹了Python的urllib+urllib2+cookielib模塊編寫爬蟲實(shí)戰(zhàn),文中給出了抓取豆瓣同城和登陸圖書館查詢圖書歸還的爬取例子,需要的朋友可以參考下2016-01-01
這篇文章主要介紹了python繪制風(fēng)場方向和大小quiver問題,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
推薦下python/ironpython:從入門到精通...2007-10-10
這篇文章主要介紹了Python使用分布式鎖的代碼演示，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-07-07
Python使用base64模塊進(jìn)行二進(jìn)制數(shù)據(jù)編碼詳解
這篇文章主要介紹了Python使用base64模塊進(jìn)行二進(jìn)制數(shù)據(jù)編碼詳解，具有一定借鑒價(jià)值,需要的朋友可以參考下2018-01-01
這篇文章主要介紹了python中賦值語句的特點(diǎn)和形式,文中介紹了多目標(biāo)賦值的共享引用問題,多目標(biāo)賦值其實(shí)是多個(gè)目標(biāo)對同一個(gè)內(nèi)存空間的引用,這里要分兩種情況,當(dāng)被引用對象是不可變對象時(shí)則不存在問題,感興趣的朋友跟隨小編一起看看吧2023-12-12
python 常用日期處理-- datetime 模塊的使用
這篇文章主要介紹了python 如何對日期進(jìn)行處理，幫助大家更好的理解和學(xué)習(xí)python，感興趣的朋友可以了解下2020-09-09
Pycharm安裝第三方庫、安裝位置以及鏡像設(shè)置方法詳解
對于Python開發(fā)用戶來講,安裝第三方庫是家常便飯,下面這篇文章主要給大家介紹了關(guān)于Pycharm安裝第三方庫、安裝位置以及鏡像設(shè)置方法的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-05-05
這篇文章主要介紹了Pandas-DataFrame知識點(diǎn)匯總，DataFrame是一種表格型數(shù)據(jù)結(jié)構(gòu)，它含有一組有序的列，每列可以是不同的值，下面我們一起進(jìn)入文章了解更多詳細(xì)內(nèi)容吧，需要的小伙伴也可以參考一下2022-03-03
詳解Python如何循環(huán)遍歷Numpy中的Array
Numpy是Python中常見的數(shù)據(jù)處理庫，是數(shù)據(jù)科學(xué)中經(jīng)常使用的庫。在本文中，我們將學(xué)習(xí)如何迭代遍歷訪問矩陣中的元素，需要的可以參考一下2022-04-04