在插入集合之前是否应该检查重复项

Question

我正在学习使用套装。我的问题是：集合不包含重复项。当我们尝试插入重复项时，它不会抛出任何错误并自动删除重复项。在插入集合之前检查每个值是否存在是一种好习惯吗？还是可以执行类似以下代码的操作？我认为 Java 会在内部使用 .contains(value) 进行检查。你怎么看？

考虑到集合中有 n 个元素，两种情况下的 Big O 复杂度是多少？

import java.util.HashSet;
import java.util.Set;

public class DuplicateTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
         Set<Integer> mySet = new HashSet<Integer>();

         mySet.add(10);
         mySet.add(20);
         mySet.add(30);
         mySet.add(40);
         mySet.add(50);
         mySet.add(50);
         mySet.add(50);
         mySet.add(50);
         mySet.add(50);
         mySet.add(50);

         System.out.println("Contents of the Hash Set :"+mySet);
    }

}

Answer 1

不查也行。这是相对于列表集的主要优势，因为它们会自动过滤掉重复项。

HashSet 具有常数时间性能(http://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html)

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets

Answer 2

根据 docs:

public boolean add(E e)

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.

所以 add() 方法已经 returns 你是真还是假。所以你不需要做额外的检查。

Answer 3

比较the API documentation of Set.add(E)

add 方法检查元素是否已经在 Set 中。如果该元素已经存在，则不添加新元素，并且 Set 保持不变。在大多数情况下，您不需要检查任何内容。

该方法的复杂性取决于您使用的 Set 的具体实现。

Answer 4

添加函数 return 是一个布尔值，您可以检查它以确定该项目是否已经在集合中。这当然是基于您的需要，并不是最佳做法。很高兴知道它不会删除已经存在的项目，因此如果您根据数据库中的代理键定义等于，则不能依赖它用新信息更新现有值。这与地图的工作方式相反，因为地图会 return 任何现有值并将其替换为新值。

Answer 5

以下是您问题的答案：

When we try to insert duplicates, it does not throw any error and automatically removes duplicates.

您的理解不正确。如果集合中已经存在，则调用 Set.add() 不会添加新项目；此声明适用于 Set 的所有实现，包括 HashSet 和 TreeSet.

Is it a good practice to check each value before inserting into set whether it exists or not? or is it okay to do something like the below code? I think java would be internally doing the check using .contains(value) . What do you think?

因为你一开始的理解是错误的，那么你不需要在插入集合之前检查每个值是否已经存在。是的，在内部，它正在做类似 contains().

的事情

What would be the Big Oh complexity in both the cases considering there are "n" elements going into the set?

对于HashSet，每个add()的时间复杂度是O(1)。对于 TreeSet() - 你没有使用 - 每个 add().

的时间复杂度是 O(lg N)

在插入集合之前是否应该检查重复项

Should you check for a duplicate before inserting into a set

java

performance

big-o

set