Java Set.contains(o) 与 List.get(index) 时间复杂度

Question

我正在创建一个股票应用程序，当购买某只股票时，我会在其中保存指数的历史记录。目前我正在使用 HashSet<Integer>保存这些值(范围 0-270)。

在程序中，有很多使用 Set.contains(o) 的历史查询。 ，即 O(1) .

我正在考虑将此历史记录更改为 ArrayList<Boolean> ，其中一个 true在指数 0 意味着在指数 0 有买入，false在指数 1 意味着在指数 1 没有买入，等等......

这样，我可以做 List.get(index) , 这也是 O(1) , 但我猜会稍微快一些，因为 HashSet 的基本性质查找。

但由于指数范围较小，我不确定我的假设是否成立。

那么如果我不关心空间复杂度，哪种方法会更快？

Answer 1

由于你的范围很小，最快是直接使用数组:

boolean[] values = new boolean[271];

// get the value (equivalent to your hashset.contains(index)):
boolean contained = values[index];

不涉及任何hashCode/equals HashSet 的操作需要。这大致相当于使用 ArrayList<Boolean> ，减去(非常小的)调用堆栈。

数组查找肯定是O(1)以及非常快的操作。

您也可以考虑使用 BitSet 正如 yshavit 所建议的那样。