面试题：Python集合与字典在性能优化场景下的选择

集合（set）和字典（dict）的底层实现原理
- 集合（set）：
  - 在Python中，set是基于哈希表实现的。哈希表是一种以键值对形式存储数据的数据结构，在set中，只关注值（因为集合中的元素是唯一的）。哈希表通过对元素进行哈希计算，将元素分配到不同的桶（bucket）中。这样在查找元素时，平均情况下时间复杂度为$O(1)$，因为通过哈希值可以快速定位到元素所在的桶。当向set中添加元素时，首先计算元素的哈希值，然后检查该哈希值对应的桶中是否已经存在该元素，如果不存在则添加。这使得set在去重操作上非常高效。
- 字典（dict）：
  - dict同样是基于哈希表实现。与set不同的是，dict存储的是键值对。在存储和查找时，也是通过对键进行哈希计算来定位存储位置。平均情况下，查找、插入和删除操作的时间复杂度都是$O(1)$。但如果出现哈希冲突（即不同的键计算出相同的哈希值），则需要通过链表等方式来处理冲突，最坏情况下时间复杂度会退化为$O(n)$，不过这种情况在实际中较少出现。
根据需求选择集合还是字典
- 只需要去重和查找：
  - 如果场景中只需要对数据进行去重和查找操作，set是更好的选择。因为set只存储值，相比dict（需要存储键值对）占用更少的内存空间。同时，set的去重操作非常直观，直接使用add方法添加元素，set会自动保证元素的唯一性。
- 需要存储键值对并进行查找：
  - 当需要存储键值对，并且根据键来查找对应的值时，dict是必须的选择。例如，在存储用户ID和用户信息的场景中，用户ID作为键，用户信息作为值，dict可以高效地根据用户ID获取对应的用户信息。
性能差异代码示例
- 使用set进行去重和查找：

import timeit

data = [1, 2, 3, 2, 4, 3, 5, 6, 5]

def set_operations():
    s = set()
    for num in data:
        s.add(num)
    return 4 in s

print(timeit.timeit(set_operations, number = 10000))

使用dict进行类似操作（模拟去重和查找）：

import timeit

data = [1, 2, 3, 2, 4, 3, 5, 6, 5]

def dict_operations():
    d = {}
    for num in data:
        d[num] = None
    return 4 in d

print(timeit.timeit(dict_operations, number = 10000))

在上述代码中，timeit模块用于测量代码执行时间。可以看到，set操作更简洁，在只需要去重和查找的场景下，set通常会比dict稍快一些，因为dict还要处理键值对的存储，占用更多内存和处理时间。但如果实际场景需要存储键值对，那么dict是不可替代的，并且在大数据量且哈希分布良好的情况下，dict的性能也能满足需求。

星途面试题库

面试题：Python集合与字典在性能优化场景下的选择

知识考点

面试题答案