您好,登錄后才能下訂單哦!
這篇文章主要介紹“Python中Dict實(shí)現(xiàn)的原理是什么”的相關(guān)知識(shí),小編通過(guò)實(shí)際案例向大家展示操作過(guò)程,操作方法簡(jiǎn)單快捷,實(shí)用性強(qiáng),希望這篇“Python中Dict實(shí)現(xiàn)的原理是什么”文章能幫助大家解決問(wèn)題。
Dict在查找key時(shí)非常的快, 這得益于它的使用空間換時(shí)間思路和哈希實(shí)現(xiàn)。的在讀取和寫入Key時(shí), 都會(huì)對(duì)Key進(jìn)行哈希計(jì)算(所以要求Key都是不可變類型,如果是可變類型,就無(wú)法計(jì)算出他的哈希值了), 然后根據(jù)計(jì)算的值, 與當(dāng)前的數(shù)組空間長(zhǎng)度進(jìn)行取模計(jì)算, 得到的值就是當(dāng)前Key在數(shù)組的下標(biāo), 最后通過(guò)下標(biāo)就可以以O(shè)(1)的時(shí)間復(fù)雜度讀取值. 這種實(shí)現(xiàn)非常棒, 也是分布式的常見做法, 但也有問(wèn)題, 如果數(shù)組滿了怎么辦或者是不同的Key, 但是哈希結(jié)果是一樣的怎么辦?
針對(duì)第一個(gè)問(wèn)題的解決辦法是在合適的時(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è)問(wèn)題則有兩個(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)是跟鏈表法反過(guò)來(lái)的, 由于Python萬(wàn)物基于Dict, 且都需要序列化, 所以選擇了開放尋址法.
通過(guò)對(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)是通過(guò)對(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ò)容后原來(lái)哈希值大于容量的key都不用做遷移, 而哈希值小于容量的都需要遷移。
但是如果按照上面是說(shuō)法, 開放尋址法還是有一個(gè)問(wèn)題的, 比如下面的數(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
來(lá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, 通過(guò)這樣算下去, 可以發(fā)現(xiàn)數(shù)字生成軌跡是0>1>6>7>4>5>2>3>0一直循環(huán)著, 這樣跳著插數(shù)據(jù)就能完美解決上面場(chǎng)景的問(wèn)題.
Python
3.6之前說(shuō)的差不多, 它的數(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)行跳過(guò).可以看出這種遍歷的生成的順序只跟哈希結(jié)果相關(guān), 無(wú)法跟插入順序相關(guān), 所以這種方法的實(shí)現(xiàn)是無(wú)序的(同時(shí)由于每次啟動(dòng)程序時(shí), 他們的哈希計(jì)算是不一樣的, 所以每次遍歷的順序也就各不相同了).
而在Python
3.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的元素.
通過(guò)上面的了解后, 可以使用Python
來(lái)寫一個(gè)新版Dict的實(shí)現(xiàn), 具體說(shuō)明見注釋:
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ù)則不過(guò)被刪除了 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)的原理是什么”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí),可以關(guān)注億速云行業(yè)資訊頻道,小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。