应用编程/字典和集合

数据结构

在计算机科学中，数据结构是一种数据组织、管理和存储格式，它允许高效地访问和修改。^[1][2][3]更准确地说，数据结构是数据值的集合，它们之间的关系以及可以应用于数据的函数或操作。^[4]

数据结构提供了一种有效管理大量数据的机制，用于大型数据库和互联网索引服务等用途。通常，高效的数据结构是设计高效算法的关键。一些正式的设计方法和编程语言强调数据结构，而不是算法，作为软件设计中的主要组织因素。数据结构可用于组织存储在主内存和辅助存储器中的信息的存储和检索。^[5]

数据结构通常基于计算机能够在它的内存中的任何位置获取和存储数据的能力，该位置由一个指针指定 - 一个表示内存地址的位串，它本身可以存储在内存中并由程序操作。因此，数组和记录数据结构基于对数据项地址进行算术运算来计算，而链接数据结构基于将数据项地址存储在结构本身中。

数据结构的实现通常需要编写一组过程，这些过程创建和操作该结构的实例。数据结构的效率不能与这些操作分开分析。这一观察促使了抽象数据类型的理论概念，抽象数据类型是一种通过可以在其上执行的操作以及这些操作的数学属性（包括其空间和时间成本）来间接定义的数据结构。^[6]

存在许多类型的数据结构，通常构建在更简单的原始数据类型之上：^[7]

• 数组是一系列按特定顺序排列的元素，通常都是相同类型（取决于语言，单个元素要么都被强制为相同类型，要么可以是几乎任何类型）。元素是使用整数索引来访问的，以指定需要哪个元素。典型的实现为数组的元素分配连续的内存字（但这并不总是必需的）。数组可以是固定长度的，也可以是可调整大小的。
• 链表（也称为列表）是任何类型的数据元素的线性集合，称为节点，每个节点本身都有一个值，并指向链表中的下一个节点。链表相对于数组的主要优势在于，始终可以高效地插入和删除值，而无需重新定位列表的其余部分。但是，某些其他操作，例如对某个元素的随机访问，在列表上的速度比在数组上慢。
• 记录（也称为元组或结构体）是聚合数据结构。记录是一个包含其他值的价值，通常是固定数量和顺序，通常由名称索引。记录的元素通常称为字段或成员。
• 联合体是一种数据结构，它指定其实例中可能存储的许多允许的原始类型中的哪一个，例如浮点数或长整数。与记录形成对比，记录可以被定义为包含一个浮点数和一个整数；而在联合体中，一次只有一个值。分配足够的存储空间来容纳最宽的成员数据类型。
• 标记联合体（也称为变体、变体记录、区分联合体或不相交联合体）包含一个附加字段来指示其当前类型，以增强类型安全性。
• 对象是一种数据结构，它包含数据字段，就像记录一样，以及对数据内容进行操作的各种方法。对象是类从分类学中的内存中实例。在面向对象编程的背景下，记录被称为普通的旧数据结构，以将它们与对象区分开来。^[8][9]

字典（数据结构）

在计算机科学中，关联数组、映射、符号表或字典是一种抽象数据类型，由（键，值）对的集合组成，使得每个可能的键在集合中最多出现一次。

与这种数据类型相关的操作允许：^[10][11]

• 将一对添加到集合中；
• 从集合中删除一对；
• 修改现有的一对；
• 查找与特定键关联的值。

实现关联数组提出了字典问题，这是一个经典的计算机科学问题：设计一种数据结构的任务，该结构在“搜索”、“删除”和“插入”操作期间维护一组数据。^[12]解决字典问题的两个主要方案是哈希表和搜索树。^{[10][11][13][14]}在某些情况下，也可以使用直接寻址数组、二叉搜索树或其他更专门的结构来解决问题。

许多编程语言将关联数组作为原始数据类型包含在内，它们在许多其他语言的软件库中可用。内容寻址内存是一种对关联数组的直接硬件级支持的形式。

关联数组有许多应用，包括诸如记忆化和装饰器模式等基本编程模式。^[15]

这个名字并非来自数学中已知的结合律。相反，它源于这样一个事实，即我们将值与键关联起来。

在关联数组中，键和值之间的关联通常被称为“映射”，同一个词映射也可以用来指创建新关联的过程。

通常为关联数组定义的操作有：^[10][11]

• 添加或插入：向集合添加一个新的 $(key,value)$ 对，将新键映射到其新值。此操作的参数是键和值。
• 重新分配：替换集合中已有的 $(key,value)$ 对中的值，将现有键映射到新值。与插入一样，此操作的参数是键和值。
• 删除：从集合中删除 $(key,value)$ 对，取消将给定键与其值之间的映射。此操作的参数是键。
• 查找：查找绑定到给定键的值（如果有）。此操作的参数是键，返回值是操作的结果。如果找不到值，一些关联数组实现会抛出异常，而其他实现则会创建一个具有给定键和值类型默认值（零、空容器...）的键值对。

因此，通常情况下，除了添加或重新分配之外，还存在一个单独的 设置 操作，该操作会在 $(key,value)$ 对不存在时添加一个，否则重新分配它。

此外，关联数组还可能包含其他操作，例如确定映射的数量或构造一个迭代器来遍历所有映射。通常，对于这种操作，返回映射的顺序可能是实现定义的。

多重映射通过允许将多个值与单个键关联来概括关联数组。 双向映射是一种相关的抽象数据类型，其中映射在两个方向上起作用：每个值必须与唯一的键关联，并且第二个查找操作以值作为参数并查找与该值关联的键。

