所以最初,我有这个代码:
import java.util.*;
public class sandbox {
public static void main(String[] args) {
HashSet<Integer> hashSet = new HashSet<>();
for (int i = 0; i < 100_000; i++) {
hashSet.add(i);
}
long start = System.currentTimeMillis();
for (int i = 0; i < 100_000; i++) {
for (Integer val : hashSet) {
if (val != -1) break;
}
hashSet.remove(i);
}
System.out.println("time: " + (System.currentTimeMillis() - start));
}
}
在我的计算机上运行嵌套的 for 循环大约需要 4 秒,我不明白为什么要花这么长时间。外循环运行 100,000 次,内循环应该运行 1 次(因为 hashSet 的任何值永远不会是 -1)并且从 HashSet 中删除一个项目是 O(1),所以应该有大约 200,000 次操作。如果一秒钟内通常有 100,000,000 次操作,为什么我的代码需要 4 秒才能运行?
此外,如果行
hashSet.remove(i);
注释掉,代码只需要16ms。如果内部 for 循环被注释掉(但不是
hashSet.remove(i);
),代码只需要 8ms。
最佳答案
您已经创建了一个边缘用例 HashSet
,其中算法降级为二次复杂度。
这是需要很长时间的简化循环:
for (int i = 0; i < 100_000; i++) {
hashSet.iterator().next();
hashSet.remove(i);
}
async-profiler显示几乎所有的时间都花在了
java.util.HashMap$HashIterator()
里面构造函数: HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
---> do {} while (index < t.length && (next = t[index++]) == null);
}
}
突出显示的行是一个线性循环,用于搜索哈希表中的第一个非空桶。
自
Integer
有琐碎的hashCode
(即 hashCode 等于数字本身),结果是连续整数大部分占据哈希表中的连续桶:数字 0 进入第一个桶,数字 1 进入第二个桶,以此类推。现在删除从 0 到 99999 的连续数字。在最简单的情况下(当存储桶包含单个键时),删除键的实现是将存储桶数组中的相应元素清空。请注意,表在删除后不会被压缩或重新散列。
因此,从存储桶数组的开头删除的键越多,
HashIterator
的时间就越长。需要找到第一个非空桶。尝试从另一端移除 key :
hashSet.remove(100_000 - i);
算法将变得更快!
关于java - HashSet 代码的意外运行时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59522136/