How are sets and frozenset implemented in Python?

Sets and immutable sets (frozenset) in Python are two data structures used to store unique elements. They are mutable and immutable objects respectively, so they have different properties and usage. This article will introduce in detail how collections and frozenset are implemented in Python, and provide specific code examples.

1. How to implement a set:
In Python, a set is implemented using a hash table. A hash table is an efficient data structure that takes advantage of the fast lookup capabilities of hash functions. The elements in the collection are in no particular order and cannot be repeated.

The implementation of collections is based on the principle of hash tables, by storing the hash value of each element in the hash table as an index. When we add an element to the collection, Python calculates the hash value of the element and uses that value as an index to store the element at the corresponding location. When we need to determine whether an element exists in the set, Python will calculate the hash value of the element again and find the corresponding position in the hash table. If an element exists at that position, it means that the element exists in the set; otherwise, the element does not exists in the collection.

The following is a simple sample code that demonstrates the basic usage of collections:

# 创建集合
s = set()
print(s)  # 输出: set()

# 添加元素
s.add(1)
s.add(2)
s.add(3)
print(s)  # 输出: {1, 2, 3}

# 判断元素是否存在
print(1 in s)  # 输出: True
print(4 in s)  # 输出: False

# 删除元素
s.remove(2)
print(s)  # 输出: {1, 3}

2. The implementation of immutable collections (frozenset):
Different from collections, immutable collections The elements in are immutable, that is, the elements cannot be modified. Therefore, immutable collections are implemented differently than collections.

The implementation of immutable collections is also based on hash tables, but the hash tables are frozen when they are created, making them immutable objects. In this way, we cannot add, delete, or modify elements to the immutable collection.

The following is a simple sample code that demonstrates the basic usage of immutable collections:

# 创建不可变集合
fs = frozenset([1, 2, 3])
print(fs)  # 输出: frozenset({1, 2, 3})

# 尝试添加元素（报错）
fs.add(4)  # 报错: AttributeError: 'frozenset' object has no attribute 'add'

# 尝试删除元素（报错）
fs.remove(2)  # 报错: AttributeError: 'frozenset' object has no attribute 'remove'

# 判断元素是否存在
print(1 in fs)  # 输出: True
print(4 in fs)  # 输出: False

Summary:
Sets (set) and immutable collections (frozenset) are used in Python A data structure used to store unique elements. The implementation of collections is based on hash tables, while immutable collections are frozen into immutable objects after the hash table is created. Through the above code examples, we can better understand the usage and implementation of collections and immutable collections.

The above is the detailed content of How are sets and frozenset implemented in Python?. For more information, please follow other related articles on the PHP Chinese website!