前言
1. List（列表）
- 原理
- 列表是一种有序的可变容器，可以存储任意类型的对象。它的主要操作包括索引、切片、添加、删除、修改元素等。
- 列表中的元素在内存中是连续存储的（对于简单的对象，如整数、字符串等是这样，对于复杂对象可能涉及到引用的存储），这使得通过索引访问元素的速度非常快，时间复杂度为O(1)。但是，在列表中间插入或删除元素可能需要移动后面的元素，时间复杂度为O(n)，其中n是列表的长度。
- 底层结构
- 在CPython（Python的官方实现）中，列表是由一个动态数组实现的。当列表需要扩展时（例如添加元素超过了当前数组的容量），会分配一个更大的数组，并将原来的元素复制到新数组中。这个过程可能会涉及到内存的重新分配和数据的移动，但是Python会尽量优化这个过程以减少性能开销。
2. Tuple（元组）
- 原理
- 元组是一种有序的不可变容器，与列表类似，但是元组一旦创建，其元素就不能被修改。元组常用于存储多个相关的值，并且作为不可变对象，它可以作为字典的键（而列表不能）。
- 由于元组是不可变的，所以它在一些操作上比列表更高效。例如，元组可以作为字典的键，因为字典要求键是不可变的。
- 底层结构
- 元组的底层实现与列表有相似之处，但由于它是不可变的，在内存中它的结构相对简单和固定。它可能也是以一种紧凑的方式存储元素，并且不会像列表那样需要动态扩展或收缩的机制。
3. Set（集合）
- 原理
- 集合是一种无序的、不包含重复元素的数据结构。它主要用于去重和集合运算（如交集、并集、差集等）。
- 集合中的元素必须是可哈希的，这是为了保证元素的唯一性和快速查找。当向集合中添加一个元素时，会通过哈希函数计算该元素的哈希值，然后根据哈希值确定元素在集合中的存储位置。如果该位置已经有元素且两个元素相等（通过
__eq__方法判断），则不会添加新元素。
- 底层结构
- 在CPython中，集合是通过哈希表实现的。哈希表是一种数据结构，它通过哈希函数将元素映射到一个特定的位置（桶）。当多个元素的哈希值映射到同一个桶时，会通过一种称为“链地址法”或其他冲突解决方法来处理。这种结构使得集合在查找、添加和删除元素时具有较高的效率，平均时间复杂度为O(1)，尽管在最坏情况下（哈希冲突严重时）可能会退化为O(n)。
4. Dict（字典）
- 原理
- 字典是一种无序的键值对集合，用于存储和查找数据。通过键来访问值，键必须是不可变的（如字符串、元组等），值可以是任意类型。
- 字典提供了快速的查找功能，通过键查找值的时间复杂度通常为O(1)。这是因为字典使用了哈希表来实现，与集合类似，它将键通过哈希函数映射到一个特定的位置，然后在该位置存储键值对。
- 底层结构
- 在CPython中，字典是由哈希表实现的。具体来说，它使用了一种称为“开放寻址法”的哈希冲突解决机制（在Python 3.6+中也有一些改进和优化）。每个桶中存储一个键值对，当发生哈希冲突时，会通过一定的规则（如线性探测、二次探测等）寻找下一个可用的桶来存储键值对。这种结构使得字典在大多数情况下能够快速地查找、添加和删除键值对。
1.set
x = set('runoob')
y = set('google')
x, y #(set(['b', 'r', 'u', 'o', 'n']), set(['e', 'o', 'g', 'l'])) # 重复的被删除
x & y # 交集，set(['o'])
x | y # 并集，set(['b', 'e', 'g', 'l', 'o', 'n', 'r', 'u'])
x - y # 差集，set(['r', 'b', 'u', 'n'])
2.list
虽说叫作list，但是python中的list并不是链表，而是长度可变的动态数组，可以理解为vector：
可以看到，list存储的是元素的引用，在分配空间快满的时候，会自动申请两倍空间，其效率比传统的链表低很多。
另外，当执行pop等删除操作之后，list会动态释放部分内存。
3.tuple
tuple和list很像，唯一的不同在于tuple是只读属性，但是要注意tuple的实现跟list几乎是一样，所以tuple中每个位置指向的是一个引用，引用不能变，但是引用所指向的数据可以变，比如：
a=(1, 2, [1, 3])
a[2][1] = 0 #a=(1,2, [1, 0])
a=a+(3,4) # a=(1,2, [1, 0], 3, 4),这里a这个对象整体变了
4.dict
dict和set一样，都是用了哈希表来构建的，利用开放寻址法来解决哈希冲突：
如图所示，在存储dict时，首先会依据dict的key进行哈希映射，使其对应到相应的表元，接着在对应的表元中开辟内存来存入数据。倘若存在两个不同的key，它们的哈希结果相同，那么就会使用散列值的另一部分来定位散列表中的另一行。
在dict中查找指定的key时，会先计算key的散列值，然后利用散列值的一部分来定位表元。如果没有找到相应的表元，这就表明dict中不存在对应的key，此时会抛出KeyError异常。若找到表元之后，会判断表元中的key是否与要查找的key相等，若相等则返回对应的值；若不相等，则使用其对应的散列值的其他部分来定位散列表中的其他行。（这是因为不同的对象其散列值有一定概率相同，这也是为什么在存放dict开辟内存时需要预留出大约1/3的空地址。这样一来，如果出现相同的哈希值，就会有空闲的地址来存放数据。并且随着数据的增加，还会继续开辟新的内存，以确保空内存始终保持在1/3左右。）
补充说明：①在Python中，set的值存储方式与dict相同。所以dict的key和set的值都必须是可哈希（不可修改）的对象。②dict的开销较大，因为要空出将近1/3的内存，不过它的查询速度很快。