成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

python3.7的字典是有序的

iamyoung001 / 3206人閱讀

摘要：表容量更新的前后，它的鍵之間的相對(duì)順序是會(huì)變化的，因此字典的元素是無序的。而且字典擴(kuò)容和縮容時(shí)要按照的順序來保持字典始終有序。舊的字典總會(huì)預(yù)留大于的容量的位置，防止碰撞過多影響效率。

python3.7的字典是有序的 舊結(jié)構(gòu)

python3.7之前的字典結(jié)構(gòu)，經(jīng)典粗暴的hash表實(shí)現(xiàn)方式，這樣的話每次hash表的擴(kuò)容和縮容都可能導(dǎo)致hash值的改變。

hash表容量更新的前后，它的鍵之間的相對(duì)順序是會(huì)變化的，因此字典的元素是無序的。舊結(jié)構(gòu)類似下面

--+-------------------------------+
  | 哈希值 (hash)  鍵 (key)  值 (value)
--+-------------------------------+
0 |    hash0      key0    value0
--+-------------------------------+
1 |    hash1      key1    value1
--+-------------------------------+
2 |    hash2      key2    value2
--+-------------------------------+
. |           ...
__+_______________________________+
新結(jié)構(gòu) 
Indices
----------------------------------------------------
None | index0 | None | None | index2 | None | index1 ...
----------------------------------------------------

Entries
--------------------
hash0   key0  value0
---------------------
hash1   key1  value1
---------------------
hash2   key2  value2
---------------------
        ...
---------------------

新結(jié)構(gòu)由 Indices(索引，數(shù)組實(shí)現(xiàn)) 和 Entries(實(shí)體，PyDictObject類型) 兩種結(jié)構(gòu)組成。

當(dāng)插入一個(gè)數(shù)據(jù)時(shí)，先計(jì)算數(shù)據(jù)對(duì)應(yīng)的hash值并映射成 Indices 數(shù)組的一個(gè)下標(biāo)，沒有沖突的話就將另一個(gè)值 Entries_index(暫時(shí)這么叫吧) 填入Indices數(shù)組中下標(biāo)對(duì)應(yīng)的位置。并在Entries后面追加一行記錄，類似 hash值, key值, value值 。如果沖突的話可以用基本的解決沖突的辦法，這里不贅述了。

這種方法，字典 增刪改查的時(shí)間復(fù)雜度 會(huì)有以前的O(1) 變?yōu)镺(2)，因?yàn)槎嗔艘徊讲檎业倪^程。而且字典擴(kuò)容和縮容時(shí)要按照Indices的順序來保持字典始終有序。

但是至少有兩個(gè)優(yōu)化。

字典占用的內(nèi)存變小了。舊的字典總會(huì)預(yù)留大于 1/3的容量的hash位置，防止hash碰撞過多影響效率?，F(xiàn)在則不必預(yù)留。

字典有序了。

源碼見：
dictobject.h

dictobject.c

記于：2019/07/23

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/45229.html

相關(guān)文章

  • Python 有序字典簡(jiǎn)介

    摘要：有序字典簡(jiǎn)介示例有序字典和通常字典類似，只是它可以記錄元素插入其中的順序，而一般字典是會(huì)以任意的順序迭代的。 有序字典-OrderedDict簡(jiǎn)介 示例 有序字典和通常字典類似，只是它可以記錄元素插入其中的順序，而一般字典是會(huì)以任意的順序迭代的。參見下面的例子: import collections print Regular dictionary: d = {} d[a] = ...

    DrizzleX 評(píng)論0 收藏0

  • Python中的字典到底是有序的嗎

    摘要：并且中會(huì)顯示，的版本在中已經(jīng)不再支持了。接下來再看下以上版本的效果以版本為例從上圖可以看出，在新的版本中，針對(duì)的存儲(chǔ)已經(jīng)變?yōu)橛行颍诒闅v和打印的時(shí)候，會(huì)按照存儲(chǔ)的順序進(jìn)行取值。再補(bǔ)充一點(diǎn)之前介紹到，在字典中，是唯一的。 之前寫了文章介紹python中的列表和字典，在文章中描述到了python...

    aervon 評(píng)論0 收藏0

  • 跟著大彬讀源碼 - Redis 6 - 對(duì)象和數(shù)據(jù)類型（下）

    摘要：哈希對(duì)象哈希對(duì)象的可選編碼分別是和。編碼的哈希對(duì)象編碼的哈希對(duì)象使用壓縮列表作為底層實(shí)現(xiàn)。關(guān)于哈希編碼轉(zhuǎn)換的函數(shù)，可以參考，源碼如下是原始對(duì)象，是目標(biāo)編碼。對(duì)應(yīng)源碼如下對(duì)象元素?cái)?shù)量為，或者總結(jié)哈希對(duì)象有和編碼。 繼續(xù)擼我們的對(duì)象和數(shù)據(jù)類型。 上節(jié)我們一起認(rèn)識(shí)了字符串和列表，接下來還有哈希、集合和有序集合。 1 哈希對(duì)象 哈希對(duì)象的可選編碼分別是：ziplist 和 hashtable。...

    YFan 評(píng)論0 收藏0

  • Python字典小結(jié)

    摘要：我們用函數(shù)，來簡(jiǎn)單快捷地創(chuàng)建這個(gè)字典輸出結(jié)果與原先代碼一致。示例代碼如下版本為無序字典有序字典輸出的結(jié)果為無序字典有序字典默認(rèn)字典是內(nèi)建類的一個(gè)子類，第一個(gè)參數(shù)為屬性提供初始值，默認(rèn)為。 ??字典（dict）結(jié)構(gòu)是Python中常用的數(shù)據(jù)結(jié)構(gòu)，筆者結(jié)合自己的實(shí)際使用經(jīng)驗(yàn)，對(duì)字典方面的相關(guān)知識(shí)做個(gè)小結(jié)，希望能對(duì)讀者一些啟發(fā)~ 創(chuàng)建字典 ??常見的字典創(chuàng)建方法就是先建立一個(gè)空字典，然后逐一...

    BoYang 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<