如果我经常对项目列表使用contains方法，那么在存储项目列表方面是否有比HashMap更好的DS？

Question

我有一个数字列表。在我的程序中，我会经常检查某个数字是否是我列表的一部分。如果它不在我的列表中，我会将其添加到列表中，否则我什么都不做。我发现自己使用hashmap来存储项目，而不是arraylist。

void add(Map<Integer, Integer> mp, int item){
   if(!mp.containsKey(item)){
      mp.put(item, 1);
   }
}

正如您在上面看到的，我将任何东西作为值，因为我不会使用这些值。我已经测试过这个过程比使用数组列表要快得多。（此外，hashmap的容器键（）是O（1），而数组列表的包含（）是O（n））

虽然它对我来说效果很好，但感觉很尴尬，原因很简单，它不是正确的数据结构。这是一种好的做法吗？是否有更好的DS供我使用？是否没有使用哈希存储值的列表？

Answer 1

标准库中的另一种解决方案是java。util。位集。在我看来，这只是一个选项，如果项的值不是太大，并且它们相对接近。如果您的值彼此不接近（并且不是从零开始），那么寻找提供稀疏位集或其他稀疏数据结构的第三方解决方案可能是值得的。

您可以使用位设置，例如：

BitSet bits = new BitSet();

void add(int item) {
    bits.set(item);
}

正如厄立特里亚人的评论中建议的那样，您也可以使用Set（例如HashSet）。在内部，HashSet使用HashMap，因此它的性能与您当前的解决方案相似，但它无需在您自己中放置哨兵值（您只需添加或删除项目本身）。

作为一个额外的好处，如果您使用Collection