views:

144

answers:

4

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?

+9  A: 

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

This cheatsheet is of great help: http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf

Pangea
nice.. great document! thanks!
codechobo
For what it's worth, hash maps in general aren't O(1) in lookup when hash collisions occur (and they can happen pretty often, if very few at a time). Worst case is O(n) in lookup.
Blindy
I agree with Blindy. Performance of hash based collection is limited by performance of hash function.
sbidwai
A: 

hashing(hash set) is the best one with O(1)

Satish
There's 8 minutes between your answer and Pangea's. Yours adds no extra value, so why post it?
Bart Kiers
@bart real slow internet connection
Will
@Will, perhaps. If so, then by now @Satish had time enough to remove his/her redundant answer. Yet s/he chooses to let it dangle. Perhaps in the hope of collection some points? Maybe that was the intention to begin with, who knows?
Bart Kiers
@Bart: your up/down vote ratio suggests you're a little hard toward people. Relax ^_^
Po
@Po, for your information, I'm not being hard to people but to the answers people give of which I think are wrong or do not add any new information. Before I vote such answers down, I usually first give a comment why I think the answer is wrong/inappropriate. If the OP does not take action, or explains him/herself, I cast my down vote. That's what SO is all about after all! If the OP would have added some extra information to his/her answer or simply removed it, I wouldn't have down voted in this case. Again, I am not voting people down (or up), but the answers they give. A big difference.
Bart Kiers
@Po, one more thing, it's all rather subjective me being "harsh" with my down-votes. What if someone who voted 1000 times with just 1 down vote comments on your vote-ratio? In his/her eyes, **you** are also harsh.
Bart Kiers
Ok ok I'm sorry for my superficial comment :D
Po
@Po, no harm done!
Bart Kiers
+3  A: 

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.

starblue
+3  A: 

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.

Peter Lawrey