Is there a better DS than a HashMap for storing a list of items if I frequently use the contains method on it?

user_18494246 0
Viewed 52

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. I have found myself using a hashmap to store the items instead of an arraylist.

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

As you can see above, I put anything as the value, since I would not be using the values. I have tested this process to be a lot faster than using an arraylist. (Also, containsKey() for hashmap is O(1) while contains() for arraylist is O(n))

Although it works well for me, it feels awkward for the simple reason that it is not the right data structure. Is this a good practice? Is there a better DS that I can use? Is there not any list that utilizes hashing to store values?

hashmap list java
2 Answers

An alternative solution from the standard library is a java.util.BitSet. This is - in my opinion - only an option if the values of item are not too big, and if they are relatively close together. If your values are not near each other (and not starting near to zero), then it might be worthwhile looking for third party solutions that offers sparse bit sets or other sparse data structures.

You can use a bit set like:

BitSet bits = new BitSet();

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

And as suggested in the comments by Eritrean, you can also use a Set (e.g. HashSet). Internally, a HashSet uses a HashMap, so it will perform similar to your current solution, but it does away with having to put sentinel values in yourself (you just add or remove the item itself).

As an added benefit, if you use Collection<Integer> as the type of parameters/fields in your code, you can easily switch between using an ArrayList or an HashSet and test it without having to change code all over the place.

user_4668620

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.

You are describing a set. From the Javadoc, a java.util.Set is:

A collection that contains no duplicate elements.

Further, the operation you are describing is add():

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

In code, you would create a new Set (this example uses a HashSet):

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

Then any time you encounter a number you wish to keep track of, just call add(). If x is already present, the set will remain unchanged and will not throw any errors – you don't need to be careful about adding things, just add anything you see, and the set sort of "filters" out the duplicates for you.

numbers.add(x);

It's beyond your original question, but there are various things you can do with the data once you've populated a set - check if other numbers are present/absent, iterate the numbers in the set, etc. The Javadoc shows which functionality is available to use.

user_113749570
Related