java - 在添加之前检查 LinkedHashSet.contains(...) 是否值得？

Question

我正在使用 LinkedHashSet 来实现按条目排序的集合。如果添加了重复的元素，它应该放在最后，并且应该删除集合中已经存在的条目。

我在争论是否值得在调用 set.remove(entry) 之前检查 set.contains(entry)？本质上每次检查 contains() 是否比每次盲目调用 remove() 提供任何时间/空间优势？

Set<Integer> set = new LinkedHashSet<>();
// The below
set.remove(entry);
set.add(entry);
// Versus the below
if (set.contains(entry)) {
set.remove(entry);
}
set.add(entry);

Answer 1

我建议不要同时调用 contains 和 remove。两个调用都必须搜索链以找到元素，而 contains 执行此操作的速度并不比 remove 快。因此，您每次通话所需的时间可能会增加一倍。

您可以浏览 contains 的代码和 remove自己。

你会发现两者最终都可能在某个点迭代哈希链(HashMap 的 removeNode 中的 remove 和 HashMap 的 getNode 中的 contains)，如果您的设备负载很重，这可能会影响性能。

如果你的集合没有承受重负载，那么它仍然可能不值得，但并不重要，因为在稀疏哈希链集合中，预期的查找/删除是 O(1)(即会无论您有 5 个元素还是 5000 个元素，速度都一样快。