資訊專欄INFORMATION COLUMN
摘要：表容量更新的前后，它的鍵之間的相對順序是會變化的，因此字典的元素是無序的。而且字典擴(kuò)容和縮容時要按照的順序來保持字典始終有序。舊的字典總會預(yù)留大于的容量的位置，防止碰撞過多影響效率。
python3.7的字典是有序的 舊結(jié)構(gòu)
python3.7之前的字典結(jié)構(gòu)，經(jīng)典粗暴的hash表實現(xiàn)方式，這樣的話每次hash表的擴(kuò)容和縮容都可能導(dǎo)致hash值的改變。
hash表容量更新的前后，它的鍵之間的相對順序是會變化的，因此字典的元素是無序的。舊結(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ù)組實現(xiàn)) 和 Entries(實體，PyDictObject類型) 兩種結(jié)構(gòu)組成。
當(dāng)插入一個數(shù)據(jù)時，先計算數(shù)據(jù)對應(yīng)的hash值并映射成 Indices 數(shù)組的一個下標(biāo)，沒有沖突的話就將另一個值 Entries_index(暫時這么叫吧) 填入Indices數(shù)組中下標(biāo)對應(yīng)的位置。并在Entries后面追加一行記錄，類似 hash值, key值, value值 。如果沖突的話可以用基本的解決沖突的辦法，這里不贅述了。
這種方法，字典 增刪改查的時間復(fù)雜度 會有以前的O(1) 變?yōu)镺(2)，因為多了一步查找的過程。而且字典擴(kuò)容和縮容時要按照Indices的順序來保持字典始終有序。
但是至少有兩個優(yōu)化。
字典占用的內(nèi)存變小了。舊的字典總會預(yù)留大于 1/3的容量的hash位置，防止hash碰撞過多影響效率?，F(xiàn)在則不必預(yù)留。
字典有序了。
源碼見：
dictobject.h
dictobject.c
記于：2019/07/23
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/45229.html
摘要：有序字典簡介示例有序字典和通常字典類似，只是它可以記錄元素插入其中的順序，而一般字典是會以任意的順序迭代的。 有序字典-OrderedDict簡介 示例 有序字典和通常字典類似，只是它可以記錄元素插入其中的順序，而一般字典是會以任意的順序迭代的。參見下面的例子: import collections print Regular dictionary: d = {} d[a] = ...
摘要：并且中會顯示，的版本在中已經(jīng)不再支持了。接下來再看下以上版本的效果以版本為例從上圖可以看出，在新的版本中，針對的存儲已經(jīng)變?yōu)橛行颍诒闅v和打印的時候，會按照存儲的順序進(jìn)行取值。再補(bǔ)充一點(diǎn)之前介紹到，在字典中，是唯一的。 之前寫了文章介紹python中的列表和字典，在文章中描述到了python...
摘要：哈希對象哈希對象的可選編碼分別是和。編碼的哈希對象編碼的哈希對象使用壓縮列表作為底層實現(xiàn)。關(guān)于哈希編碼轉(zhuǎn)換的函數(shù)，可以參考，源碼如下是原始對象，是目標(biāo)編碼。對應(yīng)源碼如下對象元素數(shù)量為，或者總結(jié)哈希對象有和編碼。 繼續(xù)擼我們的對象和數(shù)據(jù)類型。 上節(jié)我們一起認(rèn)識了字符串和列表，接下來還有哈希、集合和有序集合。 1 哈希對象 哈希對象的可選編碼分別是：ziplist 和 hashtable。...
摘要：我們用函數(shù)，來簡單快捷地創(chuàng)建這個字典輸出結(jié)果與原先代碼一致。示例代碼如下版本為無序字典有序字典輸出的結(jié)果為無序字典有序字典默認(rèn)字典是內(nèi)建類的一個子類，第一個參數(shù)為屬性提供初始值，默認(rèn)為。 ??字典（dict）結(jié)構(gòu)是Python中常用的數(shù)據(jù)結(jié)構(gòu)，筆者結(jié)合自己的實際使用經(jīng)驗，對字典方面的相關(guān)知識做個小結(jié)，希望能對讀者一些啟發(fā)~ 創(chuàng)建字典 ??常見的字典創(chuàng)建方法就是先建立一個空字典，然后逐一...
閱讀 3675·2023-04-26 01:43
閱讀 3046·2021-10-14 09:42
閱讀 5732·2021-09-30 09:59
閱讀 2232·2021-09-04 16:40
閱讀 1278·2019-08-30 15:52
閱讀 899·2019-08-29 17:09
閱讀 2111·2019-08-26 13:37
閱讀 3594·2019-08-26 10:20
