哪个更快？检查一个元素是否已经在一个集合中，如果不添加它或者只是添加它？

Question

将元素添加到集合中哪种方式最快？

在我看来，您可以通过两种不同的方式做到这一点：

检查你要添加的元素是否已经在集合中，如果不在集合中，添加它。
就加吧，因为一个集合的元素是唯一的。我不确定这种方式不会抛出错误。

Answer 1

直接添加即可。它有检查机制。

来自 add 方法的文档。

Adds the specified element to this set if it is not already present. More formally, adds the specified element e to this set if this set contains no element e2 such that (e==null ? e2==null : e.equals(e2)). If this set already contains the element, the call leaves the set unchanged and returns false.

Answer 2

我做了一些工作来为您检查一下

Random rng = new Random();
ArrayList<Integer> numbers = new ArrayList<>();
for (int i = 0; i < 100000; ++i)
    numbers.add(rng.nextInt());
    
HashSet<Integer> set = new HashSet<>();
long beginNoCheck = System.nanoTime();
for (int i : numbers)
{
    set.add(i);
}
long endNoCheck = System.nanoTime();
   
set = new HashSet<>();
long beginCheck = System.nanoTime();
for (int i : numbers)
{
    if (!set.contains(i))
        set.add(i);
}
long endCheck = System.nanoTime();
    
System.out.println("Without check: " + (endNoCheck - beginNoCheck));
System.out.println("With check: " + (endCheck - beginCheck));

而且，在添加元素之前检查 HashSet 是否包含元素似乎要快一些。我得到的结果类似于

Without check: 66060748
With check: 46209808

Without check: 38249163
With check: 32058546

Without check: 58362677
With check: 34429848

Without check: 52095512
With check: 39612073

Without check: 34892990
With check: 28945278

Without check: 42090287
With check: 38426209

Answer 3

您也可以随时检查实现以了解幕后发生的事情：

HashSet 只是一个 HashMap

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.getEntry%28java.lang.Object%29

类似下面发布的测试在不同的机器上甚至在不同的情况下可能会有不同的结果。如果运行时之间没有真正巨大的差异，可读性通常比几毫秒要好得多。通常一个简单的正确概念和整个软件的设计远远胜过复杂的技巧。

哪个更快？检查一个元素是否已经在一个集合中，如果不添加它或者只是添加它？

Which is faster? Checking if an element is already in a set, if not add it or just adding it anyway?

java

add

set