假设图书馆提供的贷款集合在数据结构中表示。图书馆中的每本书一次只能由一位图书馆用户借阅。但是，单个用户可以借阅多本书。因此，关于哪些书借阅给哪些用户的信息可以用关联数组表示，其中书籍是键，用户是值。使用来自 Python 或 JSON 的符号，数据结构将是

{
    "Pride and Prejudice": "Alice",
    "Wuthering Heights": "Alice",
    "Great Expectations": "John"
}

对键“Great Expectations”进行查找操作将返回“John”。如果 John 还回了他的书，这将导致删除操作，而如果 Pat 借阅了一本书，这将导致插入操作，导致不同的状态

{
    "Pride and Prejudice": "Alice",
    "The Brothers Karamazov": "Pat",
    "Wuthering Heights": "Alice"
}

字典的基本定义没有规定顺序。为了保证枚举的固定顺序，通常使用关联数组的有序版本。有序字典有两种含义

• 枚举顺序对于给定的键集始终是确定的，方法是通过排序。对于基于树的实现而言，情况就是这样，其中一个代表是 C++ 的 <map> 容器。
• 枚举顺序与键无关，而是基于插入顺序。这就是 .NET Framework 和 Python 中的“有序字典”的情况。

后一种有序字典的含义更为常见。它们可以使用关联列表实现，或者通过在普通字典之上叠加双向链表来实现。后一种方法，如 CPython 在 3.6 版本之前的版本中使用的方法，具有保持另一种实现的潜在更佳复杂度的优势。CPython 3.6+ 通过将哈希表拆分为一个插入有序的键值对数组和一个稀疏数组（“哈希表”）来使字典有序。

键值数据库

什么是键值数据库？

键值数据库是一种非关系型数据库，它使用简单的键值方法来存储数据。键值数据库将数据存储为键值对的集合，其中键用作唯一标识符。键和值都可以是任何东西，从简单的对象到复杂的复合对象。键值数据库高度可分区，并且允许水平扩展到其他类型的数据库无法达到的规模。

与关系型数据库相比，键值数据库有何不同？

关系型数据库使用表格来组织数据。表是结构，它们对它们保存的记录施加模式。表中的每一列都有一个名称和一个数据类型。每一行代表表中的一个单独的记录或数据项，其中包含每列的值。关系型数据库的名称来自使用元组（如表中的行）来表示有序数据集的数学关系。

这意味着什么？

键值数据库的工作方式与广为人知的关系型数据库 (RDB) 非常不同。RDB 预先定义了数据库中的数据结构，作为包含具有明确定义的数据类型的字段的一系列表格。将数据类型公开给数据库程序，使其能够应用许多优化。相反，键值系统将数据视为单个不透明的集合，每个记录可能具有不同的字段。这提供了相当大的灵活性，并且更紧密地遵循面向对象编程等现代概念。由于可选值不像大多数 RDB 中那样由占位符或输入参数表示，因此键值数据库通常使用更少的内存来存储相同的数据库，这可能在某些工作负载中导致巨大的性能提升。

活动

1) 编写一个程序，创建一个字典，其中键是 2 到 20 之间的偶数整数，值是相应的键乘以它之前的奇数整数。

示例输出：{2: 2, 4: 12, 6: 30, 8: 56...}

2) 编写一个程序，它接受两个列表并将它们合并为一个字典。

示例

list_1 = [5, 10, 15, 20] 

list_2 = ['a', 'b', 'c', 'd']

结果：{5: 'a', 10: 'b', 15: 'c', 20: 'd'}

3) 编写一个程序，它搜索最小值并返回相应的键。

示例

prices = {'Popcorn': 1.50, 'Soda': 1.00, 'Hotdog': 1.25, 'Nachos': 0.75}

结果：'Nachos'

关键术语

字典 / 关联数组 / 哈希 / 映射 - 一种抽象数据类型，可以以 (键，值) 对的形式保存数据。

冻结集 - Python 中的本机数据类型，它具有集合的特性（包括类方法），但像元组一样是不可变的。

哈希冲突 - 当使用相同的索引键生成两个条目时发生。当对大型可能的键集的随机子集进行哈希运算时，这种情况发生的可能性很高。

哈希表 - 一种存储键值对的数据结构类型。键被发送到哈希函数，该函数对其执行算术运算。结果（通常称为 哈希值 或 哈希）是哈希表中键值对的索引。

键 - 数据库表中的一个字段或字段组合，用于根据某些要求检索和排序表中的行。定义键是为了加快对数据的访问速度，并且在许多情况下是为了在不同的表之间创建链接。

负载因子 - 哈希表的一个关键统计量，它指的是访问哈希表的快慢。较高的负载因子表明表可能会变慢或根本无法工作。

合并算法 - 一系列算法，它们将多个排序列表作为输入，并生成单个列表作为输出，该列表包含输入列表的所有元素，并按排序顺序排列。这些算法用作各种排序算法中的子例程，最著名的是合并排序。

多重映射 - 映射或关联数组抽象数据类型的一种泛化，其中可以将多个值与给定键关联并为其返回。

多重集 - 一种与集合类似的关联容器类型，区别在于多个元素可以具有相同的值。

序列化 - 生成原始对象的文本或二进制表示，可以将其直接写入文件，并提供了一种使用关联数组的永久形式的解决方案。

集合 - 一种无序的可变数据类型，其中每个值必须是唯一的。