Python 的集合和字典是强大而灵活的数据结构，可提供存储和检索数据的有效方法。其效率的核心在于哈希表的实施，这确保了快速的访问时间。

集合和词典基础知识

在 Python 中，集合和字典是提供高效数据存储和检索的基本数据结构。集合和字典都利用哈希表的强大功能来实现各种操作的快速平均情况时间复杂性。了解这些结构对于有效的 Python 编程至关重要。

集

集合是唯一元素的无序集合，这意味着集合中没有两个元素是相同的。当需要执行涉及多个元素的操作而不必担心重复项时，集特别有用。它们提供高效的成员身份测试，允许快速检查集合中是否存在元素。

集合也适用于各种数学运算。例如，可以使用 sets 来执行并集、交集、差集和对称差集运算，这些运算在许多算法和应用程序中都很常见。

# Example of creating and using a set
my_set = {1, 2, 3, 4, 5}
print(3 in my_set)  # Output: True

# Mathematical operations with sets
set_a = {1, 2, 3}
set_b = {3, 4, 5}

# Union: Elements in either set_a or set_b
print(set_a | set_b)  # Output: {1, 2, 3, 4, 5}

# Intersection: Elements in both set_a and set_b
print(set_a & set_b)  # Output: {3}

# Difference: Elements in set_a but not in set_b
print(set_a - set_b)  # Output: {1, 2}

# Symmetric difference: Elements in either set_a or set_b but not both
print(set_a ^ set_b)  # Output: {1, 2, 4, 5}

集是可变的，这意味着您可以在创建集后添加或删除元素。但是，元素本身必须是不可变的（例如，数字、字符串或 Tuples）。

# Adding and removing elements in a set
my_set.add(6)
print(my_set)  # Output: {1, 2, 3, 4, 5, 6}

my_set.remove(3)
print(my_set)  # Output: {1, 2, 4, 5, 6}

字典

字典是键值对的无序集合。与仅存储唯一元素的 sets 不同，字典存储每个键都是唯一的并映射到特定值的对。此结构允许基于键进行高效的数据检索。

字典用途广泛，可用于存储各种数据类型。它们通常用于计算发生次数、对数据进行分组和实施查找表等任务。

# Example of creating and using a dictionary
my_dict = {'apple': 1, 'banana': 2, 'cherry': 3}
print(my_dict['banana'])  # Output: 2

# Adding and modifying key-value pairs
my_dict['date'] = 4
my_dict['banana'] = 5
print(my_dict)  # Output: {'apple': 1, 'banana': 5, 'cherry': 3, 'date': 4}

# Removing key-value pairs
del my_dict['apple']
print(my_dict)  # Output: {'banana': 5, 'cherry': 3, 'date': 4}

字典中的键必须是不可变类型，例如数字、字符串或元组。另一方面，值可以是任何数据类型，包括列表或其他字典。

字典提供了访问所有键、值或键值对的方法：

# Accessing keys, values, and items in a dictionary
print(my_dict.keys())   # Output: dict_keys(['banana', 'cherry', 'date'])
print(my_dict.values()) # Output: dict_values([5, 3, 4])
print(my_dict.items())  # Output: dict_items([('banana', 5), ('cherry', 3), ('date', 4)])

词典的主要优势之一是它们的速度。字典操作（如插入、删除和查找）的平均时间复杂度通常为 O（1），这使得它们对于大型数据集非常有效。

集合和字典都建立在哈希表之上，哈希表是一种提供这种高效性能的数据结构。了解哈希表的工作原理以及 Python 如何处理冲突和调整大小，对于掌握这些数据结构非常重要。

哈希表

哈希表是 Python 中 sets 和 dictionaries 背后的核心数据结构。它们使这些集合能够有效地执行插入、删除和查找等操作。了解哈希表是掌握集合和字典在后台如何工作的关键。

什么是哈希表？

哈希表（也称为哈希映射）是一种数据结构，它使用哈希函数将索引计算到存储桶或槽数组中。哈希函数接受一个输入（或“key”）并返回一个整数，称为哈希值。此哈希值确定相应值应在哈希表中存储的索引。

# Example of hash function
print(hash('apple'))  # Output: -8388877758555033324

哈希表允许基本操作的平均大小写 O（1）时间复杂度，这使得它们非常高效。这种效率是通过使用良好的哈希函数将元素均匀地分布在表中来实现的。

