java - 在 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);

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);
}

还有 addAll来自 AbstractCollection :

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;
}