前記

在Python中, Dict是一系列由鍵和值配對(duì)組成的元素的集合, 它是一個(gè)可變?nèi)萜髂Ｐ?，可以存?chǔ)任意類型對(duì)象. Dict的存取速度非常的快, 而這全靠他的哈希算法的功勞, 在Python3.6之前Dict是無序的, 在Python3.6中絕大部分是有序的, 在Python3.7以及之后則是絕對(duì)有序的, 而且占用內(nèi)存空間更少, 對(duì)于萬物基于Dict的Python,這算一個(gè)大優(yōu)化, 也讓我好奇Python是如何實(shí)現(xiàn)哈希有序的.

1.無序Dict的實(shí)現(xiàn)

Dict在查找key時(shí)非常的快， 這得益于它的使用空間換時(shí)間思路和哈希實(shí)現(xiàn)。的在讀取和寫入Key時(shí)， 都會(huì)對(duì)Key進(jìn)行哈希計(jì)算(所以要求Key都是不可變類型，如果是可變類型，就無法計(jì)算出他的哈希值了), 然后根據(jù)計(jì)算的值, 與當(dāng)前的數(shù)組空間長(zhǎng)度進(jìn)行取模計(jì)算, 得到的值就是當(dāng)前Key在數(shù)組的下標(biāo), 最后通過下標(biāo)就可以以O(shè)(1)的時(shí)間復(fù)雜度讀取值. 這種實(shí)現(xiàn)非常棒, 也是分布式的常見做法, 但也有問題, 如果數(shù)組滿了怎么辦或者是不同的Key, 但是哈希結(jié)果是一樣的怎么辦?

針對(duì)第一個(gè)問題的解決辦法是在合適的時(shí)候進(jìn)行擴(kuò)容, 在Python中, 當(dāng)Dict中放置的數(shù)量占容量的2/3時(shí), Dict就會(huì)開始擴(kuò)容, 擴(kuò)容后的總?cè)萘渴菙U(kuò)容之前的一倍, 這是為了減少頻繁擴(kuò)容， 導(dǎo)致key的遷移次數(shù)變多;

而針對(duì)第二個(gè)問題則有兩個(gè)解法:

鏈接法: 原本數(shù)組里面存的是Key對(duì)應(yīng)的值, 而鏈接法的數(shù)組存的是一個(gè)數(shù)組, 這個(gè)數(shù)組存了一個(gè)包含key和對(duì)應(yīng)值的數(shù)組, 如下所示, 假設(shè)key1和key2的哈希結(jié)果都是0, 那就會(huì)插入到數(shù)組的0下標(biāo)中, key1在0下標(biāo)的數(shù)組的第一位, 而key2在插入時(shí),發(fā)現(xiàn)已經(jīng)存在key1了, 再用key2與key1進(jìn)行對(duì)比, 發(fā)現(xiàn)它們的key其實(shí)是不一樣的, 那就在0下標(biāo)進(jìn)行追加.

array = [
	[
    # 分別為key, hash值， 數(shù)值
		('key1', 123, 123),
		('key2', 123, 123)
	],
	[
		('key3', 123, 123)
	]
]

開發(fā)尋址法: 開發(fā)尋址法走的是另外一個(gè)思路, 采取借用的思想, 在插入數(shù)據(jù)時(shí)， 如果遇到了沖突那就去使用當(dāng)前下標(biāo)的下一位, 如果下一位還是沖突, 就繼續(xù)用下一位.在查找數(shù)據(jù)時(shí)則會(huì)對(duì)哈希值對(duì)應(yīng)的key進(jìn)行比較， 如果有值且對(duì)不上就找下一位， 直到或者空位找到為止。

上面兩個(gè)的方案的實(shí)現(xiàn)都很簡(jiǎn)單, 對(duì)比下也很容易知道他們的優(yōu)缺點(diǎn):

鏈表法的優(yōu)點(diǎn):

• 刪除記錄方便, 直接處理數(shù)組對(duì)應(yīng)下標(biāo)的子數(shù)組即可.
• 平均查找速度快, 如果沖突了, 只需要對(duì)子數(shù)組進(jìn)行查詢即可

鏈表法的缺點(diǎn):

• 用到了指針, 導(dǎo)致了查詢速度會(huì)偏慢一點(diǎn), 內(nèi)存占用可能會(huì)較高, 不適合序列化. 而開放尋址法的優(yōu)缺點(diǎn)是跟鏈表法反過來的, 由于Python萬物基于Dict, 且都需要序列化, 所以選擇了開放尋址法.