哈希表的工作原理

当将元素添加到集合中或将键值对添加到字典中时，Python 会计算键的哈希值。然后，此哈希值用于确定哈希表中将存储元素的索引。

例如，考虑将值为 1 的键 'apple' 添加到字典中。Python 计算 'apple' 的哈希值，并使用此值在哈希表中查找适当的索引。

# Adding an element to a dictionary
my_dict = {}
my_dict['apple'] = 1  # Hash maps 'apple' to an index in the hash table
print(my_dict)  # Output: {'apple': 1}

存储桶和索引

哈希表由一组存储桶组成。每个 bucket 可以包含多个元素，但理想情况下，每个 key 都映射到一个唯一的 bucket。当不同的键产生相同的哈希值时，会发生哈希冲突，Python 必须处理此冲突才能正确存储所有元素。

Python 的哈希函数

Python 的内置 hash（）函数旨在生成广泛的哈希值分布，从而降低冲突的可能性。该函数确保具有不同值的对象具有不同的哈希值，而相同的值始终导致相同的哈希值。

# Demonstrating Python's hash function
print(hash('banana'))  # Output: 7689599545323731411
print(hash('taco'))    # Output: 1026735073076657625
print(hash('banana'))  # Output: 7689599545323731411 Same as the first time as it does not change

负载系数和大小调整

哈希表的效率取决于其负载因子，即条目数除以存储桶数。高负载系数意味着更多的碰撞和性能更慢。为了保持性能，Python 会在负载因子超过特定阈值时动态调整哈希表的大小。

在调整大小期间，将创建一个新的更大的哈希表，并且所有现有键都将重新哈希并插入到新表中。此过程可确保哈希表即使在元素数量增加时也能保持高效。

# Example of resizing
my_dict = {i: i for i in range(1000)}  # Initial dictionary
# Python automatically resizes the dictionary as needed

哈希表的优点

哈希表的主要优点是它们的速度。由于哈希表使用存储桶数组和哈希函数来索引元素，因此插入、删除和查找等操作平均可以在恒定时间内执行。

另一个优点是哈希表可以处理多种数据类型。在 Python 中，可以使用数字、字符串、元组和其他不可变类型作为字典中的键或集合中的元素。这种灵活性使哈希表成为许多编程任务的多功能且强大的工具。

碰撞解决

当多个键产生相同的哈希值时，会发生哈希冲突，从而导致哈希表中的索引相同。有效解决这些冲突对于维护 set 和 dictionaries 的性能至关重要。Python 使用多种技术的组合来处理冲突，确保数据结构保持快速可靠。

开放寻址

开放寻址是一种冲突解决技术，其中所有元素都直接存储在哈希表中。发生冲突时，算法会探测表以查找下一个可用槽。有几种探测策略，包括线性探测、二次探测和双重哈希。

线性探测

在线性探测中，当发生冲突时，算法会检查表中的下一个槽（即索引索引 + 1 处的槽）。如果该槽也被占用，它将检查下一个槽，依此类推，直到找到空槽。

Python 的字典使用线性探测的变体。发生冲突时，算法会查找线性序列中的下一个可用槽。

# Assuming 'a' and 'b' have the same hash
my_dict = {}
my_dict['a'] = 1  # Hash maps 'a' to slot 0
my_dict['b'] = 2  # Collision, next slot (linear probing)
print(my_dict)  # Output: {'a': 1, 'b': 2}

二次探测

二次探测通过增加间隔检查槽来解决冲突。它不是检查下一个插槽，而是以 12、22、32 等的间隔检查插槽。此方法减少了集群，但实施起来可能更复杂。

双重哈希

双重哈希使用第二个哈希函数来确定探测的步长。发生冲突时，算法使用第二个哈希函数计算新索引并移动到该槽。此方法可以进一步减少聚类并提高性能。

链接

链接是另一种冲突解决技术，其中哈希表中的每个存储桶都指向映射到同一存储桶的条目的链接列表。当发生冲突时，新条目将添加到该索引处的链接列表中。此方法允许多个元素共存于同一个存储桶中，而无需探测。

尽管 Python 的集合和字典不使用链接，但它是其他哈希表实现中的常用方法。链接的优点是避免了开放寻址方法中出现的主要集群问题。

