Python中Dict實現的原理是什么

這篇文章主要介紹“Python中Dict實現的原理是什么”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“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?？梢院苊黠@的看出，擴容后原來哈希值大于容量的key都不用做遷移， 而哈希值小于容量的都需要遷移。

但是如果按照上面是說法, 開放尋址法還是有一個問題的, 比如下面的數組:

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實現的原理是什么”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。