这篇文章主要介绍“Python中Dict实现的原理是什么”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“Python中Dict实现的原理是什么”文章能帮助大家解决问题。
1.无序Dict的实现
Dict在查找key时非常的快， 这得益于它的使用空间换时间思路和哈希实现。的在读取和写入Key时， 都会对Key进行哈希计算(所以要求Key都是不可变类型，如果是可变类型，就无法计算出他的哈希值了), 然后根据计算的值, 与当前的数组空间长度进行取模计算, 得到的值就是当前Key在数组的下标, 最后通过下标就可以以O(1)的时间复杂度读取值. 这种实现非常棒, 也是分布式的常见做法, 但也有问题, 如果数组满了怎么办或者是不同的Key, 但是哈希结果是一样的怎么办?
针对第一个问题的解决办法是在合适的时候进行扩容, 在
Python而针对第二个问题则有两个解法:
链接法: 原本数组里面存的是Key对应的值, 而链接法的数组存的是一个数组, 这个数组存了一个包含key和对应值的数组, 如下所示, 假设key1和key2的哈希结果都是0, 那就会插入到数组的0下标中, key1在0下标的数组的第一位, 而key2在插入时,发现已经存在key1了, 再用key2与key1进行对比, 发现它们的key其实是不一样的, 那就在0下标进行追加.
array = [
[
# 分别为key, hash值， 数值
('key1', 123, 123),
('key2', 123, 123)
],
[
('key3', 123, 123)
]
]开发寻址法: 开发寻址法走的是另外一个思路, 采取借用的思想, 在插入数据时， 如果遇到了冲突那就去使用当前下标的下一位, 如果下一位还是冲突, 就继续用下一位.在查找数据时则会对哈希值对应的key进行比较， 如果有值且对不上就找下一位， 直到或者空位找到为止。
上面两个的方案的实现都很简单, 对比下也很容易知道他们的优缺点:
链表法的优点:
删除记录方便, 直接处理数组对应下标的子数组即可.
平均查找速度快, 如果冲突了, 只需要对子数组进行查询即可
链表法的缺点:
用到了指针, 导致了查询速度会偏慢一点, 内存占用可能会较高, 不适合序列化. 而开放寻址法的优缺点是跟链表法反过来的, 由于Python万物基于Dict, 且都需要序列化, 所以选择了开放寻址法.
通过对比链表法和开放寻执法都可以发现, 他们都是针对哈希冲突的一个解决方案, 如果存数据的数组够大, 那么哈希冲突的可能性就会很小, 不用频繁扩容迁移数据, 但是占用的空间就会很大.所以一个好的哈希表实现初始值都不能太大, 在
PythonPython哈希表扩容一倍只会迁移一半的key的原因是获取key在数组的下标是通过对哈希值取模实现的， 比如一个哈希表容量为8，一个哈希值为20的key取模值为4，哈希表扩容后长度变为16， 此时取模结果还是4。而一个哈希值为11的key取模值为3， 扩容后取模值为11。可以很明显的看出，扩容后原来哈希值大于容量的key都不用做迁移， 而哈希值小于容量的都需要迁移。
但是如果按照上面是说法, 开放寻址法还是有一个问题的, 比如下面的数组:
arrray = [None, None, None, None, True, True, True, True]以True代表当前数组的位置已经被占用, None代表未被占用, 可以看出当前并未满足使用了数组的2/3空间, 数组还未到扩容阶段。 此时假设要插入一个Key, 刚好落在数组下标4, 那么插入的时候就要一直查询下去, 最后发现只有数组下标0的位置的空的, 才可以真正的插入数据. 对于一个长度只有8的数组, 需要执行5次才能插入数据, 那也太浪费性能了, 所以
PythonPythonx = ((5*y) + 1) % 2**i2.有序Dict的原理
Pythonarray = [
[],
[123456, "key1", 1],
[],
[],
[],
[234567, "key2", 2],
[],
[]
]这种实现的空间大小在初始化时就固定了, 直到下次扩容再发送变化, 在遍历字典时, 实际上就是遍历数组, 只是把没有占用的空间进行跳过.可以看出这种遍历的生成的顺序只跟哈希结果相关, 无法跟插入顺序相关, 所以这种方法的实现是无序的(同时由于每次启动程序时， 他们的哈希计算是不一样的， 所以每次遍历的顺序也就各不相同了).
而在
PythonPythonPython# 初始的结构
# -1代表还未插入数据
array_1 = [-1, -1, -1, -1, -1, -1, -1, -1]
array_2 = []
# 插入值后, 他就会变为:
array_1 = [-1, 0, -1, -1, -1, 1, -1, -1]
array_2 = [
[123456, "key1", 1],
[234567, "key2", 2],
]可以看出, 数组2的容量跟当前放入的值相等的, 数组1虽然还会保持1/3的空闲标记位, 但他只保存数组二的下标, 占用空间也不多, 相比之前的方案会节省一些空间, 同时在遍历的时候可以直接遍历数组2, 这样
Python3.有序字典的实现
通过上面的了解后, 可以使用
Pythonfrom typing import Any, Iterable, List, Optional, Tuple
class CustomerDict(object):
def __init__(self):
self._init_seed: int = 3 # 容量因子
self._init_length: int = 2 ** self._init_seed # 初始化数组大小
self._load_factor: float = 2 / 3 # 扩容因子
self._index_array: List[int] = [-1 for _ in range(self._init_length)] # 存放下标的数组
self._data_array: List[Optional[Tuple[int, Any, Any]]] = [] # 存放数据的数组
self._used_count: int = 0 # 目前用的量
self._delete_count: int = 0 # 被标记删除的量
def _create_new(self):
"""扩容函数"""
self._init_seed += 1 # 增加容量因子
self._init_length = 2 ** self._init_seed
old_data_array: List[Tuple[int, Any, Any]] = self._data_array
self._index_array: List[int] = [-1 for _ in range(self._init_length)]
self._data_array: List[Tuple[int, Any, Any]] = []
self._used_count = 0
self._delete_count = 0
# 这里只是简单实现, 实际上只需要搬运一半的数据
for item in old_data_array:
if item is not None:
self.__setitem__(item[1], item[2])
def _get_next(self, index: int):
"""计算冲突的下一跳，如果下标对应的值冲突了, 需要计算下一跳的下标"""
return ((5*index) + 1) % self._init_length
def _core(self, key: Any, default_value: Optional[Any] = None) -> Tuple[int, Any, int]:
"""获取数据或者得到可以放新数据的方法, 返回值是index_array的索引, 数据, data_array的索引"""
index: int = hash(key) % (self._init_length - 1)
while True:
data_index: int = self._index_array[index]
# 如果是-1则代表没有数据
if data_index == -1:
break
# 如果是-2则代表之前有数据则不过被删除了
elif data_index == -2:
index = self._get_next(index)
continue
_, new_key, default_value = self._data_array[data_index]
# 判断是不是对应的key
if key != new_key:
index = self._get_next(index)
else:
break
return index, default_value, data_index
def __getitem__(self, key: Any) -> Any:
_, value, data_index = self._core(key)
if data_index == -1:
raise KeyError(key)
return value
def __setitem__(self, key: Any, value: Any) -> None:
if (self._used_count / self._init_length) > self._load_factor:
self._create_new()
index, _, _ = self._core(key)
self._index_array[index] = self._used_count
self._data_array.append((hash(key), key, value))
self._used_count += 1
def __delitem__(self, key: Any) -> None:
index, _, data_index = self._core(key)
if data_index == -1:
raise KeyError(key)
self._index_array[index] = -2
self._data_array[data_index] = None
self._delete_count += 1
def __len__(self) -> int:
return self._used_count - self._delete_count
def __iter__(self) -> Iterable:
return iter(self._data_array)
def __str__(self) -> str:
return str({item[1]: item[2] for item in self._data_array if item is not None})
def keys(self) -> List[Any]:
"""模拟实现keys方法"""
return [item[1] for item in self._data_array if item is not None]
def values(self) -> List[Any]:
"""模拟实现values方法"""
return [item[2] for item in self._data_array if item is not None]
def items(self) -> List[Tuple[Any, Any]]:
"""模拟实现items方法"""
return [(item[1], item[2]) for item in self._data_array if item is not None]
if __name__ == '__main__':
customer_dict: CustomerDict = CustomerDict()
customer_dict["demo_1"] = "a"
customer_dict["demo_2"] = "b"
assert len(customer_dict) == 2
del customer_dict["demo_1"]
del customer_dict["demo_2"]
assert len(customer_dict) == 0
for i in range(30):
customer_dict[i] = i
assert len(customer_dict) == 30
customer_dict_value_list: List[Any] = customer_dict.values()
for i in range(30):
assert i == customer_dict[i]
for i in range(30):
assert customer_dict[i] == i
del customer_dict[i]
assert len(customer_dict) == 0