碰撞解决示例

考虑一个例子来说明 Python 如何处理开放寻址的冲突：

class SimpleHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        while self.table[index] is not None:
            index = (index + 1) % self.size  # Linear probing
        self.table[index] = (key, value)

    def get(self, key):
        index = self.hash_function(key)
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
        return None

# Creating a simple hash table
hash_table = SimpleHashTable(10)
hash_table.insert('a', 1)
hash_table.insert('b', 2)
print(hash_table.get('a'))  # Output: 1
print(hash_table.get('b'))  # Output: 2

在此示例中，SimpleHashTable 类使用线性探测来解决冲突。insert 方法为每个键找到合适的插槽，如果发生冲突，它会探测下一个插槽，直到找到空插槽。

性能特点

Python 中 sets 和 dictionaries 的性能是它们被广泛使用的主要原因。通过利用哈希表，这些数据结构提供了高效的存储和检索功能。在这里，我们将介绍 set 和 dictions 的性能特征，重点介绍平均情况和最坏情况，以及用于保持性能的策略。

平均性能

在平均情况下，集合和字典为插入、删除和查找等操作提供恒定的时间复杂度 O（1）。这种效率是通过使用哈希表来实现的，哈希表使用哈希函数在可用插槽之间均匀分布元素。

查找

在集合和字典中查找的平均大小写性能为 O（1）。当在字典中查找键或检查集合中的成员身份时，Python 会计算键的哈希值，并使用它直接索引到哈希表中。

my_dict = {'apple': 1, 'banana': 2, 'cherry': 3}
print(my_dict['banana'])  # Output: 2

插入和删除

插入和删除操作的平均时间复杂度也为 O（1）。在字典中插入新的键值对或将元素添加到集合中时，Python 会计算哈希值并将元素放入相应的存储桶中。删除遵循类似的过程，通过元素的哈希值查找元素并将其删除。

my_dict = {'apple': 1, 'banana': 2, 'cherry': 3}
my_dict['date'] = 4  # Insertion
del my_dict['banana']  # Deletion
print(my_dict)  # Output: {'apple': 1, 'cherry': 3, 'date': 4}

最坏情况下的性能

虽然 sets 和 dictionaries 的平均情况性能非常好，但最坏情况的性能可能会降级为 O（n）。当发生许多冲突时，会出现这种情况，导致所有元素都存储在同一个存储桶中。但是，如果拥有良好的哈希函数和有效的冲突解决策略，这种情况很少见。

影响最坏情况性能的因素

哈希函数差：设计不佳的哈希函数可能会导致过多的冲突，其中许多键映射到相同的哈希值。这会导致链接方法中的探针序列更长或链表更大。
高负载系数：负载因子是哈希表中元素数与桶数的比率。高负载系数会增加发生碰撞的可能性，并可能降低性能。

Python 通过动态调整大小和使用设计良好的哈希函数来缓解这些问题。

动态调整大小

为了保持高效的性能，当负载因子超过特定阈值时，Python 会动态调整哈希表的大小。此过程包括创建一个新的、更大的哈希表，并重新哈希所有现有键以更均匀地分配它们。

调整大小过程

创建新的哈希表：将创建一个具有更多存储桶的新哈希表。
重新哈希现有 Key：旧哈希表中的所有键都会重新哈希并插入到新表中。此步骤可确保元素在新存储桶中均匀分布。

# Example of resizing
my_dict = {i: i for i in range(1000)}  # Initial dictionary
# Python automatically resizes the dictionary as needed

动态调整大小通过降低冲突的可能性并确保哈希表保持有效利用，帮助保持 O（1）的平均大小写性能。

性能注意事项

使用集和字典时，必须考虑它们的性能特征，以便在应用程序中实现最佳结果。

选择正确的数据结构：使用集进行成员资格测试和涉及唯一元素的数学运算。使用字典存储键值对和实现查找表。
监控负载系数：请注意负载因子，尤其是在具有大型数据集的应用程序中。Python 会自动处理大小调整，但了解此机制可以帮助您预测性能影响。
选择好键：使用不可变类型（例如数字、字符串、元组）作为字典中的键，以确保一致和高效的哈希。

。

流照教程网

Python 的集合和字典实现的机制（python字典与集合答案）