在Java中将一个字符串集合复制到另一个集合的时间复杂度

Question

我有几个问题关于Java Collection的add函数如何处理字符串。例如，在下面的代码片段中，我正在将一个字符串List复制到HashSet中。在这种情况下，最坏情况下的总时间复杂度是多少？是O(M x N)还是O(N)，其中M是列表中任何字符串的最大长度，N是列表中字符串的总数。

public HashSet<String> createDict(List<String> wordList) {
   HashSet<String> wordDict = new HashSet<>();
   for(String word : wordList) {
       wordDict.add(word);
   }
   return wordDict;
}

如果我使用以下代码而不是循环，时间复杂度会完全相同吗？

HashSet<String> wordDict = new HashSet<>(wordList);

- Kaustav

---

“是O（M x N）还是O（N），其中M是列表中任何字符串的最大长度[...]”，你能解释一下吗？为什么长度会影响复制过程？为什么要乘以N？ - akuzminykh

列表的长度(N)会影响复制过程，因为我正在运行一个循环来遍历列表中的所有字符串。但我的问题是，特定字符串的最大长度(M)是否也会影响复制的时间复杂度？如果是，为什么？ - Kaustav

它没有，这与HashSet添加元素和工作方式有关。请参见下面提供有关此信息的答案。但这是现实的答案。您可以认为必须至少读取长度M一次。逐个字符进行读取，如果对于每个n都这样做，则复杂度确实为O（M x N）。但这是“我非常严肃地采用O符号表示法”的答案。 - akuzminykh

没有通过值复制任何字符串，只是通过引用复制，所以它们的长度是不相关的。 - user207421

Answer 1

字符串长度与在集合之间复制元素没有关系。事实上，你不是复制字符串本身，而是复制对它们的引用。因此，复杂度将为O(N)。

当谈到第二个问题new HashSet<>(wordList)时，这个调用会比循环快。原因是在HashSet(Collection)构造函数中，它首先检查该集合的大小，并根据其开始使用initialCapacity。这样就不必经常调整底层HashMap的大小。

对于那些好奇但太懒得搜索的人来说，这是有关HashSet的构造函数：

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

还有来自AbstractCollection的addAll方法：

public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}

如果您在示例代码中设置了initialCapacity，则将获得相同的性能，如下所示：

public HashSet<String> createDict(List<String> wordList) {
   int initialCapacity = Math.max((int) (wordList.size()/.75f) + 1, 16);
   HashSet<String> wordDict = new HashSet<>(initialCapacity );
   for(String word : wordList) {
       wordDict.add(word);
   }
   return wordDict;
}

- Amongalen

---

谢谢你的回答。如果我将一个列表中的字符串复制到另一个列表中会发生什么？这也是O(N)吗？ - Kaustav

它将完全相同。 - Amongalen

初始容量是否有影响取决于原始列表中有多少个重复项。 - Holger

Answer 2

复杂度将为 O(N)。

向 HashSet 添加一个元素的复杂度为O(1)，它不会逐个字符比较字符串，这也是获取 O(MxN) 的可能方式。

是的，通过在构造函数中传递列表来创建 HashSet 将具有相同的复杂度。实际上，您可以检查 HashSet 实现代码，它做的事情与您所做的完全相同，除了基于列表大小更优化的对象创建。

- matteobarbieri

Answer 3

HashSet是使用HashTable实现的。这意味着它具有O(1)的插入时间，并使用哈希函数来插入元素。在这种情况下，插入元素的大小并不真正重要，它们都被认为是O(1)。因此，您的整个代码复杂度为O(N)，其中N是您列表的大小。

- Vorashil Farzaliyev