关于Python字典的底层实现原理

这篇文章主要介绍了关于Python字典的底层实现原理，具有很好的参考价值，希望对大家有所帮助。如有错误或未考虑完全的地方，望不吝赐教

字典是否是有序

在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]