java - 如果我经常使用 contains 方法，是否有比 HashMap 更好的 DS 来存储项目列表？

Question

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

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

正如您在上面看到的，我将任何东西作为值，因为我不会使用这些值。我已经测试过这个过程比使用 arraylist 快很多。 (此外，hashmap 的 containsKey() 是 O(1) 而 arraylist 的 contains() 是 O(n))

虽然它对我来说效果很好，但由于它不是正确的数据结构，所以感觉很尴尬。这是一个好习惯吗？我可以使用更好的 DS 吗？有没有利用哈希存储值的列表？

Answer 1

I have a list of numbers. In my program I would frequently be checking if a certain number is part of my list. If it is not part of my list, I add it to the list, otherwise I do nothing.

你在描述一个集合。来自Javadoc ，一个 java.util.Set 是:

A collection that contains no duplicate elements.

此外，您描述的操作是 add() :

Adds the specified element to this set if it is not already present.

在代码中，您将创建一个新的 Set(此示例使用 HashSet):

Set<Integer> numbers = new HashSet<>();

然后，每当您遇到要跟踪的数字时，只需调用 add()。如果 x 已经存在，集合将保持不变并且不会抛出任何错误——你不需要小心添加东西，只要添加你看到的任何东西，集合排序的“过滤器” "为您排除重复项。

numbers.add(x);

这超出了您最初的问题，但是一旦您填充了一个集合，您就可以对数据执行各种操作 - 检查其他数字是否存在/不存在，迭代集合中的数字等。Javadoc 显示了哪些功能可供使用。