關(guān)于Python字典的底層實(shí)現(xiàn)原理
字典是否是有序
在Python3.6之前，字典是無序的，但是Python3.7+，字典是有序的。
在3.6中，字典有序是一個implementation detail，在3.7才正式成為語言特性，因此3.6中無法確保100%有序。
字典的查詢、添加、刪除的時間復(fù)雜度
字典的查詢、添加、刪除的平均時間復(fù)雜度都是O(1)，相比列表與元祖，性能更優(yōu)。
字典的實(shí)現(xiàn)原理
Python3.6之前的無序字典
字典底層是維護(hù)一張哈希表，可以把哈希表看成一個列表，哈希表中的每一個元素又存儲了哈希值（hash）、鍵（key）、值（value）3個元素。
enteies = [
['--', '--', '--'],
[hash, key, value],
['--', '--', '--'],
['--', '--', '--'],
[hash, key, value],
]
帶入具體的數(shù)值來介紹
# 給字典添加一個值，key為hello，value為word
# my_dict['hello'] = 'word'
# hash表初始如下
enteies = [
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
]
hash_value = hash('hello') # 假設(shè)值為 12343543
index = hash_value & ( len(enteies) - 1) # 假設(shè)index值計算后等于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值計算后同樣等于3
# 下面會將值存在enteies中
enteies = [
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
[12343543, 'hello', 'word'], # 由于index=3的位置已經(jīng)被占用，且key不一樣，所以判定為hash沖突，繼續(xù)向下尋找
[12343543, 'color', 'green'], # 找到空余位置，則保存
]
enteies表是稀疏的，隨著我們插入的值不同，enteies表會越來越稀疏（enteies也是一個會動態(tài)擴(kuò)展長度的，每一此擴(kuò)展長度，都會重新計算所有key的hash值），所以新的字典實(shí)現(xiàn)就隨之出現(xiàn)。
Python3.7+后的新的實(shí)現(xiàn)方式
Python3.7+帶入數(shù)據(jù)演示
# 給字典添加一個值，key為hello，value為word
# my_dict['hello'] = 'word'
# 假設(shè)是一個空列表，hash表初始如下
indices = [None, None, None, None, None, None]
enteies = []
hash_value = hash('hello') # 假設(shè)值為 12343543
index = hash_value & ( len(indices) - 1) # 假設(shè)index值計算后等于3
# 會找到indices的index為3的位置
indices = [None, None, None, 0, None, None]
# 此時enteies會插入第一個元素
enteies = [
[12343543, 'hello', 'word']
]
# 我們繼續(xù)向字典中添加值
my_dict['haimeimei'] = 'lihua'
hash_value = hash('haimeimei') # 假設(shè)值為 34323545
index = hash_value & ( len(indices) - 1) # 假設(shè)index值計算后等于 0
# 會找到indices的index為0的位置
indices = [1, None, None, 0, None, None]
# 此時enteies會插入第一個元素
enteies = [
[12343543, 'hello', 'word'],
[34323545, 'haimeimei', 'lihua']
]
查詢字典
# 下面是一個字典與字典的存儲
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í)行這句時
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]
時間復(fù)雜度
字典的平均時間復(fù)雜度是O(1)，因?yàn)樽值涫峭ㄟ^哈希算法來實(shí)現(xiàn)的，哈希算法不可避免的問題就是hash沖突，Python字典發(fā)生哈希沖突時，會向下尋找空余位置，直到找到位置。
如果在計算key的hash值時，如果一直找不到空余位置，則字典的時間復(fù)雜度就變成了O(n)了。
常見的哈希沖突解決方法
1 開放尋址法（open addressing）
開放尋址法中，所有的元素都存放在散列表里，當(dāng)產(chǎn)生哈希沖突時，通過一個探測函數(shù)計算出下一個候選位置，如果下一個獲選位置還是有沖突，那么不斷通過探測函數(shù)往下找，直到找個一個空槽來存放待插入元素。
2 再哈希法
這個方法是按順序規(guī)定多個哈希函數(shù)，每次查詢的時候按順序調(diào)用哈希函數(shù)，調(diào)用到第一個為空的時候返回不存在，調(diào)用到此鍵的時候返回其值。
3 鏈地址法
將所有關(guān)鍵字哈希值相同的記錄都存在同一線性鏈表中，這樣不需要占用其他的哈希地址，相同的哈希值在一條鏈表上，按順序遍歷就可以找到。
4 公共溢出區(qū)
其基本思想是：所有關(guān)鍵字和基本表中關(guān)鍵字為相同哈希值的記錄，不管他們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。
總結(jié)
以上為個人經(jīng)驗(yàn)，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
Python解析器安裝指南分享(Mac/Windows/Linux)
這篇文章主要介紹了Python解析器安裝指南(Mac/Windows/Linux),具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2025-03-03
利用Python的Flask框架來構(gòu)建一個簡單的數(shù)字商品支付解決方案
這篇文章主要介紹了利用Python的Flask框架來構(gòu)建一個簡單的數(shù)字商品支付解決方案,文中用極簡的代碼展示了一個flask框架下的支付模版，需要的朋友可以參考下2015-03-03
這篇文章主要為大家詳細(xì)介紹了如何利用python來實(shí)現(xiàn)自動化辦公操作excel文件進(jìn)行各種樣式展示,并自動發(fā)送文件給"老板"的郵箱,希望對大家有所幫助2024-03-03
如何將Pycharm中調(diào)整字體大小的方式設(shè)置為"ctrl+鼠標(biāo)滾輪上下滑"
這篇文章主要介紹了如何將Pycharm中調(diào)整字體大小的方式設(shè)置為"ctrl+鼠標(biāo)滾輪上下滑",本文通過圖文并茂的形式給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-11-11
本文給大家分享python 定時拆分備份 nginx 日志的方法，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友參考下吧2020-04-04
Python模塊_PyLibTiff讀取tif文件的實(shí)例
今天小編就為大家分享一篇Python模塊_PyLibTiff讀取tif文件的實(shí)例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-01-01
日常工作中總會遇到一些需要收集文件的情況,但往往最后收集回來的文件名稱會五花八門,下面小編就來為大家講講如何使用Python實(shí)現(xiàn)批量重命名操作吧2025-02-02
這篇文章主要介紹了Python簡單I/O操作,結(jié)合實(shí)例形式分析了Python針對文件的I/O讀寫及cPickle模塊相關(guān)使用操作技巧,需要的朋友可以參考下2019-03-03
這篇文章主要介紹了PyCharm搭建一勞永逸的開發(fā)環(huán)境,本文通過圖文并茂的形式給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-04-04
這篇文章主要為大家詳細(xì)介紹了一個基于PyQt5開發(fā)的桌面應(yīng)用,可以實(shí)現(xiàn)Office文檔圖片提取功能,文中的示例代碼講解詳細(xì),需要的可以參考一下2025-01-01