Python에서 Dict 구현의 원리는 무엇입니까?

1. 순서가 지정되지 않은 Dict 구현

Dict는 시공간 전략과 해시 테이블 구현 덕분에 빠르게 키를 찾을 수 있습니다. 키를 읽고 쓸 때 키는 해시됩니다(따라서 키는 불변 유형이어야 합니다. 변수 유형인 경우 해시 값을 계산할 수 없습니다). 그런 다음 계산된 값을 기준으로 현재 배열 공간 길이는 모듈식으로 계산되며, 얻은 값은 배열에 있는 현재 키의 첨자입니다. 마지막으로 첨자를 통해 값을 O(1)의 시간 복잡도로 읽을 수 있습니다. 분산형이 일반적인 접근 방식이지만 문제도 있습니다. 배열이 가득 차면 어떻게 해야 하나요? 아니면 키가 달라도 해시 결과가 동일하면 어떻게 해야 하나요?

첫 번째 문제에 대한 해결책은 다음과 같습니다. 적절한 시점에 용량을 확장합니다. Python에서는 Dict에 배치된 숫자가 용량의 2/3를 차지하면 Dict는 확장 후 총 용량이 두 배가 되기 전에 확장되기 시작합니다. 확장 잦은 확장을 줄이기 위한 것입니다. 결과적으로 키 마이그레이션 수가 증가합니다.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

두 번째 문제에 대한 해결책은 두 가지가 있습니다.

링크 방법: 원본 배열은 해당 값을 저장합니다. Key에, 그리고 링크 메소드의 배열이 저장되는 것은 배열입니다. 이 배열은 아래와 같이 key와 해당 값을 포함하는 배열을 저장합니다. key1과 key2의 해시 결과가 모두 0이라고 가정하면 삽입됩니다. Key1은 0에 있습니다. 첨자 배열의 첫 번째 위치에 key2가 삽입되면 key1이 이미 존재하는 것으로 확인됩니다. 그런 다음 key2와 key1을 비교하여 실제로 키가 다르다는 것을 확인합니다. 첨자 0에 붙습니다.

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

개발 주소 지정 방법: 개발 주소 지정 방법은 데이터를 삽입할 때 충돌이 발생하면 다음 숫자를 차용하는 아이디어를 채택합니다. 현재 첨자가 사용되며, 한 비트가 여전히 충돌하면 다음 비트를 계속 사용합니다. 데이터 검색 시 해시 값에 해당하는 키를 비교하여 일치하지 않는 경우. 빈 비트가 발견될 때까지 다음 비트가 발견됩니다. 🎜🎜위 두 솔루션의 구현은 매우 간단하며 비교를 통해 장점과 단점을 쉽게 알 수 있습니다.🎜🎜연결된 목록 방법의 장점:🎜

• 🎜기록 삭제 편리합니다. 배열의 첨자에 해당하는 하위 배열만 처리하면 됩니다.🎜
• 🎜평균 검색 속도가 빠릅니다. 충돌이 있는 경우 하위 배열만 쿼리하면 됩니다.🎜

🎜 연결 목록 방법의 단점: 🎜

• 🎜포인터가 사용되므로 쿼리 속도가 느려지고 메모리 사용량이 많아지며 직렬화에 적합합니다. 주소 지정 방식의 장점과 단점은 연결 목록 방식과 반대입니다. Python의 모든 내용은 Dict를 기반으로 하고 직렬화되어야 하므로 개방형 주소 지정 방식을 선택했습니다. 🎜

🎜연결된 목록 방법과 공개 주소 지정 방법을 비교하면 법 집행 기관은 모두 해시 충돌에 대한 솔루션임을 알 수 있습니다. 데이터를 저장하는 배열이 충분히 크면 해시 충돌 가능성이 매우 작습니다. 빈번한 데이터 확장 및 마이그레이션은 필요하지 않지만 차지하는 공간은 매우 큽니다. 따라서 좋은 해시 테이블 구현의 초기 값은 Python</에서 너무 클 수 없습니다. code>는 8입니다. 또한 해시 테이블은 데이터를 저장하는 배열에서 사용되지 않는 공간을 유지해야 하며, 이를 통해 공간 사용 및 해시 충돌 가능성이 최적의 상황으로 유지됩니다. , 각각의 확장은 많은 성능을 소비하므로 변경될 때마다 확장할 수 없으므로 값을 결정해야 합니다. 미사용/사용 비율이 이 값에 도달하면 <의 Dict에서 용량이 자동으로 확장됩니다. code>Python, 이 값은 2/3입니다. 즉, Dict에서 2/3을 사용하면 공간이 할당된 후 자동으로 확장되어 동시에 새로운 최적의 균형에 도달합니다. 확장할 때마다 키 마이그레이션 수를 줄이려면 확장 후 총 용량이 확장 전 총 용량의 두 배가 되어야 하므로, 그렇다면 키 수의 절반만 마이그레이션하면 됩니다. 🎜🎜해시 테이블을 두 배로 늘리는 이유. 키의 절반만 마이그레이션한다는 것은 해시와 같은 해시 값의 모듈로를 취하여 배열에 있는 키의 첨자를 얻는다는 것입니다. 해시 테이블의 용량은 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!