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

Question

我正在创建一个股票应用程序,我可以在购买特定股票时保存指数的历史记录.目前我正在使用a HashSet<Integer>来保存这些值(范围0-270).

在程序中,有很多查找使用的历史记录Set.contains(o),即O(1).

我正在考虑将此历史更改为a ArrayList<Boolean>,其中trueat指数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)一个非常快速的操作.

您还可以考虑使用BitSetyshavit建议的a.