Python辞書dict実現原理

一.辞書は何ですか.
辞書は、キーと値のペアからなる要素の一連の集合です.ディクショナリは、任意のタイプのオブジェクトを格納できる可変コンテナモデルです.辞書はハッシュアルゴリズムと密接に分けられず(異なるPythonバージョンではアルゴリズムが異なる)、ハッシュアルゴリズムを知らない子供靴はまず関連知識を知ることができる.
二.辞書は整然としていますか?
Python 3.6以前は辞書は無秩序だったが、Python 3.7+、辞書は整然としています.3.6では、辞書秩序はimplementation detailであり、3.7で正式に言語特性になったため、3.6では100%秩序を確保できません.
三.辞書のクエリー、追加、削除の時間の複雑さ?
辞書のクエリー、追加、削除の平均時間複雑度はすべてO(1)(なぜ平均時間複雑度なのか、文章の後で説明します)で、リストと元祖より性能が優れています.
四.辞書の実現原理?

まずPython 3について話します.6以前の無秩序辞書

辞書の下部はハッシュテーブル(下図参照)を維持し、ハッシュテーブルをリストと見なすことができ、ハッシュテーブルの各要素にはハッシュ値(hash)、キー(key)、値(value)の3つの要素が格納されている.(Python 3.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値ではなく、enteiesにおける値の位置

を示すlen(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のデータは挿入されたデータと同じであるため、新しい辞書は秩序化されている.
上記の例は衝突の解決策を説明していないので、自分で考えてみることができます.
五.時間複雑度の説明
上述したように,辞書の平均時間複雑度はO(1)であり,辞書はハッシュアルゴリズムによって実現されるため,ハッシュアルゴリズムではhash競合が避けられない問題であり,Python辞書でハッシュ競合が発生すると,位置が見つかるまで下に空き位置を探す.keyのhash値を計算する際,空き位置が見つからないままでは辞書の時間的複雑度がO(n)となるため,Pythonのハッシュアルゴリズムが重要となる.Python辞書のハッシュアルゴリズムは、ハッシュ値で計算されたindexが平均分布であり、各値の間に残りの位置があることをできるだけ保証します.例えば、次のようにします.

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

およびindexはできるだけ0,3,5,7の類似値で、ハッシュ競合が発生した場合、すぐに空き位置を見つけることができることを保証します.
六.辞書のkeyはどんな値を使うことができますか?
Python辞書のkeyには、文字列(str)、整数(int)、元祖(tuple)などが使用できます.辞書はハッシュアルゴリズムによってkeyの値を計算することを知っているので、keyはハッシュ可能でなければならない.listは辞書のkeyとしてはならない.listは可変でハッシュ不可能なオブジェクトであるため、辞書のkeyとしてはならない.