Data structure to hold just keys (not caring about value)

Question

I need to store a list of Strings and need to check if a String exists in the list.

I normally would just use some Map with a key and boolean... i.e.

HashMap map<String,Boolean> = new HashMap<String,Boolean)()

And just do a map.contains(string)

This is sort of the way I have always done these kind of lookups in the past because I know that using a map will be O(1) access.

I know this might be nitpicky and unimportant, but I was just curious if there was some structure that was out there that would save that boolean value. Just seems like a waste of memory because I don't care about the false value because if the key doesn't exist that equates to false.

I was thinking maybe pointing a keyword to null would do what I want, but I was wondering if there was some data structure that sort of did this.

Answer 1

This is what the Set<T> collection is for. The HashSet<T> implementation is O(1) and internally does just what you propose: It's a HashMap<T,V> where the value for each key is the same internal Object instance. That is, the source contains

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

and the value of each entry is set to PRESENT.

Answer 2

Maybe a HashSet<E>?

Or indeed, anything that implements Set<E>, although they don't all have O(1) expected lookup.