Python での Dict 実装の原理は何ですか?

1. 順序なし Dict の実装

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 に基づいており、シリアル化する必要があるため、オープン アドレッシング方式が選択されました。

比較すると、リンク リスト方式とオープン サーチ方式の両方が見つかります。どちらもハッシュ競合の解決策です。データを格納する配列が十分に大きい場合、ハッシュ競合が発生する可能性があります。非常に小さくなり、データを頻繁に拡張および移行する必要はありませんが、より多くのスペースを占有します。スペースは非常に大きくなります。したがって、適切なハッシュ テーブル実装の初期値は大きすぎることはできません。初期値

Python の Dict の値は 8 です。さらに、ハッシュ テーブルにはデータの配列を保存できる必要もあります。未使用の空席は範囲内で変動するため、スペースの使用量とハッシュ衝突の確率が高くなります。容量は最適な状態に維持されますが、拡張するたびに多大なパフォーマンスを消費するため、毎回変更することはできません。拡張するため、値を決定する必要があります。未使用/使用率がこの値に達すると、容量は自動的に変更されますPython の Dict では、この値は 2/3 です。つまり、Dict が使用されると、スペースの 2/3 が占有された後、新しい最適なバランスに達するために自動的に拡張されます。同時に、拡張ごとのキーの移行数を減らすために、拡張後の総容量は拡張前の総容量の 3 分の 1 倍にする必要があり、この場合、キーの数は半分だけで済みます。

ハッシュ テーブルを 2 倍にしてもキーの半分のみが移行される理由は、配列内のキーの添字がハッシュ値のモジュロ実装によって取得されるためです (たとえば、ハッシュ テーブルの容量は次のとおりです)。図 8 では、ハッシュ値 20 のキーはモジュロ値 4 をとり、ハッシュ テーブルを拡張すると長さは 16 になります。このとき、モジュロ結果は 4 のままです。ハッシュ値が 11 のキーのモジュロ値は 3 であり、展開後のモジュロ値は 11 になります。ハッシュ テーブルを拡張した後、ハッシュ値が元の容量より大きいキーは移行する必要がなく、ハッシュ値が容量より小さいキーは移行する必要があることが明確にわかります。

しかし、上記のステートメントに従う場合、次の配列のようなオープン アドレッシング方法には依然として問題が発生します。

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一直循环着, 这样跳着插数据就能完美解决上面场景的问题.

2.有序Dict的原理

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的元素.

3.有序字典的实现

通过上面的了解后, 可以使用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 サイトの他の関連記事を参照してください。