Python字典dict實作原理

一. 什麼是字典？

字典是一系列由鍵（key）和值（value）配對組成的元素的集合。字典是一個可變容器模型，可以存儲任意類型對象。字典實作與雜湊演算法密不可分（不同的Python版本，算法會不同），不了解雜湊演算法的童鞋可以先去了解相關知識。

二. 字典是否是有序的？

在Python3.6之前，字典是無序的，但是Python3.7+，字典是有序的。在3.6中，字典有序是一個implementation detail，在3.7才正式成為語言特性，是以3.6中無法確定100%有序。

三. 字典的查詢、添加、删除的時間複雜度？

字典的查詢、添加、删除的平均時間複雜度都是O(1)（為什麼是平均時間複雜度，文章後面會講解到），相比清單與元祖，性能更優。

四. 字典的實作原理？

1. 首先說說Python3.6之前的無序字典

字典底層是維護一張哈希表（見下圖），我們可以把哈希表看成一個清單，哈希表中的每一個元素又存儲了哈希值（hash）、鍵（key）、值（value）3個元素。（Python3.6之前）

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

由上可以見哈希表的存儲結構，我們也可以看出，元素之間有一些空元素，我們通過增加一個元素來講解具體實作。

• 計算key的hash值【hash(key)】，再和mask做與操作【mask=字典最小長度（DictMinSize） - 1】，運算後會得到一個數字【index】，這個index就是要插入的enteies哈希表中的下标位置
• 若index下标位置已經被占用，則會判斷enteies的key是否與要插入的key是否相等
• 如果key相等就表示key已存在，則更新value值
• 如果key不相等，就表示hash沖突，則會繼續向下尋找空位置，一直到找到剩餘空位為止。

以上介紹了老字典的實作過程，下面我們帶入具體的數值來介紹。

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

# 假設是一個空清單，hash表初始如下
enteies = [
    ['--', '--', '--'],
    ['--', '--', '--'],
    ['--', '--', '--'],
    ['--', '--', '--'],
    ['--', '--', '--'],
]      

hash_value = hash('hello')  # 假設值為 12343543 注：以下計算值不等于實際值，僅為示範使用
index = hash_value & ( len(enteies) - 1)  # 假設index值計算後等于3，具體的hash算法本文不做介紹

# 下面會将值存在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'],  # 找到空餘位置，則儲存
]      

通過上面的講解，已經了解了字典的插入的過程，可以更具此過程分析出字典查找、插入的執行過程，這裡就不過多贅述。我們可以看到，不同的key計算的出的index值是不一樣的，在enteies中插入的位置不一樣，是以當我們周遊字典的時候，字段的順序與我們插入的順序是不相同的。

我們同樣可以發現，enteies表是稀疏的，随着我們插入的值不同，enteies表會越來越稀疏（enteies也是一個會動态擴充長度的，每一此擴充長度，都會重新計算所有key的hash值），是以新的字典實作就随之出現。

2. Python3.7+後的新的實作方式

老字典使用一張hash，而新字典還使用了一張Indices表來輔助。下來列出新的結構：

indices = [None, None, index, None, index, None, index]
enteies = [
    [hash0, key0, value0],
    [hash1, key1, value1],
    [hash2, key2, value2]
]      

下面為具體的實作過程：

• 計算key的hash值【hash(key)】，再和mask做與操作【mask=字典最小長度（IndicesDictMinSize） - 1】，運算後會得到一個數字【index】，這個index就是要插入的indices的下标位置（注：具體算法與Python版本相關，并不一定一樣）
• 得到index後，會找到indices的位置，但是此位置不是存的hash值，而是存的len(enteies)，表示該值在enteies中的位置
• 如果出現hash沖突，則處理方式與老字典處理方式類似

下面帶入實際實作過程：

# 給字典添加一個值，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，具體的hash算法本文不做介紹

# 會找到indices的index為3的位置，并插入enteies的長度
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的位置，并插入enteies的長度
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]      

由上可以看出，新字典存儲資料本身的enteies并不會稀疏，由indices來維護具體存儲的位置，enteies中的資料是和插入的資料是一樣的，是以新的字典是有序的。

上面的例子沒有說明沖突的解決方案，大家可以自己思考思考。

五. 時間複雜度說明

[index, None, None, None, index, None, None, None]      

六. 字典的key能使用什麼值？