Fastest data structure for contains() in Java?

Question

What's the data structure in Java that has the fastest operation for contains() ?

e.g. i have a set of numbers { 1, 7, 12, 14, 20... }

Given another arbitrary number x, what's the fastest way (on average) to generate the boolean value of whether x is contained in the set or not? The probability for !contains() is about 5x higher.

Do all the map structures provide o(1) operation? Is HashSet the fastest way to go?

Answer 1

look at set (Hashset, enumset) and hash (HashMap,linkedhash...,idnetityhash..) based implementations. they have O(1) for contains()

This cheatsheet is of great help.

Answer 2

For your particular case of numbers with a relatively high density I'd use a BitSet, it will be faster and much smaller than a hash set.

Answer 3

The only data structure faster than HashSet is likely to be TIntHashSet from Trove4J. This uses primitives avoiding the need to use Integer Objects.

If the number of integers is small, you can create a boolean[] where each value present is turned into a "true". This will be O(1). Note: HashSet is not guarenteed to be O(1) and is more likely to be O(log(log(N))).

You will only get O(1) for an ideal hash distribution. However, it is more likely you will get collisions of hashed buckets and some lookups will need to check more than one value.