时间戳

首页 > 解决方案 > 在 Java 中将字符串集合复制到另一个字符串的时间复杂度

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

问题描述

我有几个关于 Java 的 add 函数如何Collection处理字符串的问题。例如，在下面的代码片段中，我将一个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);

标签： javastringcollectionstime-complexity

解决方案

字符串的长度与在集合之间复制元素无关。实际上，您不会复制字符串本身，而是复制对它们的引用。所以复杂度将是 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;
}

推荐阅读