为什么 HashSet.add 的算法性能会变差？

Question

我正在使用一种算法，该算法必须读取一个包含 100 万行的文件并存储有关该文件的一些信息。我发现在 O(1) 性能中添加、删除和查找任何数据的 HashSet 结构。但是，当我使用将数据添加到 HashSet 的行执行算法时，算法执行时间变得最差 4 倍以上。当我们向其中插入太多数据时，HashSet 性能变得最差？

Answer 1

不同的 HashSet 实现可能会在性能上有所不同。首先，需要某种树或一组桶，两者都有自己的性能成本。从理论上讲，哈希数据结构很快，但实际情况可能大不相同。即使O(1)意味着执行时间与元素个数无关，但并不意味着它是免费的或快速的。