Python中set集合去重的底层实现原理是什么？

你猜的没错，Python的set根本不是靠循环遍历找重复项来实现去重的，它用的是效率高得多的**哈希表（Hash Table）**结构——说白了set就是只存key、不存value的字典，和dict是同源实现。

具体的去重过程可以拆解成这几步：

• 往set里添加元素时，先调用元素的__hash__()方法算出它的哈希值，这个值是元素唯一标识的简化版。
• 用哈希值定位到哈希表中的对应存储位置。
• 如果这个位置是空的，直接把元素存进去就行；如果位置已经有元素了，就调用元素的__eq__()方法对比两个元素是否完全相等：
  • 要是相等，就判定是重复元素，直接跳过不添加；
  • 要是不相等，就通过开放寻址法（Python哈希表的处理方式）找下一个空位置存进去。

这种哈希方式的平均时间复杂度是O(1)，不管集合里有多少元素，添加和判断重复的操作都快得很，完全不是循环遍历那种O(n)的效率能比的。

另外要提一句：不是所有对象都能放进set里，必须是**可哈希（hashable）**的对象——也就是得实现__hash__()和__eq__()方法，而且对象的哈希值在它生命周期里不能变。比如列表（list）就不可哈希，没法直接放进set；但字符串、整数、元素都可哈希的元组这些都没问题。

内容的提问来源于stack exchange，提问作者eunsnag