Python中Dict實作的原理是什麼

1.無序Dict的實作

Dict能夠快速找到key，這歸功於它採用的空間換時間策略和雜湊表實作。的在讀取和寫入Key時， 都會對Key進行哈希計算(所以要求Key都是不可變類型，如果是可變類型，就無法計算出他的哈希值了), 然後根據計算的值, 與目前的數組空間長度進行取模計算, 得到的值就是當前Key在數組的下標, 最後通過下標就可以以O(1)的時間複雜度讀取值. 這種實現非常棒, 也是分散式的常見做法, 但也有問題, 如果數組滿了怎麼辦或者是不同的Key, 但是哈希結果是一樣的怎麼辦?

針對第一個問題的解決辦法是在合適的時候進行擴容, 在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的Dict中這個值是2/3. 也就是當Dict裡面使用了2/3的空間後, 他就會自動擴容, 使他達到一個新的最優平衡. 同時, 為了減少每次擴容時key的遷移次數, 擴容後的總容量一定是擴容之前的總容量的一倍, 這樣的話, key只需要遷移一半的數量即可.

哈希表擴容一倍只會遷移一半的key的原因是獲取key在數組的下標是通過對哈希值取模實現的， 例如一個哈希表容量為8，一個哈希值為20的key取模值為4，哈希表擴容後長度變成16， 此時取模結果還是4。而一個雜湊值為11的key取模值為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中文網其他相關文章！