通過對(duì)比鏈表法和開放尋執(zhí)法都可以發(fā)現(xiàn), 他們都是針對(duì)哈希沖突的一個(gè)解決方案, 如果存數(shù)據(jù)的數(shù)組夠大, 那么哈希沖突的可能性就會(huì)很小, 不用頻繁擴(kuò)容遷移數(shù)據(jù), 但是占用的空間就會(huì)很大.所以一個(gè)好的哈希表實(shí)現(xiàn)初始值都不能太大, 在Python的Dict的初始值是8. 另外哈希表還需要讓存數(shù)據(jù)的數(shù)組的未使用空位保持在一個(gè)范圍值內(nèi)波動(dòng), 這樣空間的使用和哈希沖突的概率都會(huì)保持在一個(gè)最優(yōu)的情況, 但由于每次擴(kuò)容都會(huì)消耗很大的性能, 也不能每次更改都進(jìn)行一次擴(kuò)容, 所以需要確定一個(gè)值, 當(dāng)未使用/使用的占比達(dá)到這個(gè)值時(shí), 就自動(dòng)擴(kuò)容, 在Python的Dict中這個(gè)值是2/3. 也就是當(dāng)Dict里面使用了2/3的空間后, 他就會(huì)自動(dòng)擴(kuò)容, 使他達(dá)到一個(gè)新的最優(yōu)平衡. 同時(shí), 為了減少每次擴(kuò)容時(shí)key的遷移次數(shù), 擴(kuò)容后的總?cè)萘恳欢ㄊ菙U(kuò)容之前的總?cè)萘康囊槐? 這樣的話, key只需要遷移一半的數(shù)量即可.

哈希表擴(kuò)容一倍只會(huì)遷移一半的key的原因是獲取key在數(shù)組的下標(biāo)是通過對(duì)哈希值取模實(shí)現(xiàn)的， 比如一個(gè)哈希表容量為8，一個(gè)哈希值為20的key取模值為4，哈希表擴(kuò)容后長(zhǎng)度變?yōu)?6， 此時(shí)取模結(jié)果還是4。而一個(gè)哈希值為11的key取模值為3， 擴(kuò)容后取模值為11?？梢院苊黠@的看出，擴(kuò)容后原來哈希值大于容量的key都不用做遷移， 而哈希值小于容量的都需要遷移。

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

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

以True代表當(dāng)前數(shù)組的位置已經(jīng)被占用, None代表未被占用, 可以看出當(dāng)前并未滿足使用了數(shù)組的2/3空間, 數(shù)組還未到擴(kuò)容階段。 此時(shí)假設(shè)要插入一個(gè)Key, 剛好落在數(shù)組下標(biāo)4, 那么插入的時(shí)候就要一直查詢下去, 最后發(fā)現(xiàn)只有數(shù)組下標(biāo)0的位置的空的, 才可以真正的插入數(shù)據(jù). 對(duì)于一個(gè)長(zhǎng)度只有8的數(shù)組, 需要執(zhí)行5次才能插入數(shù)據(jù), 那也太浪費(fèi)性能了, 所以Python要實(shí)現(xiàn)一個(gè)算法, 盡量讓沖突的數(shù)據(jù)插在別的地方. 在源碼中, Python用到了公式x = ((5*y) + 1) % 2**i來實(shí)現(xiàn)跳躍插入沖突數(shù)據(jù). 式子中x為數(shù)組的下一個(gè)坐標(biāo), y為當(dāng)前發(fā)生沖突的坐標(biāo),i為容量系數(shù), 比如初始化時(shí), i為3, 那么容量就是8了, 第一次插入數(shù)據(jù)到坐標(biāo)0沖突時(shí), y = 0, 帶入公式后, 求得x 等于1, 第二次插入數(shù)據(jù)到坐標(biāo)0時(shí), y = 1, 求得x 等于 6, 通過這樣算下去, 可以發(fā)現(xiàn)數(shù)字生成軌跡是0>1>6>7>4>5>2>3>0一直循環(huán)著, 這樣跳著插數(shù)據(jù)就能完美解決上面場(chǎng)景的問題.

2.有序Dict的原理

Python3.6之前說的差不多, 它的數(shù)組大概是長(zhǎng)這樣的, 數(shù)組中存了子數(shù)組, 第一項(xiàng)為hash值, 第二項(xiàng)為key, 第三項(xiàng)為值.

array = [
	[],
	[123456, "key1", 1],
	[],
	[],
	[],
	[234567, "key2", 2],
	[],
	[]
]

這種實(shí)現(xiàn)的空間大小在初始化時(shí)就固定了, 直到下次擴(kuò)容再發(fā)送變化, 在遍歷字典時(shí), 實(shí)際上就是遍歷數(shù)組, 只是把沒有占用的空間進(jìn)行跳過.可以看出這種遍歷的生成的順序只跟哈希結(jié)果相關(guān), 無法跟插入順序相關(guān), 所以這種方法的實(shí)現(xiàn)是無序的(同時(shí)由于每次啟動(dòng)程序時(shí)， 他們的哈希計(jì)算是不一樣的， 所以每次遍歷的順序也就各不相同了).

