Was ist das Prinzip der Dict-Implementierung in Python?

1. Implementierung von ungeordnetem Dict

Dict kann dank seiner Raum-für-Zeit-Strategie und Hash-Tabellenimplementierung schnell Schlüssel finden. Beim Lesen und Schreiben des Schlüssels wird der Schlüssel gehasht (daher muss der Schlüssel ein unveränderlicher Typ sein. Wenn es sich um einen Variablentyp handelt, kann sein Hash-Wert nicht berechnet werden) und dann basierend auf dem berechneten Wert eine Modulo-Berechnung durchführen Mit der aktuellen Array-Raumlänge ist der erhaltene Wert der Index des aktuellen Schlüssels im Array. Schließlich kann der Wert mit einer Zeitkomplexität von O(1) gelesen werden ist ein gängiger Ansatz, aber es gibt auch Probleme. Was soll ich tun, wenn das Array voll ist, oder was soll ich tun, wenn die Hash-Ergebnisse trotz der unterschiedlichen Schlüssel gleich sind? Erweitern Sie die Kapazität zum richtigen Zeitpunkt, wenn die im Dict platzierte Nummer 2/3 der Kapazität ausmacht. Die Gesamtkapazität nach der Erweiterung wird verdoppelt Erweiterung. Dies dient dazu, häufige Erweiterungen zu reduzieren.

Es gibt zwei Lösungen für das zweite Problem:Python中, 当Dict中放置的数量占容量的2/3时, Dict就会开始扩容, 扩容后的总容量是扩容之前的一倍, 这是为了减少频繁扩容， 导致key的迁移次数变多;

而针对第二个问题则有两个解法:

链接法: 原本数组里面存的是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, 且都需要序列化, 所以选择了开放寻址法.

通过对比链表法和开放寻执法都可以发现, 他们都是针对哈希冲突的一个解决方案, 如果存数据的数组够大, 那么哈希冲突的可能性就会很小, 不用频繁扩容迁移数据, 但是占用的空间就会很大.所以一个好的哈希表实现初始值都不能太大, 在Python的Dict的初始值是8. 另外哈希表还需要让存数据的数组的未使用空位保持在一个范围值内波动, 这样空间的使用和哈希冲突的概率都会保持在一个最优的情况, 但由于每次扩容都会消耗很大的性能, 也不能每次更改都进行一次扩容, 所以需要确定一个值, 当未使用/使用的占比达到这个值时, 就自动扩容, 在Python

Link-Methode: Das ursprüngliche Array speichert den entsprechenden Wert zum Schlüssel und zum Array der Link-Methode. Es wird ein Array gespeichert, das den Schlüssel und den entsprechenden Wert enthält, wie unten gezeigt. Unter der Annahme, dass die Hash-Ergebnisse von Schlüssel1 und Schlüssel2 beide 0 sind, wird es eingefügt In den 0-Index des Arrays befindet sich Schlüssel1 an der ersten Position im Index-Array. Als Schlüssel2 eingefügt wurde, wurde festgestellt, dass Schlüssel1 bereits vorhanden war. Dann verglichen wir Schlüssel2 mit Schlüssel1 und stellten fest, dass ihre Schlüssel tatsächlich unterschiedlich waren Wir haben es am 0-Index hinzugefügt.

arrray = [None, None, None, None, True, True, True, True]

Entwicklungsadressierungsmethode: Die Entwicklungsadressierungsmethode übernimmt eine andere Idee und übernimmt die Idee des Ausleihens. Wenn beim Einfügen von Daten ein Konflikt auftritt, wird der nächste verwendet Wenn ein Bit immer noch in Konflikt steht, verwenden Sie weiterhin das nächste Bit. Bei der Suche nach Daten werden die den Hash-Werten entsprechenden Schlüssel verglichen , wird das nächste Bit gefunden, bis ein freies Bit gefunden wird.

Die Implementierung der beiden oben genannten Lösungen ist sehr einfach und ihre Vor- und Nachteile lassen sich durch Vergleich leicht erkennen:🎜🎜Vorteile der verknüpften Listenmethode:🎜

