日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

關于Python字典的底層實現原理_python

作者：Generalzy ? 更新時間： 2023-04-22 編程語言

字典是否是有序

在Python3.6之前，字典是無序的，但是Python3.7+，字典是有序的。

在3.6中，字典有序是一個implementation detail，在3.7才正式成為語言特性，因此3.6中無法確保100%有序。

字典的查詢、添加、刪除的時間復雜度

字典的查詢、添加、刪除的平均時間復雜度都是O(1)，相比列表與元祖，性能更優。

字典的實現原理

Python3.6之前的無序字典

字典底層是維護一張哈希表，可以把哈希表看成一個列表，哈希表中的每一個元素又存儲了哈希值（hash）、鍵（key）、值（value）3個元素。

enteies = [
    ['--', '--', '--'],
    [hash, key, value],
    ['--', '--', '--'],
    ['--', '--', '--'],
    [hash, key, value],
]

帶入具體的數值來介紹

# 給字典添加一個值，key為hello，value為word
# my_dict['hello'] = 'word'

# hash表初始如下
enteies = [
    ['--', '--', '--'],
    ['--', '--', '--'],
    ['--', '--', '--'],
    ['--', '--', '--'],
    ['--', '--', '--'],
]

hash_value = hash('hello')  # 假設值為 12343543 

index = hash_value & ( len(enteies) - 1)  # 假設index值計算后等于3

# 下面會將值存在enteies中
enteies = [
    ['--', '--', '--'],
    ['--', '--', '--'],
    ['--', '--', '--'],
    [12343543, 'hello', 'word'],  # index=3
    ['--', '--', '--'],
]

# 繼續向字典中添加值
# my_dict['color'] = 'green'

hash_value = hash('color')  # 假設值為 同樣為12343543
index = hash_value & ( len(enteies) - 1)  # 假設index值計算后同樣等于3

# 下面會將值存在enteies中
enteies = [
    ['--', '--', '--'],
    ['--', '--', '--'],
    ['--', '--', '--'],
    [12343543, 'hello', 'word'],  # 由于index=3的位置已經被占用，且key不一樣，所以判定為hash沖突，繼續向下尋找
    [12343543, 'color', 'green'],  # 找到空余位置，則保存
]

enteies表是稀疏的，隨著我們插入的值不同，enteies表會越來越稀疏（enteies也是一個會動態擴展長度的，每一此擴展長度，都會重新計算所有key的hash值），所以新的字典實現就隨之出現。

Python3.7+后的新的實現方式

Python3.7+帶入數據演示

# 給字典添加一個值，key為hello，value為word
# my_dict['hello'] = 'word'

# 假設是一個空列表，hash表初始如下
indices = [None, None, None, None, None, None]
enteies = []

hash_value = hash('hello')  # 假設值為 12343543
index = hash_value & ( len(indices) - 1)  # 假設index值計算后等于3

# 會找到indices的index為3的位置
indices = [None, None, None, 0, None, None]
# 此時enteies會插入第一個元素
enteies = [
    [12343543, 'hello', 'word']
]

# 我們繼續向字典中添加值
my_dict['haimeimei'] = 'lihua'

hash_value = hash('haimeimei')  # 假設值為 34323545
index = hash_value & ( len(indices) - 1)  # 假設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'}

# 數據實際存儲
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'])  # 當我們執行這句時

hash_value = hash('age')  # 假設值為 23343199
index = hash_value & ( len(indices) - 1)  # index = 1

entey_index = indices[1]  # 數據在enteies的位置是2
value = enteies[entey_index]  # 所以找到值為 enteies[2]

時間復雜度

字典的平均時間復雜度是O(1)，因為字典是通過哈希算法來實現的，哈希算法不可避免的問題就是hash沖突，Python字典發生哈希沖突時，會向下尋找空余位置，直到找到位置。

如果在計算key的hash值時，如果一直找不到空余位置，則字典的時間復雜度就變成了O(n)了。

常見的哈希沖突解決方法

1 開放尋址法（open addressing）

開放尋址法中，所有的元素都存放在散列表里，當產生哈希沖突時，通過一個探測函數計算出下一個候選位置，如果下一個獲選位置還是有沖突，那么不斷通過探測函數往下找，直到找個一個空槽來存放待插入元素。

2 再哈希法

這個方法是按順序規定多個哈希函數，每次查詢的時候按順序調用哈希函數，調用到第一個為空的時候返回不存在，調用到此鍵的時候返回其值。

3 鏈地址法

將所有關鍵字哈希值相同的記錄都存在同一線性鏈表中，這樣不需要占用其他的哈希地址，相同的哈希值在一條鏈表上，按順序遍歷就可以找到。

4 公共溢出區

其基本思想是：所有關鍵字和基本表中關鍵字為相同哈希值的記錄，不管他們由哈希函數得到的哈希地址是什么，一旦發生沖突，都填入溢出表。

總結

原文鏈接：https://blog.csdn.net/General_zy/article/details/122038164

欄目分類
最近更新