Dict は、空間対時間戦略とハッシュ テーブル実装のおかげで、キーをすばやく見つけることができます。キーの読み取りおよび書き込み時には、キーがハッシュ化され (そのため、キーは不変型である必要があります。変数型の場合、ハッシュ値は計算できません)、計算された値と現在の配列空間の長さは剰余的に計算され、取得された値は配列内の現在の Key の添字です。最後に、添字を通じて、O(1) の時間計算量で値を読み取ることができます。この実装は優れています。は分散への一般的なアプローチですが、問題もあります。配列がいっぱいであるかキーが異なる場合、ハッシュ結果が同じ場合はどうすればよいですか?
最初の問題の解決策は、容量を拡張する際、Python では、Dict に配置された数値が容量の 2/3 を占めると、Dict が拡張を開始し、拡張後の総容量は拡張前の 2 倍になります。これは、頻繁な拡張によるキーの移行の増加を減らすためです。
2 番目の問題には 2 つの解決策があります:
リンク メソッド: 元の配列には、次の値に対応する値が含まれます。 Key、連鎖メソッドの配列には配列が格納されます。この配列には、以下に示すように、キーと対応する値を含む配列が格納されます。key1 と key2 のハッシュ結果が両方とも 0 であると仮定して、In に挿入されます。配列の 0 の添字、key1 は 0 の添字配列の最初の位置にあり、key2 が挿入されると、key1 がすでに存在することがわかります。次に、key2 と key1 を比較して、それらのキーが実際に異なることを確認し、次に追加します。 0 subscript.
array = [
[
# 分别为key, hash值， 数值
('key1', 123, 123),
('key2', 123, 123)
],
[
('key3', 123, 123)
]
]アドレッシング方法の開発: アドレッシング方法の開発では、データを挿入するときに競合が発生した場合に、借用のアイデアを採用する別のアイデアが採用されています。現在の添字の次の桁です。次の桁がまだ競合する場合は、次の桁を使用し続けます。データを検索するとき、ハッシュ値に対応するキーが比較されます。値があり、一致しない場合は、次のビット、空席が見つかるまで、または空席が見つかるまで。
上記の 2 つのソリューションの実装は非常に簡単で、比較することでそれぞれの長所と短所を簡単に知ることができます:
リンク リスト方式の利点:
Python の Dict の値は 8 です。さらに、ハッシュ テーブルにはデータの配列を保存できる必要もあります。未使用の空席は範囲内で変動するため、スペースの使用量とハッシュ衝突の確率が高くなります。容量は最適な状態に維持されますが、拡張するたびに多大なパフォーマンスを消費するため、毎回変更することはできません。拡張するため、値を決定する必要があります。未使用/使用率がこの値に達すると、容量は自動的に変更されますPython の Dict では、この値は 2/3 です。つまり、Dict が使用されると、スペースの 2/3 が占有された後、新しい最適なバランスに達するために自動的に拡張されます。同時に、拡張ごとのキーの移行数を減らすために、拡張後の総容量は拡張前の総容量の 3 分の 1 倍にする必要があり、この場合、キーの数は半分だけで済みます。
arrray = [None, None, None, None, True, True, True, True]
以True代表当前数组的位置已经被占用, None代表未被占用, 可以看出当前并未满足使用了数组的2/3空间, 数组还未到扩容阶段。 此时假设要插入一个Key, 刚好落在数组下标4, 那么插入的时候就要一直查询下去, 最后发现只有数组下标0的位置的空的, 才可以真正的插入数据. 对于一个长度只有8的数组, 需要执行5次才能插入数据, 那也太浪费性能了, 所以Python要实现一个算法, 尽量让冲突的数据插在别的地方. 在源码中, Python用到了公式x = ((5*y) + 1) % 2**i来实现跳跃插入冲突数据. 式子中x为数组的下一个坐标, y为当前发生冲突的坐标,i为容量系数, 比如初始化时, i为3, 那么容量就是8了, 第一次插入数据到坐标0冲突时, y = 0, 带入公式后, 求得x 等于1, 第二次插入数据到坐标0时, y = 1, 求得x 等于 6, 通过这样算下去, 可以发现数字生成轨迹是0>1>6>7>4>5>2>3>0一直循环着, 这样跳着插数据就能完美解决上面场景的问题.
Python3.6之前说的差不多, 它的数组大概是长这样的, 数组中存了子数组, 第一项为hash值, 第二项为key, 第三项为值.
array = [ [], [123456, "key1", 1], [], [], [], [234567, "key2", 2], [], [] ]
这种实现的空间大小在初始化时就固定了, 直到下次扩容再发送变化, 在遍历字典时, 实际上就是遍历数组, 只是把没有占用的空间进行跳过.可以看出这种遍历的生成的顺序只跟哈希结果相关, 无法跟插入顺序相关, 所以这种方法的实现是无序的(同时由于每次启动程序时， 他们的哈希计算是不一样的， 所以每次遍历的顺序也就各不相同了).
而在Python3.7之后, Python的Dict使用了新的数据结构, 使Python新Dict的内存占用也比老的Dict少了, 同时新的Dict在遍历时是跟插入顺序是一致的, 具体的实现是, 初始化时会生成两个数组, 插入值时, 在数组二追加当前的数据, 并获得当前追加数据所在的下标A, 然后对key进行哈希取模算出下标B, 最后对数组下标B的值更新为A, 简单的演示如下:
# 初始的结构 # -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, 这样Python的Dict就变为有序的了. 注: 为了保持操作高效, 在删除的时候, 只是把数组1的值设置为-2, 并把数组2对应的值设置为None, 而不去删除它, 在查找时会忽略掉数组1中值为-2的元素， 在遍历时会忽略掉值为None的元素.
通过上面的了解后, 可以使用Python来写一个新版Dict的实现, 具体说明见注释:
from 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以上がPython での Dict 実装の原理は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
