CodeForces问题中的歧义-- HashSet Vs LinkedHashSet的用法

Question

昨天我在解决一个Codeforce问题。问题的网址是这

我只会在以下简单地解释这个问题。

给定一个二进制字符串，将其划分为最小数目的子序列，使字符串中的每个字符恰好属于一个子序列，并且每个子序列看起来像"010101 .“或者"101010 .“(即子序列不应包含两个相邻的零或1)。

现在，对于这个问题，我昨天在比赛中提交了一个解决方案。这是解决方案。它被暂时接受，在最后的测试用例中，时间限制超过了状态。

所以今天，我再次提交了另一个解决方案，这通过了所有的案例。

在第一个解决方案中，我使用了HashSet，在第二个解决方案中，我使用了LinkedHashSet。我想知道，为什么HashSet不把所有的案子都办好？这是否意味着每当我需要LinkedHashSet实现时都应该使用Set？我看了这的文章，发现HashSet比LinkedHashSet表现得更好。但为什么我的代码在这里不起作用？

Answer 1

这个问题可能会在Codeforces上得到更多的答复，但无论如何我还是会在这里回答的。

竞赛结束后，Codeforce允许其他用户通过编写自定义输入在其他用户的程序上运行来“黑”解决方案。如果维护用户的程序在自定义输入上运行缓慢，则他们提交代码的状态将从“接受”更改为“超出时间限制”。

您的代码之所以从“接受”更改为“超过时间限制”，是因为有人创建了一个“反哈希测试”(您的哈希函数在该测试上导致了许多冲突)，您的程序运行速度比平时慢。如果您对如何生成这样的测试感兴趣，您可以在Codeforces上找到几个帖子，比如：https://codeforces.com/blog/entry/60442。

正如@Photon所链接的，Codeforces上有一篇文章解释了为什么您应该避免使用Java.HashSet和Java.HashMap：https://codeforces.com/blog/entry/4876，这主要是由于反哈希测试。在某些情况下，从平衡的BST中添加额外的log(n)因子可能不是那么糟糕(通过使用TreeSet或TreeMap)。在许多情况下，额外的log(n)因素不会使您的代码超时，并且它为您提供了免受反哈希测试的保护。

如何确定算法是否足够快以添加log(n)因子？我想这是伴随着一些经验，但大多数人建议进行某种计算。大多数在线评判(包括Codeforces)显示了允许程序在特定问题上运行的时间(通常在1到4秒之间)，并且在执行计算时可以使用每秒10^9固定时间操作作为经验法则。