我有几个关于 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);
最佳答案
字符串的长度与在集合之间复制元素无关。实际上,您不会复制字符串本身,而是复制对它们的引用。所以复杂度将是 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;
}
关于java - 在 Java 中将字符串集合复制到另一个字符串的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62129780/