而在Python3.7之后, Python的Dict使用了新的數(shù)據(jù)結(jié)構(gòu), 使Python新Dict的內(nèi)存占用也比老的Dict少了, 同時(shí)新的Dict在遍歷時(shí)是跟插入順序是一致的, 具體的實(shí)現(xiàn)是, 初始化時(shí)會(huì)生成兩個(gè)數(shù)組, 插入值時(shí), 在數(shù)組二追加當(dāng)前的數(shù)據(jù), 并獲得當(dāng)前追加數(shù)據(jù)所在的下標(biāo)A, 然后對(duì)key進(jìn)行哈希取模算出下標(biāo)B, 最后對(duì)數(shù)組下標(biāo)B的值更新為A, 簡(jiǎn)單的演示如下:

# 初始的結(jié)構(gòu)
# -1代表還未插入數(shù)據(jù)
array_1 = [-1, -1, -1, -1, -1, -1, -1, -1]
array_2 = []


# 插入值后, 他就會(huì)變?yōu)?
array_1 = [-1, 0, -1, -1, -1, 1, -1, -1]
array_2 = [
	[123456, "key1", 1],
	[234567, "key2", 2],
]

可以看出, 數(shù)組2的容量跟當(dāng)前放入的值相等的, 數(shù)組1雖然還會(huì)保持1/3的空閑標(biāo)記位, 但他只保存數(shù)組二的下標(biāo), 占用空間也不多, 相比之前的方案會(huì)節(jié)省一些空間, 同時(shí)在遍歷的時(shí)候可以直接遍歷數(shù)組2, 這樣Python的Dict就變?yōu)橛行虻牧? 注: 為了保持操作高效, 在刪除的時(shí)候, 只是把數(shù)組1的值設(shè)置為-2, 并把數(shù)組2對(duì)應(yīng)的值設(shè)置為None, 而不去刪除它, 在查找時(shí)會(huì)忽略掉數(shù)組1中值為-2的元素， 在遍歷時(shí)會(huì)忽略掉值為None的元素.

3.有序字典的實(shí)現(xiàn)

通過上面的了解后, 可以使用Python來寫一個(gè)新版Dict的實(shí)現(xiàn), 具體說明見注釋:

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  # 初始化數(shù)組大小
        self._load_factor: float = 2 / 3  # 擴(kuò)容因子
        self._index_array: List[int] = [-1 for _ in range(self._init_length)]  # 存放下標(biāo)的數(shù)組
        self._data_array: List[Optional[Tuple[int, Any, Any]]] = []  # 存放數(shù)據(jù)的數(shù)組
        self._used_count: int = 0  # 目前用的量
        self._delete_count: int = 0  # 被標(biāo)記刪除的量

    def _create_new(self):
        """擴(kuò)容函數(shù)"""
        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

        # 這里只是簡(jiǎn)單實(shí)現(xiàn), 實(shí)際上只需要搬運(yùn)一半的數(shù)據(jù)
        for item in old_data_array:
            if item is not None:
                self.__setitem__(item[1], item[2])

    def _get_next(self, index: int):
        """計(jì)算沖突的下一跳，如果下標(biāo)對(duì)應(yīng)的值沖突了, 需要計(jì)算下一跳的下標(biāo)"""
        return ((5*index) + 1) % self._init_length

    def _core(self, key: Any, default_value: Optional[Any] = None) -> Tuple[int, Any, int]:
        """獲取數(shù)據(jù)或者得到可以放新數(shù)據(jù)的方法, 返回值是index_array的索引, 數(shù)據(jù), data_array的索引"""
        index: int = hash(key) % (self._init_length - 1)
        while True:
            data_index: int = self._index_array[index]
            # 如果是-1則代表沒有數(shù)據(jù)
            if data_index == -1:
                break
            # 如果是-2則代表之前有數(shù)據(jù)則不過被刪除了
            elif data_index == -2:
                index = self._get_next(index)
                continue

            _, new_key, default_value = self._data_array[data_index]
            # 判斷是不是對(duì)應(yīng)的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]:
        """模擬實(shí)現(xiàn)keys方法"""
        return [item[1] for item in self._data_array if item is not None]

    def values(self) -> List[Any]:
        """模擬實(shí)現(xiàn)values方法"""
        return [item[2] for item in self._data_array if item is not None]

    def items(self) -> List[Tuple[Any, Any]]:
        """模擬實(shí)現(xiàn)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

到此這篇關(guān)于Python中Dict兩種實(shí)現(xiàn)的原理詳解的文章就介紹到這了,更多相關(guān)Python Dict內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！