Java Set.contains(o) 与 List.get(index) 时间复杂度
Java Set.contains(o) vs. List.get(index) Time Complexity
我正在创建一个股票应用程序，当购买某只股票时，我会在其中保存指数的历史记录。目前我正在使用 HashSet<Integer> 来保存这些值（范围 0-270）。
在程序中，有很多使用Set.contains(o)查找此历史记录，即O(1)。
我正在考虑将此历史记录更改为 ArrayList<Boolean>，其中索引 0 处的 true 表示索引 0 处有买入，索引 1 处 false 表示有没有在指数 1 买入，等等...
这样，我可以执行 List.get(index)，这也是 O(1)，但由于 HashSet 查找的基本性质，我猜会稍微快一些。
但由于指数范围较小，我不确定我的假设是否成立。
所以如果我不关心 space 复杂性，哪种方法会更快？
由于你的范围很小，最快的就是直接用数组：
boolean[] values = new boolean[271];
// get the value (equivalent to your hashset.contains(index)):
boolean contained = values[index];
它不涉及 HashSet 需要的任何 hashCode / equals 操作。这大致相当于使用 ArrayList<Boolean>，减去（非常小的）调用堆栈。
数组查找绝对是O(1)和非常快操作。
您也可以按照 yshavit 的建议考虑使用 BitSet。
除了上面提到的boolean[]，你还可以考虑一个BitSet。它的设计几乎就是为了这些目的。
BitSet bs = new BitSet(271);
bs.set(someIndex);
boolean isSet = bs.get(anotherIndex);
这比 boolean[] 更紧凑，占用 34 个字节而不是 270 个字节（不计算 headers，两者大致相当）。它还可以更灵活地处理边界——如果您尝试在 270 以上的索引处设置一个位，它将起作用而不是抛出异常。这是好事还是坏事取决于你。
很明显 array[index] 比 [set/list].get(index) 快，否则现代 JIT 会以某种方式对其进行优化，您将无法看到差异, 除非你的应用有非常高的关键性能要求。
我正在创建一个股票应用程序，当购买某只股票时，我会在其中保存指数的历史记录。目前我正在使用 HashSet<Integer> 来保存这些值（范围 0-270）。
在程序中，有很多使用Set.contains(o)查找此历史记录，即O(1)。
我正在考虑将此历史记录更改为 ArrayList<Boolean>，其中索引 0 处的 true 表示索引 0 处有买入，索引 1 处 false 表示有没有在指数 1 买入，等等...
这样，我可以执行 List.get(index)，这也是 O(1)，但由于 HashSet 查找的基本性质，我猜会稍微快一些。
但由于指数范围较小，我不确定我的假设是否成立。
所以如果我不关心 space 复杂性，哪种方法会更快？
由于你的范围很小，最快的就是直接用数组：
boolean[] values = new boolean[271];
// get the value (equivalent to your hashset.contains(index)):
boolean contained = values[index];
它不涉及 HashSet 需要的任何 hashCode / equals 操作。这大致相当于使用 ArrayList<Boolean>，减去（非常小的）调用堆栈。
数组查找绝对是O(1)和非常快操作。
您也可以按照 yshavit 的建议考虑使用 BitSet。
除了上面提到的boolean[]，你还可以考虑一个BitSet。它的设计几乎就是为了这些目的。
BitSet bs = new BitSet(271);
bs.set(someIndex);
boolean isSet = bs.get(anotherIndex);
这比 boolean[] 更紧凑，占用 34 个字节而不是 270 个字节（不计算 headers，两者大致相当）。它还可以更灵活地处理边界——如果您尝试在 270 以上的索引处设置一个位，它将起作用而不是抛出异常。这是好事还是坏事取决于你。
很明显 array[index] 比 [set/list].get(index) 快，否则现代 JIT 会以某种方式对其进行优化，您将无法看到差异, 除非你的应用有非常高的关键性能要求。