面试题：Python集合在数据去重与高效查找中的应用

def remove_duplicates_and_check(lst):
    unique_set = set(lst)
    def check_number(num):
        return num in unique_set
    return check_number

你可以这样调用：

original_list = [1, 2, 2, 3, 4, 4, 5]
check_func = remove_duplicates_and_check(original_list)
print(check_func(3))  
print(check_func(6))

去重效率：
- 集合（set）：Python 集合内部基于哈希表实现，添加元素时，通过计算哈希值来确定元素的存储位置，平均情况下添加一个元素的时间复杂度为 (O(1))。因此，对于包含大量重复元素的列表，使用集合去重的时间复杂度为 (O(n))，其中 (n) 是列表元素的数量。
- 列表：如果使用列表去重，通常需要遍历列表，对于每个元素检查是否已存在于新列表中，时间复杂度为 (O(n^2))，因为对于每个元素都要遍历一次已处理的部分列表。
查找效率：
- 集合（set）：集合的查找操作平均时间复杂度为 (O(1))，因为通过哈希值可以快速定位元素是否存在。
- 列表：列表的查找操作需要遍历整个列表，时间复杂度为 (O(n))，随着列表元素增多，查找时间会显著增加。

问题：
- 内存消耗：集合基于哈希表实现，在处理海量数据时，哈希表本身需要占用大量内存，可能导致内存不足问题。
- 哈希冲突：虽然哈希表平均查找时间复杂度为 (O(1))，但在极端情况下，大量元素哈希值相同（哈希冲突严重）时，查找时间复杂度会退化到 (O(n))。
解决方案：
- 内存消耗：
  - 分块处理：将海量数据分成多个小块，分别进行去重和处理，最后合并结果。例如，可以按文件块读取数据，对每个文件块内的数据进行去重，然后再合并不同块的去重结果。
  - 使用外部存储：如果内存实在无法容纳全部数据，可以考虑使用数据库（如 SQLite 等轻量级数据库）来存储数据，数据库有成熟的索引机制可以实现高效查找，并且可以处理远超内存容量的数据。
- 哈希冲突：
  - 选择好的哈希函数：Python 的内置集合已经使用了相对较好的哈希函数，但在自定义数据类型时，需要确保定义合理的 __hash__ 方法，减少哈希冲突。
  - 使用更复杂的数据结构：如布隆过滤器（Bloom Filter），它可以在极低的内存消耗下，以极小的误判率快速判断一个元素是否存在。虽然存在误判，但对于某些允许一定误判的场景（如网页爬虫判断 URL 是否已访问过）非常适用。

星途面试题库