• 🎜Datensätze löschen Praktisch, verarbeiten Sie einfach das Subarray, das dem Index des Arrays entspricht.🎜
• 🎜Die durchschnittliche Suchgeschwindigkeit ist hoch. Wenn ein Konflikt vorliegt, müssen Sie nur das Subarray abfragen🎜li>

🎜 Nachteile der Methode der verknüpften Liste: 🎜

• 🎜Es werden Zeiger verwendet, was zu einer langsameren Abfragegeschwindigkeit und einer höheren Speichernutzung führt, was jedoch nicht der Fall ist Geeignet für die Serialisierung. Die Vor- und Nachteile der Adressierungsmethode sind das Gegenteil der verknüpften Listenmethode. Da in Python alles auf Dict basiert und serialisiert werden muss, wurde die offene Adressierungsmethode gewählt >

🎜Durch den Vergleich der Methode der verknüpften Liste und der Methode der offenen Adressierung können Strafverfolgungsbehörden feststellen, dass sie alle eine Lösung für Hash-Konflikte sind. Wenn das Array, in dem Daten gespeichert werden, groß genug ist, ist die Wahrscheinlichkeit von Hash-Konflikten sehr gering Eine häufige Erweiterung und Migration von Daten ist nicht erforderlich, aber der belegte Speicherplatz kann nicht zu groß sein /code> ist 8. Darüber hinaus muss die Hash-Tabelle auch ungenutzte Räume im Array speichern, die innerhalb eines Wertebereichs schwanken, damit die Raumnutzung und die Wahrscheinlichkeit von Hash-Kollisionen in einem optimalen Zustand bleiben. Da jede Erweiterung viel Leistung verbraucht und die Erweiterung nicht jedes Mal durchgeführt werden kann, muss ein Wert ermittelt werden. Wenn das Verhältnis von ungenutzter/genutzter Kapazität diesen Wert erreicht, wird die Kapazität im Dict von Python automatisch erweitert , dieser Wert beträgt 2/3. Das heißt, wenn 2/3 im Dict verwendet werden, wird der Speicherplatz automatisch erweitert, um gleichzeitig ein neues optimales Gleichgewicht zu erreichen Bei der Anzahl der Schlüsselmigrationen während jeder Erweiterung muss die Gesamtkapazität nach der Erweiterung doppelt so hoch sein wie die Gesamtkapazität vor der Erweiterung. Wenn ja, muss nur die Hälfte der Schlüssel migriert werden 🎜🎜Der Grund, warum die Hash-Tabelle verdoppelt wird, wird nur migriert Die Hälfte der Schlüssel besteht darin, dass der Index des Schlüssels im Array durch Nehmen des Modulo des Hash-Werts erreicht wird, z. B. eines Hashs. Die Kapazität der Hash-Tabelle beträgt 8. Der Modulo-Wert eines Schlüssels mit einem Hash-Wert von 20 ist 4. Nachdem die Hash-Tabelle erweitert wurde, beträgt die Länge 16. Zu diesem Zeitpunkt ist das Modulo-Ergebnis immer noch 4. Ein Schlüssel mit einem Hash-Wert von 11 hat einen Modulo-Wert von 3 und nach der Erweiterung beträgt der Modulo-Wert 11. Es ist deutlich zu erkennen, dass nach der Erweiterung der Hash-Tabelle die Schlüssel, deren Hash-Wert größer als die ursprüngliche Kapazität ist, nicht migriert werden müssen, während die Schlüssel, deren Hash-Wert kleiner als die Kapazität ist, migriert werden müssen. 🎜🎜Aber wenn Sie der obigen Aussage folgen, gibt es immer noch ein Problem mit der offenen Adressierungsmethode, wie zum Beispiel das folgende Array:🎜

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

Das obige ist der detaillierte Inhalt vonWas ist das Prinzip der Dict-Implementierung in Python?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!