python3.7的字典是有序的

iamyoung001 發布于2019-07-31 11:30 / 3191人閱讀

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

python3.7的字典是有序的 舊結構

python3.7之前的字典結構，經典粗暴的hash表實現方式，這樣的話每次hash表的擴容和縮容都可能導致hash值的改變。

hash表容量更新的前后，它的鍵之間的相對順序是會變化的，因此字典的元素是無序的。舊結構類似下面

--+-------------------------------+
  | 哈希值 (hash)  鍵 (key)  值 (value)
--+-------------------------------+
0 |    hash0      key0    value0
--+-------------------------------+
1 |    hash1      key1    value1
--+-------------------------------+
2 |    hash2      key2    value2
--+-------------------------------+
. |           ...
__+_______________________________+

新結構

Indices
----------------------------------------------------
None | index0 | None | None | index2 | None | index1 ...
----------------------------------------------------

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

新結構由 Indices(索引，數組實現) 和 Entries(實體，PyDictObject類型) 兩種結構組成。

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

這種方法，字典 增刪改查的時間復雜度會有以前的O(1) 變為O(2)，因為多了一步查找的過程。而且字典擴容和縮容時要按照Indices的順序來保持字典始終有序。

但是至少有兩個優化。

字典占用的內存變小了。舊的字典總會預留大于 1/3的容量的hash位置，防止hash碰撞過多影響效率。現在則不必預留。

字典有序了。

源碼見：
dictobject.h

dictobject.c

記于：2019/07/23

GPU云服務器云服務器 java 集合有序的 html的有序li 字典的使用字典的鍵值

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/45229.html

Python 有序字典簡介

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

DrizzleX 2019-07-31 10:54 評論0 收藏0
Python中的字典到底是有序的嗎

摘要：并且中會顯示，的版本在中已經不再支持了。接下來再看下以上版本的效果以版本為例從上圖可以看出，在新的版本中，針對的存儲已經變為有序，在遍歷和打印的時候，會按照存儲的順序進行取值。再補充一點之前介紹到，在字典中，是唯一的。之前寫了文章介紹python中的列表和字典，在文章中描述到了python...

aervon 2021-09-28 09:36 評論0 收藏0
跟著大彬讀源碼 - Redis 6 - 對象和數據類型（下）

摘要：哈希對象哈希對象的可選編碼分別是和。編碼的哈希對象編碼的哈希對象使用壓縮列表作為底層實現。關于哈希編碼轉換的函數，可以參考，源碼如下是原始對象，是目標編碼。對應源碼如下對象元素數量為，或者總結哈希對象有和編碼。繼續擼我們的對象和數據類型。上節我們一起認識了字符串和列表，接下來還有哈希、集合和有序集合。 1 哈希對象哈希對象的可選編碼分別是：ziplist 和 hashtable。...

YFan 2019-08-06 13:45 評論0 收藏0
Python字典小結

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

BoYang 2019-07-31 11:13 評論0 收藏0