是的，字典成了有序的数据类型

从Python 3.7开始，字典类型被修改为有序的数据类型。这意味着字典中的键值对会按照它们被插入的顺序进行存储，并且在遍历字典时会按照插入顺序返回键值对。

在早期的Python版本中，字典是无序的数据类型，这意味着字典中的键值对的顺序是不确定的，并且在遍历字典时也不会按照插入顺序返回键值对。这是因为在早期版本中，字典的实现使用了哈希表来存储键值对，而哈希表是一种无序的数据结构。

在Python 3.7中，字典的实现被修改为使用双向链表和哈希表的混合结构来存储键值对。这种新的实现方式保持了哈希表的快速查找特性，同时使用双向链表来保持键值对的插入顺序。因此，从Python 3.7开始，字典成为了有序的数据类型。

需要注意的是，虽然从Python 3.7开始字典是有序的数据类型，但在早期版本中，字典仍然是无序的。如果要确保字典中的键值对按照插入顺序进行存储和遍历，建议使用Python 3.7及更高版本。

“Compact Dict”的概念

进一步来说，从Python 3.7开始，字典类型的实现基于一个叫做“Compact Dict”的概念。这个概念基于两个关键想法：

1. 紧凑性：Compact Dict的实现尽可能地减少了每个字典实例所需的内存。在早期的Python版本中，字典类型的实现会为每个键值对分别分配内存，因此对于包含大量键值对的字典，会占用大量内存。Compact Dict使用更小的结构来存储每个键值对，从而减少了内存占用。
2. 有序性：Compact Dict使用了一个叫做“插入顺序链表”的数据结构来实现字典的有序性。插入顺序链表是一个双向链表，用于按照插入顺序存储字典中的键。这样可以保证在遍历字典时，返回的键值对会按照插入顺序返回。

需要注意的是，虽然Compact Dict是有序的，但是它并不是完全有序的。具体来说，Compact Dict会根据内存管理和哈希表的性能考虑，定期重建哈希表，这可能会导致字典中的元素重新排序。因此，在使用Compact Dict时，不能依赖于字典中元素的顺序是固定不变的。

OrderedDict 完全有序的字典类型

除了字典类型，Python 3.7还引入了一个新的数据类型叫做OrderedDict，它是一个完全有序的字典类型。OrderedDict在实现上使用了一个普通的字典和一个双向链表来存储键值对，可以保证键值对的顺序不会改变。如果需要强制保证字典中键值对的顺序，可以使用OrderedDict。

应该何时使用Compact Dict和OrderedDic ?

假设你有一个Python程序需要存储大量的键值对，而且你希望在保持插入顺序的同时最小化内存使用。在这种情况下，应该选择Compact Dict，因为它能够按照插入顺序提供有序的访问，并且使用的内存比OrderedDict少。

例如，考虑以下代码，它创建了一个Compact Dict和一个OrderedDict来存储相同的键值对：

from sys import getsizeof
from collections import OrderedDict

# 创建一个Compact Dict
compact_dict = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}
compact_dict_size = getsizeof(compact_dict)

# 创建一个OrderedDict
ordered_dict = OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)])
ordered_dict_size = getsizeof(ordered_dict)

print(f'Compact Dict大小: {compact_dict_size} 字节')
print(f'OrderedDict大小: {ordered_dict_size} 字节')

这段代码的输出结果是：

Compact Dict大小: 232 字节
OrderedDict大小: 1056 字节

可以看到，Compact Dict使用的内存远少于OrderedDict。这是因为Compact Dict的实现针对内存使用进行了优化，而OrderedDict的实现则针对保持顺序进行了优化。

但是，如果需要保证字典中的条目顺序，即使在修改后也是如此，应该使用OrderedDict。例如，如果需要确保字典中的条目始终按字母顺序排列，应该使用OrderedDict。

如果我需要在字典中存储大量数据，但不需要保持插入顺序，应该使用哪种字典？

如果你需要存储大量数据，但不需要保持插入顺序，那么应该使用Python标准库中的普通字典（dict）。普通字典是Python最基本的键值对数据结构，也是Python内置数据类型中最常用的数据类型之一。它的实现使用哈希表，可以在O(1)时间内进行插入、查找和删除操作，因此非常高效。

与Compact Dict和OrderedDict不同，普通字典没有保证插入顺序，因此可以更快地进行插入和删除操作，也占用更少的内存。如果不需要保持插入顺序，使用普通字典是最好的选择。

例如，下面的代码创建了一个普通字典，并向其中添加100万个键值对：

import random

# 创建一个普通字典
my_dict = {}

# 向字典中添加100万个键值对
for i in range(1000000):
    key = random.randint(1, 1000000)
    value = random.randint(1, 100)
    my_dict[key] = value

这段代码使用random模块生成了100万个随机的键值对，并将它们添加到一个普通字典中。由于普通字典的实现非常高效，因此这个操作可以在很短的时间内完成，并且占用的内存也非常少。

总之，如果不需要保持插入顺序，使用普通字典是最好的选择。如果需要保持插入顺序，可以使用Compact Dict或OrderedDict。

Compact Dict和OrderedDict分别有什么特点和适用场景?

Compact Dict和OrderedDict是Python标准库中的两种字典类型，它们分别具有不同的特点和适用场景。

1. Compact Dict

   Compact Dict是从Python 3.7开始引入的，它是一种紧凑且有序的字典类型。Compact Dict使用哈希表存储键值对，同时使用一个插入顺序链表来维护键的插入顺序。它比OrderedDict更快、更节省内存，但是不能保证元素的顺序稳定，因为哈希表在重建时可能会改变顺序。

   适用场景：

• 适合存储大量的数据，但不需要保持元素顺序。Compact Dict的实现非常紧凑，因此可以节省大量的内存。
• 适合进行快速插入、删除和查找操作。由于Compact Dict使用哈希表存储元素，因此可以在O(1)时间内完成这些操作。

• 适合需要保持元素顺序的场景。例如，需要按照插入顺序遍历字典，或者需要确保元素在字典中的顺序不会改变。
• 适合存储较少的数据，或者对内存占用没有太高要求的场景。由于OrderedDict使用了双向链表来维护元素顺序，因此它的内存占用比Compact Dict要更高。

总结

总之，如果需要保持元素顺序，应该使用OrderedDict；如果不需要保持元素顺序，并且需要快速地进行插入、删除和查找操作，应该使用Compact Dict。