Big-O - 为了将元素添加到HashSet中，复杂度为O(1)，那么HashSet如何确定要添加的元素是否唯一？
这取决于哈希表的选择，但在哈希表的大多数传统实现(线性探测、链式哈希、二次探测等)中，执行插入的成本取决于期望O(1)，而不是最坏情况O(1)。这里的 O(1) 项来自这样一个事实，即在插入新值的过程中，平均只需要查看哈希表中恒定数量的元素。在线性探测中，发生这种情况是因为要检查的元素运行的预期长度为 O(1)，而在链式散列中，这是因为相关存储桶中只有预期 O(1) 元素。然后，哈希表可以在执行插入时检查新插入的元素是否等于这些值中的任何一个。如果是这样，我们知道它是重复的。如果不是，那么我们知道新元素不能是重复的;我们已经检查了可能等于它的每一个元素。这意味着平均插入的成本为 O(1)，我们可以在插入时检查唯一性。